競技プログラミング

AtCoder ABC068-D, ABC078-D

ABC068-D

問題

考えたこと

まず制約がバカでかいのでO(1)で解けるしゅっとした解法がありそうだなーと思った。

とりあえず配列サイズ2で考えてみると片方から2引いて片方に1足すという作業を繰り返すことになるのでこれでいいぢゃん!となり適当に書いて提出するもWA。

なんでやろなーと思い制約を見返してみると各数列の値は10^16 + 1000以下でなけばならないらしい。だめぢゃん!

この制約からしてたぶん配列サイズは50に固定した方がよさそうと考えそうすることに。

50が50個並ぶとちょうどK=50回となることに気づきそれなら51ひとつと50が49個並べばK=51になるのではと思い(ここが間違っていてK=100になる)、実装してみて出すもWAなので心が折れる。

正解

少し惜しいところまでいっていた。

太字で書いた箇所でもう少し丁寧にシミュレートして段差にすればいいよねと気付けていればACできたであろう。

正解は0から49までが並んだ状態をスタートとし、最も小さい値に+50、それ以外は-1をしていくという、操作を逆から考えていくもの。この逆操作を50回すると全体が+1されるので、K/50回全体に+1をして、残りK%50回だけ愚直に逆操作をしてやれば良い。

ABC078-D

問題

考えたこと

もうさっぱり何もわからなかった。力尽く解法もうまく実装できなかった。手で実際やってみても何も見えなかった。「スコアを最大化するように」「スコアを最小化するように」の意味がわからなかった感じ。

正解

もしXが全部取ったらスコアはabs(a[N] – W)で最後の1枚以外を取ったらabs(a[N-1] – a[N])になる。それ以外の時はYは最後の1枚だけ残すことで最低でもスコアabs(a[N] – a[N-1])を達成できてしまうので、Xとしてはmax(abs(a[N] – W), abs(a[N-1] – a[N]))を取るしかないよね、というお話らしい。

いろいろと実際手でシミュレートしてみたつもりだったのでそれで何も見えなかったのが悲しい。

ただD問題は「結局数パターンしかないよね」というやつはよく見る気がするので今度お手上げ空気漂う問題に出会ったらそういう見方もしてみようと思った。