Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder キーエンス プログラミング コンテスト 2020

3完4WA。相変わらず出さなくていいWAを出しています・・・。

各問題

A - Painting

行か列、どちらか効率のいい方法で塗り続けるのが最善で、塗る回数はN / max(H, W)の切り上げとなります。

B - Robot Arms

いや、Cより苦戦しましたが(実際Cより解けた人が少なかったようですね)、思いついてしまえばなんてことはない問題だったりします。

左から残すロボットを決めていくと考えるとき、正方向に伸ばした腕の座標が最も小さいものを選ぶのが得です。正方向により大きなスペースができるからです。

なので、正方向に伸ばした腕の座標でソートしてから、残すロボットを貪欲に決めていくのが最善になります。

私は、最初全く見当違いの回答を投げて1WA、次に上記考察ができたのに、ソートのロジックでミスして1WAを出してしまいました。落ち着こう・・・。

C - Subarray Sum

N == Kのとき、SをN個並べればいいです。

そうでない時、Sが偶数なら、S / 2K + 1個並べて、あとはSにならないような外れ値(殆どの場合S + 1でOKだが、Sが10^9のときに注意←私はこれで1WA・・・)を並べておけばいいです。

Sが奇数なら、S / 2S / 2 + 1を交互にK + 1個並べて、あとは偶数の時と同様にSにならないような外れ値を並べればいいのですが、これだとSが1のとき死にます。0 1 0 1 ...となって、Aiが1以上の条件に反してしまうからです。(これで1WA)

ていうか、今書いていて気づいたんですけど、単にSをK個並べればいいんじゃないのこれ? あれ!? あれれ? まじか・・・。

D - Swap and Flip

奇数回の移動でBが上に、偶数回ではBが上にしか来ないことも、bit DPを使えばいいこともわかったんですけど、状態の持ち方を発見できず・・・。

まとめ

うーん、頭が回ってなかったですね(いつものことですが)。焦るあまり、考察の詰めが甘くて失敗する悪癖が今回も出てしまったようです。よくレート微減で済んだものだ・・・。

あと、Dのような問題の壁を乗り越えられないと、青は見えてこないですね。

f:id:mdstoy:20200118232125p:plain