AtCoder CADDi 2018 D - Harlequin
目次
結論
変数が多いときは,
の例を試してみる.
最適に行動する=相手がどんな行動をとったとしても,自分が勝てるように行動する
はじめに
想定読者
- 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.
筆者の実力
- AtCoderのレートで茶色.
記事の特徴
なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.
試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.
間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).
- 連絡先:@k_hiro1818
問題のリンク
発想・解法とそれらを引きだすための方法・解釈
考察のキモ(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 更新