yukicoder No.374 コイン
問題
2人で以下のゲームを行う。
・半径Aの円の中に、半径Bの円を交互に置いていく
・置いていく円は、半径Aの円からはみ出したり、すでに置いた円とかさなったりしてはいけない
・先に置けなくなった方が負け
・置かれた円は動かせない
それぞれ最適に行動した場合、どちらが勝つか答える。
制約
1 <= A,B <= 2^32
解説
A < Bの場合、先手がすでにおけないので、後手の勝ち。
A >= Bの場合を考える。
2*A/3 < Bの場合は、真ん中に置くと、その後、どこにも置けなくなるので、先手の勝ちということがわかる。
2*A/3 >= Bの場合は、先手がどこに置いても後手に手番が回る。
最適な行動は、まず、真ん中に置いて、後手に手番をわたす。
後手がどこに置いたとしても、「円の中心の点対称の位置に円を置く」ということを繰り返すと、必ず先手はおくことができる。
したがって、先手がこの行動をとった場合、必ず勝てるので、先手の勝ちとなる。
AtCoder Regular Contest 055 C. ABCAC
問題
文字列Sが与えられる。
この文字列は、それぞれ長さ1以上の文字列A,B,Cを「ABCAC」のように連結してできている。
このような分割は何通りあるか?
制約
5<=Sの長さ<=200,000
(部分点:Sの長さ<=2,000)
解法
説明のために、「A B C A' C'」と置く。N=(Sの長さ)とする。
もし、A'が出現する位置がxだとわかったとして、A'の長さが決まれば、C'の長さが決まる。
なので、A=A'となる最大の長さa、C'=Cとなる最大の長さcが高速に求まれば、以下から判定できる。
・a+c<(N-x)ならば、作ることができないので、無し
・x<=(N-x)ならば、Bの部分を作ることができないので、無し
・候補となるA'とC'の最大の長さは、1文字以上である必要があるので、それぞれ、min(a,N-x-1)、min(c,N-x-1)
・このとき、組み合わせの数は、「min(a,N-x-1) + min(c,N-x-1) - (N-x) + 1」で求められる
・min(a,N-x-1)+min(c,N-x-1)==N-xの場合は、1通り
・min(a,N-x-1)+min(c,N-x-1)==N-x+1の場合は、2通り
・、、、
ということで、位置xにおける「A=A'となる最大の長さa」と「C'=Cとなる最大の長さc」を高速に求める必要がある。
エディトリアルではいくつかの方法が紹介されているが、SuffixArrayと高さ配列を使っても解けるので、それを試してみる。
高さ配列は、SuffixArrayが構築されている場合、次の接尾辞とのprefixの一致数をO(N)で求められる。
SuffixArrayの中で、インデクスが0の部分が「Sの先頭からの文字列」を表すので、そこから前後に高さ配列の値が降順になるようにすれば、すべての位置に対する「A=A'となる最大の長さ」を求められる。
インデクス | 接尾辞 | 高さ配列 | 高さ配列の値をインデクス0から降順になるようにしたもの |
---|---|---|---|
11 | 0 | 0 | |
10 | a | 0 | 0 |
7 | abra | 1 | 1 |
0 | abracadabra | 4 | 4 |
3 | acadabra | 1 | 1 |
5 | adabra | 1 | 1 |
8 | bra | 0 | 0 |
1 | bracadabra | 3 | 0 |
4 | cadabra | 0 | 0 |
6 | dabra | 0 | 0 |
9 | ra | 0 | 0 |
2 | racadabra | 2 | 0 |
インデクスが0の部分から、高さ配列を前後にそれぞれ降順になるようにしたものが表の一番右。
これは、min()を取りながらO(N)で求められ、これは位置xに対する「A=A'となる最大の長さ」の情報になっている。(ので、O(1)で求められる)
「C'=Cとなる最大の長さc」については、文字列Sをreverseしたものについて同様に行えば、位置x-1で終わるようなCの最大の長さがO(1)で求められる。
したがって、
・SuffixArray構築にO(N)~O(N log^2 N)
・位置xを決めるためにO(N)
・aとcを求めるのにO(1)
・位置xでの組み合わせの数を求めるのにO(1)
なので、全体でO(N)~O(N log^2 N)程度で求められる。
解法2
Z algorithmは上のをO(N)で作ることができる。
//z[i]:=文字列sと、位置iから始まる部分文字列との共通接頭辞の長さ(ただしz[0]=0) std::vector<int> Zalgorithm(const std::string& s){ int n = s.length(); std::vector<int> z(n, 0); int L = 0, R = 0; for(int i=1; i<n; i++){ if(i>R){ L = R = i; while(R<n && s[R-L] == s[R]) R++; z[i] = R-L; R--; }else{ int k = i-L; if(z[k] < R-i+1){ z[i] = z[k]; }else{ L = i; while(R<n && s[R-L] == s[R]) R++; z[i] = R-L; R--; } } } return z; }
テンプレ
コードも残したいと思います。
使っているテンプレは以下です。
#include <algorithm> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <iostream> #include <queue> #include <list> #include <stack> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll;