AtCoder Beginner Contest 120 感想
AtCoder Beginner Contest 120 に参加しました。
結果は ABC 3完、順位は 753 位でした。
B - K-th Common Divisor
正整数 A,B が与えられる。A,B ともに割り切ることができる正整数のうち、K 番目に大きいものを求めよ、という問題。
A も B も割り切ることができる正整数を全て列挙して、List に詰めていきます。
列挙する範囲は 1～min(A, B) です。
列挙が終わったら、リストの後ろから k 番目の値を取り出します。
list.get(list.size()-k) とすれば OK です。
C - Unification
S,T からなる文字列から ST を消していくという、似た問題があったような気がしますね、解いてはいませんけど。
さてこの問題ですが、
・"01" もしくは "10" の並びを消すことができる
・消した後は、文字列を詰める
・最大で何文字消せるか？
というものです。結論から言えば、
・文字列の長さ - Math.abs(0の個数 - 1の個数)
が答えになります。コンテスト中は「理由はわからないけどこれが答えなんじゃないの」と投げやりな気持ちで提出したら、なんと通ってしまって、しばらく唖然としていました。ということで、なぜこれが答えになるのか、理由を考えてみます。
答えによれば、0 の個数と 1 の個数に差があるとき、文字が残ります。
逆に、0 の個数と 1 の個数が同じなら、文字の並びに関係なく、文字列を完全に消せるということになります。
仮に、同じ個数の 0 と 1 から、 完全に消すことはできない文字列を作ることを考えてみます。
このことの不可能をもって、答えが答えである理由とすることにします。
4個の 0 、4個の 1 から文字列を作ります。0 をまず最初に置きます。
・0
次にこの 0 の左右に 0,1 を置きますが、1 を置くと文字列が消えてしまいます。したがって、0 を置きます。
・00
以上の手順を手持ちの 0 がなくなるまで繰り返します。
・0000
0 はもう持っていないので、1 を置くしかありません。どの位置に 1 を置いても、文字列から 0 が1つ消えてしまいます。
・000
以上の手順を手持ちの 1 がなくなるまで繰り返すと、最後には文字列はなくなってしまいます。
1 を最初に置いた場合も同様の結果になります。
よって、同じ個数の 0,1 から完全に消すことができない文字列を作ることは不可能です。
したがって、0 の個数と 1 の個数の差を文字列の長さから引いたものが答えになります。
追記：もっとスマートな証明方法があるみたいです、以下に記します
・文字列内に 0,1 がともに存在しているなら、0,1 が接している部分が必ず存在する
・そのような部分が存在するなら、0,1 の数は1ずつ減る
・0,1 のどちらかが無くなるまで、0,1 の数は減り続ける
・合計で min(0の個数, 1の個数)回 、0,1 の数が減る
・取り除かれる文字の個数は 2 * min(0の個数, 1の個数) 個
総括
C問題を解けたけれど、なんだか腑に落ちない感じです。というか、解いた気がしません。
ひらめき系の問題ではなく、D問題のグラフのような、典型問題をしっかりと解けるようになりたいですね。
