AtCoder Beginner Contest 111 - seriruの技術屋ブログ

AtCoder Beginner Contest111に参加しました。結果はA,Bの2完でした...悔しすぎる。しっかりわかったところまで解説します。

A AtCoder Beginner Contest 999

問題: 3桁の整数 $n$ が与えられる。1 と 9を書き換えて出力せよ。

$n$ を10で割ったあまりを0になるまで取り続け、それが1だったら9で、9だったら1で、出力させればよいです。

sample code:

問題: $N$ より大きいゾロ目の整数を出力せよ。

$N$ を111で割ったあまりを取り、それが0だったらそのまま出力、0でない場合は、Nを111で割った商 + 1 を111で掛けた数を出力すればよいです。(文章におこすとわかりづらい...)

sample code:

問題: 数列 $a_1, a_2, ... , a_n$ を以下の条件を満たすようにする最小の操作回数を求めよ。

1, $i = 1,2,...,n-2$ について $a_i = a_{i+2}$

2, 数列に現れる数はちょうど2種類

[tex: a_i = a{i+2}] より, [tex: a{i+1} = a_{i+3}] となります。

これより、数列の偶数成分と奇数成分の値を一致させればよいとわかります。

数字の書き換えは1回でできるので、数列の最頻値に書き換えるのが一番効率が良いです。

ここで注意することは、偶数成分の最頻値と奇数成分の最頻値が一致してしまう場合です。

この場合、2番目の条件を満たさなくなってしまうのでダメです。

したがって、答えを出すために以下のように場合分けをする必要があります。

偶数成分の最頻値を $e1$ , 奇数成分の最頻値を $o1$ とすると、

(i) e1 != o1の場合
(ii) e1 = o1の場合

にわけられます。

(i) e1 != o1の場合

このときは最頻値以外を数えて出力すればよいです。

(ii) e1 = o1の場合

偶数成分で次に多く登場する数をe2, 奇数成分で次に多く登場する数をo2とします。

e2 != o1 かつ o2 != e1 なので、

を数え上げて小さいほうを出力させればよいです。

また数列のすべてが同じ整数のときは最頻値が1つしか登場しません。

このときは e2, o2 に0を入れることで、片方の数列のすべての成分を数え上げることになります(出力例3も大丈夫ですね)。

sample code:

自分で実装すると、REやらWAやら大量に出て一向にACできなかったので様々なACコードを参考にさせていただきました...

配列を初期化すると、全ての成分が0になるんですね...

(pairのソートは第1成分が比較されます(らむだー使えば第2成分の比較にも昇順にも降順にもできます(私はわかりません...)))