ブログ名

競技プログラミングやお歌のお話をする高菜です。

ARC 002 (virtual) 解法

コンテストページ

✔A - うるう年

条件を逆順に走査です。うるう年を知らないと誤読をしてしまいそうです。

✔B - 割り切れる日付

日付のインクリメントを実装して、順番に試していくと、少なくとも 1 月 1 日が割り切れ混ますから、366 回以内で終わります。

✔C - コマンド入力

コマンドを全探索です。 コマンドを決めたら、前から順に見て貪欲マッチです。 ちなみにこの方法は、長さの違うコマンドが("AB" と "BXY" など)があると壊れますから、そのときにはおとなしく DP をしましょう。

✖D - ボードゲーム

誰にも邪魔されない駒があったら走り続ければよいです。 そういうものがあったら、両方なら速い方、片方ならその人の勝ちです。

ないときを考えます。(最終的に自分が動かせる回数 )− (相手が動かせる回数)を最大化させましょう。これが大きいほうが勝ちで、同じ場合は後攻の勝ちです。このとき自分から死にに行くと、この利得が大きく減少しますから、よくありません。そこでそうい手は打たないことにしましょう。

すると、('o' と '.' ばかりのエリア)と('x' と '.' ばかりのエリア)とを 2 つ繋げたようなバトル空間が存在するように見えます。それぞれで利得を最大化するには、先頭の駒を前進させればよいです。ではどのバトル空間を優先させるかを考えましょう。それは、'o' と 'x' の合計が多いほうが優先です。なせなら一つ動かすことで得られる利得(より性格に言うと、「確定している分(?)」)がこれに等しいからです。

結果

f:id:ngtkana:20200124012501p:plain

残念ならがら、3 完に終わってしまいました。難しいです。なにか見落としているのでしょうか。