こんにちは.19の皆さんは初めまして.最近競プロを少し真面目にやってみようかと思っていたので競プロでボクが面白いと思った問題を紹介します.

そもそも競プロとはなにってかたは2日前のeiya君の記事をみるとわかります.

今回紹介する問題は面白いとは思ったのですが,ボクは解説を読んでも理解にとても時間のかかりました.ゲーム木の類の問題だそうです.

今回書く内容は,プログラミングには触れません.またAtcoderのC問題なので競プロができる人には退屈な記事になると思います.
今回紹介する問題は$ABC025$-Cです.
問題
問題を見たい人は↑のリンクを見てください.

どちらが勝つでしょう??という問題

今回考える問題

問題

2人のプレイヤーが2✖️2のマス目に交互に自分の色の石を置いていく.石の置く場所により得られる得点は先に決まっている.この条件でお互いが最善手を尽くした時に最初に石を置くプレイヤーは何点取ることができるか??

今回扱う状況
青 → オレンジ → 青 → オレンジ の順番で石を置く
左上から時計回りに$7,13,17,23$の点数が得られるとする(下図)

この問題では最終的な青とオレンジの点数の合計が一定なので,オレンジは青の点数が最小になるようにすれば自分の得点を最大にすることができます.

実際には点数の大きい場所からおけば済む問題なのですがこの解法は今回は無視します.

解法

AtCoderの公式解説に書いてる,「最後の手から点数を出して考える」ことを使います.ボクはこの部分の理解に苦しみました.

ここからはボクなりの解釈なので間違っていたり他にわかりやすい方法があったら教えてください.
キーポイント

• 実際には全通り試している
• オレンジの番と青の番で取るべき行動が異なる

この記事では全部は書ききれないので最初の部分だけ行います.

青が左上に石を置いた場合下のような推移が考えられます.最後まで全部埋まった時に青の点数をカウントします.

そうすると上図のようになります石が3つ置いてある状態から石が4つに変化するのは選択肢が一通りしかないので必ず推移するので条件として判定には使いません.
石が2個置いてある状況から青がどちらに置いたら自分の点数が最大になるかを考える

まず始めに囲ってある部分に注目する.今回囲ったのは青の番なので点数が高い方が最善の置き方となる.なので30点の取り方は無視して34点の方を採用する.

青は点数を常に最大にしようとする.今のと同様のことを下でも行う.

下二つに注目する.今回も青番なので点数の高い24点の方を採用する.

もう一度行うと以下のようになる.

次はオレンジの番に注目する

オレンジの番なので点数が一番小さい24点を採用する.
これで終了!!
青が初手で左上に石を置いた場合に青,オレンジの両者が最善を尽くした場合の最高点を得られることができました.
青が初手で右上,左下,右下に石を置く場合も同じことをして最善はどれかを確かめれば答えを出すことができます.

AtCoderなどの競プロではもっと複雑な問題設定になっています.今回紹介した方法が使える場合に遭遇するかはわかりませんが,覚えておくといいことがあるかもしれません.今回はこんなイメージを持ちましたという紹介でコードには全く触れていませんが,意外と実装の方も大変かもしれません(頑張ってください).
以上です.ありがとうございました.

明日は.hosoeさんの記事です.お楽しみに~