読者です 読者をやめる 読者になる 読者になる

shaitan's blog

長文書きたいときに使う.

京大特色入試と聞いて、を読んで、を書いて

shaitan.hatenablog.com

問題の画像は新聞のなのでそのうち消えそうだと思って保存しとこうかと思ったけどぐぐったら書き写してる人見つけたのでいいや。
一応ざっと書いておくと、n個のコインを円周上に並べ、連続するk個をひっくり返す操作を行ってすべて表にすると終了、ってやつ。

問2と1は別解にするために無理やり変な解き方した感じなんだが、
2のほうでボツにしたアイデアも一応書いておこう。

【問2】
「図2が終了可能」⇔「図2に1回操作を行った110000が終了可能」。
必要な操作の最低回数が4回以上のとき、
M[i],M[i+3],M[j]を含む(jとiは3を法に合同でない)が、
これらの操作はM[j+3]と結果が同じなので、
それに変更するとより少ない回数で終了可能なので最小性に反する。
よって必要な操作の最低回数は3回以下。
110000だとひっくり返す総数が偶数回であることが必要なので終了可能ならば2回でできる。
ここで1回操作するのは6通りあるがこれらいずれも残り1回で終了可能でないので不適。