AtCoder Regular Contest 064

AtCoder Regular Contest 064やりました。以下感想。

C問題 Boxes and Candles

n個の箱に端の箱から順にキャンディーがa_i個入っている時、隣り合う箱に入っている個数がすべてx以下になるようにするには何個のキャンディーを取ればいいかという問題。

ぱっと見貪欲っぽさがあったので、どういう貪欲か考えた。

とりあえず、箱の中のキャンディをa[i]、隣り合う個数の和を配列b[i]として持ってみる。隣り合う個数について貪欲してみた。

端から順番に、b[i]>xならb[i]とb[i+1]を-=(b[i]-x)。

サンプルがなんとなく通ったので提出➔WA。後ろ4つが落ちる。

ダメなのは例えば以下のケース。

3 2

6 1 6

この時は嘘解法では真ん中の箱が負の値になってしまうので、それを修正して貪欲。AC。

D問題 An Ordinary Game

二人が文字列sに対して、端以外の文字を取り除く操作を行う。ただし同じ文字が隣り合うようにはしてはいけない。最善手を取るとどっちが最後に操作を行えるかという問題。

適当に考察してみて、abababのパターンかaxaxaのパターンになることは分かった。文字は英小文字だから26種類あるし、なんか知識いるのかなぁと思ってE問題に移ってしまった。

戻ってみてよく考えてみる。終状態は何パターンも考えられるし、その中で最善手とか無理だよなぁ〜。abababaにもacacacacaみたいなのにも成りうるし・・・。と悩んでいたのですが、よく考えればどちらも奇数個。同様にabababababのパターンは必ず偶数個。

ガックリきながら、最初の文字と最後の文字と文字列のサイズの偶奇で場合分けしてAC。

E問題 Cosmic Rays

なんか円状のバリアーがいっぱいあって宇宙線がビャービャー降ってて、スタートからゴールまで行く時の当たる宇宙線を浴びる時間の最小値を求める問題。

始点、終点、バリアーの中心を頂点として、各頂点間を直線で進んだ時に宇宙線を浴びる時間を辺の重みとするダイクストラ法で終わり。

とここまでは特に難なくという感じでしたが、ダイクストラをC++で書いたことなし。テンプレもなし。困った困った。

とりあえず「ダイクストラ C++ 競技プログラミング」でググってそれを参考に書く。バグる。いっぱいエラーが出る。困る。よく見たらcin >>x[i] >> y[i] >> r[i] >> endl;って書いてありましたとさ。

適当に書いたらAC。

F問題 Rotated Palindromes

そもそも問題名の英語がわからない。

m種類n文字の数列回文をぐるぐる回した時にできる数列の総数？を求める問題。（あんまりよく読んでない）

周期とか関係ありそーとは思いましたが、なんかよくわかんねえってなって終わりました。終わり。

108位 パフォーマンス2119 新レート1822 (+46)

D問題に気づくのがもうちょっと早ければ、もしくはE問題書くのがもうちょっと早ければと行った感じ。