AtCoder CADDi 2018 D - Harlequin

目次

結論

• 変数が多いときは，の例を試してみる．

• 最適に行動する=相手がどんな行動をとったとしても，自分が勝てるように行動する

はじめに

• AtCoderで出題された問題を復習しています．

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

想定読者

• 解説を読んで解き方はわかったものの，なぜその方法を思いつけるのか？と思った方．

筆者の実力

• AtCoderのレートで茶色．

記事の特徴

• なぜその発想に至ったのか，どうしたら解法を詰められるかといった点について，筆者なりの解釈をつづります．

• 試行錯誤した過程から，得られた前提知識や着眼点を言語化していきます．

• 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．

  • 連絡先：@k_hiro1818

問題のリンク

D - Harlequin (500点)

発想・解法とそれらを引きだすための方法・解釈

考察のキモ（Key Insight）は?

• 数列に一つでも奇数が含まれているなら，先手が勝つ．

• 自分の手番のときに，奇数の要素をすべて選択して，相手に偶数の要素を押し付ける．

どうしたら思いつけそうか?

• ゲームの決着がついた状態から，逆算していく．

• を例に実験する．

• a1, a2とする．二次元の表を用意して，勝敗を書き込む．

  • プレーヤーの手番が来たときの勝敗を判定する．先手の手番のときに，2つとも0なら負け．

  • 表の更新方法：あるマスに着目したときに，直前の手番（表の上・斜め上・左）で負けが含まれていれば勝つ，そうでなければ負ける．

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]

    for ai in a:
        if ai % 2 == 1:
            print('first')
            exit()

    print('second')


if __name__ == '__main__':
    main()

得られた知識・知見

• 最適に行動する=相手がどんな行動をとったとしても，自分が勝てるように行動する

• 変数が多いときはの例で実験する．

• 勝敗の条件をシステマティックに判定する．

感想

• 愚直な実験から直感的には，偶数のみとそれ以外に分岐するとは気がつけた点が成長していると思います．

• の場合はどうなるのだろうと思ってしまいました．

• 直感に頼りすぎており，証明できるようになりたいです（ジャッジ画面で祈る状態になってしまうため）．

参考

• 公式解説

• 公式解説放送

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

更新履歴

• 2019/06/27 作成
• 2019/0x/xx 更新