ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ABC109 参加記録

2週間ARCとの併催で配点が恐ろしい感じでしたが、久しぶりにまともな配点のABCになりました。

結果は16分台全完で18位。けっこう速かったですね。ARCでもDが400だったらこのくらいの速度で解きたいです。

f:id:betrue12:20180908212243p:plain

A - ABC333

A - ABC333

解法

 A B のどちらかが偶数だったら  A \times B \times C は必ず偶数になります。また、 A B が両方とも奇数だったら  C = 1 とすることで積を奇数にできます。これを場合分けします。

ACコード

RubySubmission #3151145 - AtCoder Beginner Contest 109

B - Shiritori

B - Shiritori

解法

重複した文字列があるかの確認をして、  i 番目の末尾と  i+1 番目の先頭が一致しているかを  i=1, ..., N-1 について判定すればよいです。

ACコード

RubySubmission #3152443 - AtCoder Beginner Contest 109

C - Skip

C - Skip

解法

座標  X からのスタートだと考えにくいので、まず  x_{i} 全てから  X を引いて、座標0からのスタートだとしてしまいましょう。

そうすると到達可能な点は、座標0からスタートして任意回の  \pm D の移動で到達できる点、つまり  D の倍数です。つまり、(補正後の)  x_{i} 全てが  D の倍数であるという条件を満たすように、なるべく大きな  D を選べばよいです。これは  x_{i} の最大公約数になります。

ACコード

RubySubmission #3153468 - AtCoder Beginner Contest 109

D - Make Them Even

D - Make Them Even

解法

問題文だけ読むと分かりませんが、出力例を見ると構築問題であることが分かります。

全コインの合計が偶数だった場合は、全マスを偶数にするのが最適です。全コインの合計が奇数だった場合は、1マスを残してそれ以外を偶数にするのが最適です。このように作れないか考えます。

全マスを一筆書きできるような経路を考えます。そのような経路をずっと辿っていき、「マスのコイン数が奇数だったら次のマスに1個渡す」ということを繰り返していくと、全マスについての操作回数を1回以下にしつつ、最後に訪問するマス以外は全て偶数個コインにできるはずです。

場合によってはちょっと操作回数に無駄がありますが、操作回数は最小化しろと言われていないので、これで大丈夫です。一筆書きの経路は、例えば以下のようなものを作ると良いでしょう。

f:id:betrue12:20180908224134p:plain

ACコード

RubySubmission #3155067 - AtCoder Beginner Contest 109

さいごに

最近激しい回が続いていましたが、ちょっと和みましたね。