CODE FESTIVAL 2017 qual C
作成日：2017.10.24
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点が$100-200-400-700-1600-1800$なので、D問題までの早解きをまずは目指す。
早解きに失敗、すなわちD問題までを40分前後で解けなかったらE,Fのいずれか簡単そうな方に時間をつぎ込む。
また、これまでの予選ではCで時間を食ったりDが解けなかったりしたので、それらの問題を先に見る。
コンテスト中
今回はC問題から見た。
なんとなく解法が浮かんだので実装し始めたが、書いたコードの前半が不要であることに後半を実装している時に気付いた。
若干時間を無駄にしたが、すぐに書ききった。[C 08:45 AC]
次にD問題を見て雰囲気をつかんでから、A,B問題を解いた。
B問題は初め誤読していたが、サンプルを見てコードを書く前に気付くことができた。[A 11:31 AC][B 14:47 AC]
D問題に戻るとbitmaskっぽいという感覚が得られ、そこから考察がトントン拍子で進んだ。
このようなことは、700点付近の問題では久々である。[D 24:46 AC]
残るはE問題とF問題だが、Eは立体図形が出てきて考えにくそうだったのでF問題に取り組み始める。
しかしDPの遷移式をサンプルからエスパーしようとしたため、解けるわけなく終了。
コンテスト後(結果)
4完1400点の61位。パフォーマンス2800、新レート2394(+57,highest)。
D問題までの早解きが成功したのは今回の良かった点。
ただF問題に90分ほどかけることができたのに、漸化式を実験から求めようとする悪い癖によって解くチャンスを逃してしまったのは反省点。
各問題の(軽い)解説
- A : Can you get AC?
- B : Similar Arrays
- C : Inserting 'x'
- D : Yet Another Palindrome Partitioning
- E : Cubes
- F : Three Gluttons
A : Can you get AC?
問題文
隣接する2文字それぞれについて$"AC"$となっているか調べれば良い。
B : Similar Arrays
問題文
数列$\{b\}$の積が偶数になるということは、要素のうちいずれかが偶数であるということである。
これを考えるのは難しいから、あり得る$\{b\}$の数から要素のすべてが奇数であるものの数を引いて求める。
前者は$3^N$であり、後者は数列$\{A\}$の要素で偶数であるものの数を$a$とすると$2^a$であるから簡単に求められる。
C : Inserting 'x'
問題文
文字列が回文であるかどうかは、両端から見ていけば判定できる。
今見ている2つの文字が同じであればともに1つ内側の文字に移り、そうでない時は回文でない。
しかし後者の時には、見ている文字のいずれかが$'x'$であれば、$'x'$でないほうの外側に$'x'$を挿入することで回文になるかもしれない。
これを繰り返して、見ている2つの文字が一致するかすれ違えばその時に限り元の文字列は回文にできることが分かる。
またこの時$'x'$を挿入する最小の個数も同時に求まっている。
D : Yet Another Palindrome Partitioning
問題文
ある文字列を並び替えると回文にできる条件$C$は、その中に含まれている個数が奇数である文字種が高々1個であることである。
ここで、先頭から$i$文字まで見た時の問題の答えをもつDPを考える。
このDPを愚直に行うと$j(>i)$文字目から$i$文字目までを分割できるかを確かめるつつ更新することになるが、これは良くても計算量が$O(N^2)$となり間に合わないので工夫する。
$C$を満たすかを判定したいから、各文字種についてはその数の偶奇以外には関心がない。
そこでbitmaskとして$i$番目のビットが$i$番目の文字種の偶奇に対応するようなものを考える。
すると累積和と同様に考えることで、文字列中の任意の部分を切り出した文字列のbitmaskは接頭辞のbitmaskが分かっていれば求められる。
さらにDPが持つ状態を位置の代わりにbitmaskで持つと遷移が$O(1)$でできるようになるので解ける。
E : Cubes
問題文
座標が変わった時に新たに距離が$D$以下となるブロックの数を数えることができれば良い。
針金に沿っていきブロックの座標が変わる時は、1つの座標のみが変わることが$A$,$B$,$C$が互いに素であることから分かる。
そこで変わった座標を$a$,変わらなかった座標を$b,c$とする。
$a+D \geq A$の時は増えない。
そうでない時は$Y=$$min(B-1,b+D)$$-max(0,b-D)$$+1$,$Z=$$min(C-1,c+D)$$-max(0,c-D)$$+1$とすると$YZ$である。
$Y$や$Z$の値が変わるのは、端のブロックから距離$D$以下であるブロックを通る時である。
そのようなブロックは$O(D)$個である。
$Y$や$Z$の値が変わらない部分はまとめて考えることができるから、答えも$O(D)$で求めることができる。
但し$Y$や$Z$の値が変わる位置を列挙して適切な順序に並べるのに$O(D log \: D)$かかるが、これでも十分高速である。
F : Three Gluttons
問題文
$A,B$が$i$個目に食べる寿司のそれぞれの順位付けにおける順位を$x_i,y_i$とする。
状態として$i,x_i,y_i$の組を持ち、$i$個目とその先の寿司の食べ方を求めるDPを考える。
まず$i = N/3$の時は、$b_{y_i} \neq a_j(j \leq x_i)$かつ$a_{x_i} \neq b_k(k \leq y_i)$ならば$a_p = b_q$となる$p(>x_i)$,$q(>y_i)$の組の数、そうでないならば$0$となる。
前者は$C$が食べることのできる寿司の種類の数を表しており、条件は食べようとしている寿司がなくなっておらず喧嘩もおきないことを表している。
$i = t < N/3$の時は、$i = t+1$の時のDPの値のうち$x_{t+1} > x_t$ , $y_{t+1} > y_t$を満たすものの総和を$max(0,$$(i=N/3$,$x_i = x_t$,$y_i = y_t$の時のdpの値$)-3(N/3-i))$である。
これは寿司を食べ進めれば$x_i$,$y_i$は単調に増加することと、$C$が食べることのできる寿司の種類からは$t$個目を食べた後に食べる予定となっている$3(N/3-i)$種類の寿司を取り除く必要があることから分かる。
これで漏れも重複もなく数えられているので、答えは$i = 1$,$x_i = 0$,$y_i = 0$のdpの値である。
計算量は累積和を用いれば$O(N^3)$であるから、十分高速である。
＜(古い記事) CODE FESTIVAL 2017 qual B
関連
CODE FESTIVAL 2017 Team Relay (新しい記事)＞
＜(古い記事) CODE FESTIVAL 2017 qual B