思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder いろはちゃんコンテスト Day3 F - 闇のカードゲーム

f:id:hiro_kato:20190502211424j:plain

目次

はじめに

  • AtCoderの問題を復習しています.
  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います.

想定読者

  • 筆者と同じくらいのレートの方:失敗談・回り道をみて,共感していただける部分もあるかもしれません.

  • コンテストのwriterの方:サンプル n=1ではありますが,レート茶色上位~緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません.

記事の狙い

  • 丁寧でわかりやすい解説記事がたくさん公開されているため,解法そのものについての記述は少ないと思います.

  • ACに至るまでにどうしてそのような発想に至ったのか,考察や実装で試行錯誤した過程(=失敗談や回り道)を重視しています.

  • また,得られた前提知識や着眼点について,今後応用できるように抽象化・言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

F - 闇のカードゲーム (100点)

ACに至るまでの考察・実装のコツなど

  • サンプル2から逆算した(こんな考察でいいのか不安です).
  • 制約条件からカードをどのように2枚残したらいいか,組み合わせを列挙してみた.

f:id:hiro_kato:20190502230753j:plain
サンプル2を使った考察のイメージ

考察

  • 図の例では,中央のカードを挟んで,すぬけ君もいろはちゃんも両側からカードを取るかたちになっている.
  • ただし,いろはちゃんの行動次第では,左側もしくは右側だけのカードを選択するケースもある.
  • どのカードを除去するかという視点から,どのカードを残すかという視点を思い出す.
  • 左側,右側のカードのそれぞれの束から1枚ずつカードを取ることになりそうだという仮定を置いた.
  • 左側と右側のカードの束をそれぞれ左端から順にみていき,2枚のカードの差の絶対値が最小となる値を調べる.

実装

  • 配列の添字でバグを埋め込みそうだったため,中央のカードを含まないように2つのリストに分解.
  • zip()関数を使って,2つのリストを同時に全探索.

提出コード

試行錯誤した過程

  • すぬけ君は,制約条件から並べられたカードの真ん中を選ぶ.スコアは,並んだカードの両端の絶対値の差.

    • サンプル1が該当.

  • カードが5枚以上となったときは,いろはちゃんの行動が影響する.

    • いろはちゃんが左端のカードを選択したときは,すぬけ君は最初のカードから見て右側のカード選択をする.
    • いろはちゃんが右端のカードを選択したときは,すぬけ君は最初のカードから見て左側のカード選択をする.
    • 回答に向けてどうすればよいか,ここで詰まる.

得られた知識・知見

  • ターン制のゲームで最適化を図る問題では,最後の結果から逆算するとうまくいくケースもあるかもしれない(要検証).
  • 多数の要素を選択して取り除く→少ない要素を残すという視点の転換.

感想

  • サンプルから逆算するような過学習っぽい解き方から卒業したいところです.
  • 仮定を置いた部分が確証が持てず,ジャッジの前でお祈りしていたところありました.
  • 解法が全く思い浮かばなかったところから,本番中になんとかACできたのはよかったです.

課題

  • 解説PDFを読んで復習する.
  • 仮定や要検証部分を更新する.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.