AtCoder Regular Contest #014
AtCoder Regular Contest #014というものに参加しました。プログラミングコンテスト初参加でしたけど楽しめました。
僕が提出した答案はこちら: http://arc014.contest.atcoder.jp/submissions/all?user_screen_name=oupo
A問題とB問題はクリアして、C問題はナイーブな解法で部分点をもらいました。D問題は時間内に解けず、開催時間終了後に提出しました。400点満点で230点です。
4問中2問はプログラミングの基礎知識があれば誰でも解ける問題だったり、UIがシンプルでわかりやすかったりなど初心者への配慮が行き届いているなーという印象を受けました。これなら続けられそうです。あと、問題文にユーモアがあるのがいいですよね。
なお、AtCoderをやってみようという気になったきっかけはこちらの記事です。良い記事ですよ！:
問題C
C: 魂の還る場所 - AtCoder Regular Contest 014 | AtCoder
一次元のぷよぷよ的問題。
各色の個数のmod 2の和が答えになるということですが、解けませんでした＞＜
証明を書いてみる。
ボールを入れていくどの段階においても筒に同じ色のボールは2つ以上ないというような入れ方が存在する
ボールを入れていくどの段階においても筒に同じ色のボールは2つ以上ない、という性質をPとしよう。
Pを満たす入れ方が存在することを与えられるボールの個数に関する帰納法で示す。
与えられるボールの列を一つ固定し、個数をNとする。
このとき、最後の一つのボールを除いたN-1個のボールの列に関する性質Pを満たす入れ方を一つとって固定する (帰納法の仮定により)。
この入れ方をし終わったときの状況を考え、ここへ今考えているN個のボールのうちの最後のボールを入れたい。
入れようとしているボールと同じ色が、この状況の筒になければ、このボールを左右どちらから入れても性質Pを満たす入れ方となり証明は終わる。
入れようとしているボールと同じ色が筒の端にあれば、その側へこのボールを入れれば、性質Pを満たす入れ方になりこの場合も証明は終わる。
それ以外の場合、筒は色の互いに異なる3個のボールからなっていて、真ん中が入れようとしているボールの色である。
仮に今入れようとしているボールの色をG、筒の中の状況をRGBとしよう。
今固定している入れ方において、最後の操作の直前でも、同じ色のボールは2つ以上ないという性質が成立している。よって、最後の操作ではボールは消えていない。
つまり、最後の操作ではRを左から入れたかBを右から入れたかのどちらかである。どちらにしても入れる方向を反対に直せばGが端に来るようになる。ここにGを入れれば、今考えているN個のボール列に関する性質Pを満たす入れ方になる。
□
「与えられたボールの各色の個数のmod 2の和」が答えに、すなわち入れ終わった後の筒の中のボールの数の最小になる
ボールが消えるときには必ず同じ色のボールが2つ消える。よって、どんな入れ方でも結果の筒と与えられたボール列との間で、各色の個数の偶奇は一致する。
上の補題から、結果の各色の個数が1以下になる入れ方が存在する。
ところが偶奇の一致によって、そのような入れ方の結果は次の形に限られる。
筒の中の色Rのボールの数 = (与えられた色Rのボールの個数 mod 2)
筒の中の色Gのボールの数 = (与えられた色Gのボールの個数 mod 2)
筒の中の色Bのボールの数 = (与えられた色Bのボールの個数 mod 2)
このとき、筒の中のボールの数は、「与えられたボールの各色の個数のmod 2の和」となり、偶奇の一致によりこれが最小値であるとわかる。
□
