ABC109

A - ABC333

A問題のわりにパッと見で趣旨がわからない。よく読むとわかる。制約が異様にきついのは関係なくて(今考えると、ループを使わずCを全通り試せるように)、単にA*Bが偶数ならA*B*Cを奇数にできないというだけ(そういえばCに奇数を設定できることを確認せずに書いたな)。実装は簡単な問題。なんとか1分切りでACできた。

B - Shiritori

こちらはパッと見で趣旨がわかる。でも確認のために問題文を読む(趣旨がわかっていると読むのは楽)と、同じ単語を2回言ったらダメなことに気づいてなかった。「ん」で終わってはいけないという条件がないかしつこく確認した(なかった)。あとはやるだけ。計算量は大きくなるが、B問題なので愚直にループを書いていく。お尻の文字を得る方法を思い出すのに少し時間がかかった。end()は最後の文字へのイテレータじゃない。back()が最後の文字だ。僕が競プロで使う紙のノートの裏表紙にはback()と書いてある。そして最初の文字はfront()だ。同じ単語があるかの確認は、setとかも考えたが二重ループでいい。気持ちよく書いてAC。高橋くんが10秒間に発言した単語が与えられていたことには今気づいた。

C - Skip

C問題らしく、解けてないうちから実装が軽そうな雰囲気を感じる。Xから見て距離がDの倍数の座標にしか行けないというシンプルな状況だ(文字にするとあれだが、これは紙に書いた図からの感情)。ただ、どうやって最大値を求めるのかはずぐにわからなかったので、1から順に試すのか?とか思ったが、それはO(N)じゃなくてO(max(x))だ。で、入力部分を書いているうちに、これはxではなくx-Xが欲しい情報だとなり、ああ最大公約数かと。制約が10^9以下なので、1回の加減算はintで大丈夫。手持ちのgcd関数に負の数を入れたときの挙動を知らなかったので単にabsをとる(今見るとやはり負の数には対応してなかった)。あとは最大公約数をとっていくだけだが、答えの変数の初期値は0だ。0はどんな正整数ででも割り切れる。さて、Xと同じxはないという制約を思い出す。もし座標Xにしかxがなかったら、このプログラムは答えとして0を吐く。それは、最大というか雰囲気としては無限大みたいな。みたいではないか。でかい数の階乗がわりと何ででも割り切れるみたいな雰囲気。そういうときに変な値にならないよう親切な制約なのか?いや、そもそもDが何でもいいから最大値が存在しない。大体状況をつかんだところで提出。

D - Make Them Even

aが9までと小さいので怖いが、状況はけっこう単純で、奇数の近いマス同士でペアを作り片方から1枚移動させるだけでいい。コインの数の合計が奇数なら1マスだけ奇数のままになる。さて、近いペアを作るのは相当大変そうに見える。最大マッチングとかより難しいんじゃないか?これはおかしいと思い問題文を読み直す(このムーブつよい)が、特に誤読はしていない。と思ったら、操作を「何度でも行うことができます」という部分をスルーしていた。そういえばそんなこと書いてあったなあ。あのとき(読んだとき)はまだ問題の趣旨がわかっていなかった。しかしこれ、TLEさえしなければどんなに操作回数が多くてもいいのか?そうだとしても、それに関する注意書きがあるはずだけど。と思っていたが、だいぶあとになってH*W以下という制約があることに気づいた。0以上ともあるので、操作する必要がないときは0とだけ出力すればいいのだろう。答えが複数あるかもしれないという記述もあると嬉しかった。
さて、回数制限がないとすると解法はすぐに思いつく。盤面全体を1列に、例えば上からジグザグに全部のマスを一筆書きする。その順に見ていって、コインの数は2で割ったあまりだけが重要なのでそうして、コインがあるマスに当たったらそれを道なりに移動させていって、コインのあるマスに来たら止まる。また次のコインを探すという感じ。全体のコインが奇数のときも、最後のコインが最後のマスまで移動するという無駄な動きが加わるだけで、答えとして問題ない。この解法は都合よく操作回数がH*W以下になっている(1列にしてあるので移動回数は最大でH*W-1)。書いて、とりあえずサンプルで様子を見ると、3つのサンプルのうち2つが通った(答えが複数ある問題なのに!)。よく見ると、出力例2がかなり親切だ。いや、無駄な動きをしてくれてるだけかな。答えが複数ある問題でサンプルが通っているのでわりと安全そうだが、まあ複雑そうな問題で怖いので最後に少し見直しをしてから提出。
今回、C問題までは簡単だったが、難しいD問題ももうちょっとスピードを出すべきだった(今回は慎重すぎた)かもしれない。わりと得意分野で、しかも解法のアイデアはわりとすぐに思いついていた。なかなか、ちょうどいいアクセルの踏み方というのは、普段からやってないとね。ていうかそれがわかるってことはほとんど解けてるってことだよな。