[Yukicoder] おやすみ

https://yukicoder.me/problems/no/648

基本的にはむこさんの解説のとおり、(sqrt(8*n+1)-1)/2を出力すれば良いですが、実装上の別解を。

  1. Integer sqrtの利用
  2. sqrtlの利用
    • long doubleの仮数部が64bitであることを思い出せば、sqrtlを使えば解けることは想像に固くありません。1
    • C https://yukicoder.me/submissions/206063
    • Python (ctypes) https://yukicoder.me/submissions/207816
      • intをマーシャリングするときにfloatを経由されるといけないので、sscanfを用いて自力でマーシャリングする必要があります

  1. あれ、topcoder初出場で撃沈したのは誰だ^^; (SRM 635 Div2 Medやらyukicoder No.413やら)↩

[Yukicoder] 旅館の予約計画

https://yukicoder.me/problems/no/580

  • 区間スケジューリング問題の、スロットが複数あるバージョンである。
  • 基本的な解き方は同じだが、popするスロットは、「部屋iの(出)時刻がdata[i]の入時刻より早い中で最大」のものである。
    • このスロットを検索するには、multisetを2分探索する以上に効率のよい方法はなさそうである。
      • 勿論普通の区間スケジューリングではこの集合は1個しか無いため定数時間である。
    • 私は最初、最小のものがdata[i]の入時刻より早ければpopする実装にして盛大に間違いました…

  • スロットを線形探索しないため、計算量をnからlognに落とすことができ、合わせてO(m(logm+logn))となる(実際にはn<mだと思われるのでO(mlogm))。

  • https://yukicoder.me/submissions/211209 (現状の最短時間とのこと)

  • n<=10000, m<=100000なるHardバージョンを作ろうと思いましたが必要ない気もするのでやめておきます。。

[Atcoder] ConvexScore

http://arc082.contest.atcoder.jp/tasks/arc082_c

初版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<long double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
bool intersectSP(const L &s, const P &p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<L>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      L l(v[i],v[j]);
      int n=0;
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectSP(l,v[k]))n++;
      r=(r-pow_binary_mod(2,n,M))%M;
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

点が載っている判定を直線へ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

bool intersectLP(const L &l, const P &p) {
  return abs(cross(l[1]-p, l[0]-p)) < EPS;
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int> >se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      L l(v[i],v[j]);
      vector<int>x={i,j};
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectLP(l,v[k]))x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          int n=b-a-1;
          r=(r-pow_binary_mod(2,n,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

インライン化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int>>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      vector<int>x={i,j};
      for(int k=j+1;k<N;k++)if(abs(imag(conj(v[j]-v[k])*(v[i]-v[k])))<1e-12)x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          r=(r-pow_binary_mod(2,b+~a,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N%M-N-1
N.times{|i|(i+1...N).map{|j|
  h[x=[i,j]]||
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k}&&
  (l=x.size).times{|a|(a+1...l).map{|b|
      r=(r-2**(b+~a))%M
      h[[x[a],x[b]]]=1
  }}
}}
p r

最終版

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N+~N
[*0...N].combination(2){|i,j|
  h[x=[i,j]]||(
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k};
  r-=2**(l=x.size)+~l;
  x.combination(2){|a,b|h[[a,b]]=1})
}
p r

[Yukicoder] 夏休みの思い出（１）

https://yukicoder.me/problems/no/550

  • 解と係数の関係から3因数はCの約数である.
  • https://gist.github.com/pekempey/9eddf9342f65552a92845e035960e8a3 によると約数の個数は最大で103680なので、約数の全列挙をすればこの問題を解くには十分である.

  • なお, Cの最大値は10**18であるが, 因数の最大値は10*9であるという制約があるので, Ruby標準ライブラリの素因数分解で問題ない.

    • -1999999865 999999864000004607 999999866000004473という入力(出力は-1 999999929 999999937)で死ぬので, 素因数列挙だけで解きたい場合はロー法を使いましょう…

  • Ruby標準ライブラリ(リジャッジでTLEになる予定) https://yukicoder.me/submissions/192779

  • ロー法 https://yukicoder.me/submissions/192783

FXCampusGatePrinterはネットプリントドライバとしても使用できない

背景

  • ファミリーマートやローソンのネットワークプリントはプリンタドライバが存在するが、セブンイレブンのネットプリントはプリンタドライバが存在しない。
  • ECCS2012(ゼロックス)のプリンタドライバはネットプリントドライバとしても使うことが出来た。
  • 現在のECCS2016では業者がリコーになったが、ネットプリントドライバ部分はまだ使えるのではないか？
  • しかし、使ってみようとすると、接続エラー(320000)となる。

調査

  • /Library/Printers/FujiXerox/FXCampusGatePrinter/FXCampusGatePrinter.plist から、
  • https://sdb.fujixerox.co.jp:443/CGPPrintPortal/Service.svc
  • という内容が読み取れる。このサーバーは現在停止している。
  • したがって、ネットプリントドライバとして使うことも現在は不可能である。

結論

  • 個人的には当面はネットワークプリントだけを使うことにします…

LAPLACE LINK

前説

LAPLACE LINK。ブラウザでターン制じゃなくてリアルタイム協力バトル。ブラウザゲームとしてはグランブルーファンタジーが一強で、これを超えるゲームはなかなか出てこないだろうと思っていた矢先の発表だったので、cTouchの作者としてはすごく期待していました。

ゲームデザイン

で、実際にやってみたところ、まあガチャは仕方ないにせよ、まず装備品がキャラごとなのが割と辛い。あ、その、装備制限はいいんですが、個数制限があるんですね。普通のRPGだと仲間になるキャラなんて10人もいませんからそこまで考えなくてもいいんですが、こちらはたくさんいますからね…。育てたいキャラを変えるには前のキャラから装備品を剥がす必要があるのは面倒でした。グラブルは(得意武器を合わせれば加算攻撃力がブーストされますが)武器編成は編成ごとで、しかも武器のみという潔さ。実は武器が10個も装備できるってどういうことなんだろうと思ったことも昔はあるのですが、現実を求めすぎるとソーシャルゲームの実情に合わなくなるつまりゲームデザイン的な都合だったのでしょうね。デザイン、難しい。あとは肝心のマルチバトルの報酬がころころロール(Attacker/Breaker/Defender/Healer)を切り替えたほうが多くもらえるってどうかしてそう。普通は集中すべき、みたいな。

戦闘

戦闘はとりあえず重かったですね。携帯は愚かiPad Proですらさくさくな動作は望めませんでした。専らcTouch入れたSafariからやってました。運営はcTouchを推奨しているのか?と疑うほどだったと思います。

cTouchの不具合的な

ただ、cTouchの作者としては思い残すことが1個だけあって、何らかのボタンをおそうとすると2回押されてしまうことがありました。これはタッチイベントの発火順に起因していて詳細は未だに調査中なんですが、FastClickが入っていても同様となります。実際、FastClickが導入されているとうまく動かないゲームがあるので、このモジュールは消すようになっています。しかしながら同様の処理をFastClickなしで実装することも勿論できて、どうすべきかというのが課題として残りました。

終わりに

結局何が原因でサービス終了となったのかは謎のままですが、もうちょっと頑張ってほしかったですね。

[Atcoder] Tournament

https://agc009.contest.atcoder.jp/tasks/agc009_b

概要

  • トーナメント戦を行ったところ、1番の選手が優勝した。
  • 他の選手について、誰に負けたのかが与えられるので、条件をみたすようなトーナメント表の深さの最低値を求めよ。

考察

  • ある選手がどの選手を倒したかのグラフを作成し、1番の選手から再帰。
  • 倒した選手(N人)のそれぞれについてトーナメント表の深さを求めようとする(倒した選手がいなければ0)。
  • 深さを降順にソートし、これらに1からNまでの数値を割り当てて、足す。
  • 足した後の配列の最大値が答えである。

再帰の深さ

  • 単純に実装すると、最悪10万回の再帰が必要になり、スタックオーバーフローになるおそれがある。
  • 今回、C++は 偶然 大丈夫であったが、RubyやPythonだと不可であった。
    • スタック拡張テクを使っても依然として通らない。
  • 今回は場当たり的(テストケース依存)な対応になるが、N/2番の選手から一旦再帰しておくことで再帰の深さをある程度減らすことができる。
    • この状態でもスタック拡張テクは依然として必要である。

解答例

余談

単位取得退学します

【http://www.adventar.org/calendars/1388 の12/10分です】

高校

東大はBランクだったが、記念受験とした結果実力を出し切れたらしい。(現役)

学部

今の研究室には学部時代の体験ゼミでお世話になった。生物とコンピュータを両方取り扱う分野ということで興味を持った。 学部の研究室は、今の研究室の教授から紹介してもらった。割と良い論文が書けた。

修士

割と良い論文が書けた、とあるが、これは学士の水準である。これを修士の基準に持っていくのは不可能であった。 1個目のテーマは論文を書いたが、学士よりも酷い内容だったので捨てた。 最終的なテーマを決めるのには結局2年半かかった(※1留)ということになり、半年で修士論文を書いた。こちらはまあまあの出来だった。

博士

博士号取得要件は、論文を査読付き雑誌に掲載することである。 修士論文のテーマでは不可能だった。 結局まともな研究を始めたのは2年秋だった。 博士3年の初めにfastqの話で論文を書いたが、内容に不備があり、修正叶わず投稿には至っていない。 予備審査は通して頂けたが、本当にやる気のある学生なら1ヶ月で仕上げられられる内容の研究しかしていない。 データの不足を痛感しつつも、親の希望により職に就くこととなった。

というわけで2017/3を以って単位取得退学となる。まずは3月までに雑誌に投稿できるかが勝負である。

[Yukicoder] (^^*)

http://yukicoder.me/problems/no/457

概要

  • 間に部分列^^*を含むような(と)の組み合わせの個数を求めよ。
    • reverse.tr('()',')(')なる処理を加えれば右向きを別に考えなくて良くなる。

考察

O(S2 logS)

  • (と)の組み合わせをすべて求めて、それぞれに対し、^^*が含まれることを判定します。
  • まず^^が含まれる一番左の座標を求めます。
    • その座標までに含まれる^の個数を累積和として持ち、(の座標における累積和+2を2分探索します。
  • 次に、その座標から)の座標までについて、*が含まれるかどうかを2分探索します。
  • 以上によりO(S^2 logS)となり、C++では通すことができます。
    • 本家解説によると愚直解はTLEらしいですが、2分探索に落とし込んだことが功を奏したのでしょうか。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int solve(char *s,int len){
  vector<int>al;
  vector<int>ar;
  vector<int>ah(len);
  vector<int>ast;
  for(int i=0;i<len;i++){
      if(s[i]=='('){
          al.push_back(i);
      }else if(s[i]==')'){
          ar.push_back(i);
      }else if(s[i]=='^'){
          ah[i]++;
      }else if(s[i]=='*'){
          ast.push_back(i);
      }
  }
  for(int i=1;i<len;i++)ah[i]+=ah[i-1];
  int ret=0;
  for(auto &l:al){
      for(auto &r:ar){
          if(l>=r)continue;
          int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
          if(hidx>=r)continue;
          auto st=lower_bound(ast.begin(),ast.end(),hidx);
          if(st!=ast.end()&&*st<r){
              ret++;
          }
      }
  }
  return ret;
}
char s[10001];
int main(){
  scanf("%s",s);
  int len=strlen(s);
  printf("%d ",solve(s,len));
  reverse(s,s+len);
  for(int i=0;i<len;i++){
      if(s[i]=='(')s[i]=')';
      else if(s[i]==')')s[i]='(';
  }
  printf("%d\n",solve(s,len));
}

O(SlogS)

  • 以下、最も重いループの計算量を減らすことを考えます。
  • まず、rは単調増加であるため、st!=ast.end()&&*st<rが一度真になれば、そのループの中では常に真になります。よってキャッシュすることができます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(auto &l:al){
  bool f=false;
  for(auto &r:ar){
      if(l>=r)continue;
      if(f){ret++;continue;}
      int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
      if(hidx>=r)continue;
      auto st=lower_bound(ast.begin(),ast.end(),hidx);
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • さらに、hidxおよびstはrに依存しないため、ループrの外で計算しておいて問題ないことがわかります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(auto &l:al){
  // if hidx>=r, l>=r is assured because hidx>l.
  int hidx=distance(ah.begin(),lower_bound(ah.begin(),ah.end(),ah[l]+2));
  // if hidx==ah.size(), st==ast.end() is assured because hidx==len.
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  bool f=false;
  for(auto &r:ar){
      if(f){ret++;continue;}
      if(st!=ast.end()&&*st<r){
          ret++;
          f=true;
      }
  }
}
  • arのループはFF...FFTT...TTのようになるので、このTになる場所を2分探索できます。
1
2
3
4
5
6

for(auto &l:al){
  int hidx=lower_bound(ah.begin(),ah.end(),ah[l]+2)-ah.begin();
  auto st=lower_bound(ast.begin(),ast.end(),hidx);
  if(st==ast.end())break;
  ret+=ar.end()-lower_bound(ar.begin(),ar.end(),*st);
}
  • 最後に、範囲を狭めるためのtweakを入れます(必要ではありませんが…)。
1
2
3
4
5
6
7
8

auto ist=ast.begin();
auto ir=ar.begin();
for(auto &l:al){
  int hidx=lower_bound(ah.begin()+l,ah.end(),ah[l]+2)-ah.begin();
  ist=lower_bound(ist,ast.end(),hidx);
  if(ist==ast.end())break;
  ret+=ar.end()-(ir=lower_bound(ir,ar.end(),*ist));
}

O(S)

  • 動的計画法によりO(S)に落とせるようです。コードがより短い実装はそうなっているものが多いようです。

[Atcoder] 木の問題

https://cf16-relay-open.contest.atcoder.jp/tasks/relay_k

概要

  • 問題文がそれなりに読みにくい。
  • いわんとしていることは、選んだ頂点については2回通ってはならないということである。この状況で選ぶ頂点の数を最大化すれば良い。
  • 答えは木の直径以上になることは容易に想像がつく。

考察

  • 枝分かれする(辺が3本以上ある)頂点については、つながっている辺の先にある葉(辺が1本ある頂点)を選んだほうが良いのは明らかである。
  • 問題は辺がちょうど2本ある頂点であるが、木の直径上にある頂点を選ぶ方法でサンプルは通る。
  • しかし、たとえばこういう入力の場合、sub-optimalになってしまう。
1
2
3
4
5
6
7
8
9

o-o-o-o-o
    |
  o-o-o
    |
  o-o-o
    |
  o-o-o
    |
    o
  • 対処するには、木の直径を求めるコードを変形し、頂点の重みを、辺が2本ある場合のみ1に、それ以外は0とすれば良い。

解答例

感想

  • これを時間内に思いつくのはやはりすごいと思いました…