AtCoder Regular Contest 103 - 情報妖精の競プロ日記

AtCoder Regular Contest 103に参加しました！
AtCoder Beginner Contest 111 beta版
 AtCoder Regular Contest 103 旧版
 AtCoder Regular Contest 103 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 111 / Regular Contest 103
rated 1200 / 2800
9/29(土) 21:00 ～ 22:40 (100分)
100-200-300-600(300)-700-900 (6問)
ペナルティ: 5分

方針

CdEの3完、あるいはCDEが理想と言えるかもだけど問題を見てから判断。
構築問題とかなら得意なので、そっちを優先させたい(DとEが両方構築問題ならD優先……？)

A - AtCoder Beginner Contest 999

各桁を弄る問題の時は、文字列で処理した方が楽です。
その時、各桁についての操作は各文字を操作することになります。
後は、その文字が'1'なら'9'に、'9'なら'1'にすれば正解となります。

B - AtCoder Beginner Contest 111

まず、制約より $N$ は3桁であることが保証され、 $999$ は出力条件を満たすので答えは必ず3桁になります。
また、答えは必ず $111$ の倍数です。
よって、 $111$ の倍数を小さい方から見ていき、 $N$ 以上になったらそれを出力すれば良いです。

C - /\/\/\/

これ、問題としては結構難しい方ですね……。
まず、 $i$ が奇数か偶数かで分けて、それぞれについて各数字の出現回数を求めます。
これはmapなどを使うと導出できます。
次に、奇数と偶数のそれぞれについて最も出現した値とその回数、および2番目に多く出現した値とその回数を求めます。
この時、まず奇数と偶数で最大に出現した値が一致しないなら、答えは $N$ からそれぞれの出現回数を引いたものになります。
問題は同値になる時で、この場合はどちらかを2番目に多く出現した数の方にしなければいけません。
これは奇数を1番目で偶数を2番目にしたときの数と奇数を2番目で偶数を1番目にしたときの数を比較し、より大きい方を $N$ から引くようにすれば良いでしょう。

D - Robot Arms

まず、構築可能かどうかの判定をしましょう。
可能かどうかの判定は $m \leq 40$ はいったん忘れて、長さ1の腕を沢山用意することを考えます。
この時、全ての座標の偶奇が一致するならば、これは可能です。(アームを1回折りたたむと2マス縮むので)
逆に、偶奇が一致しないならばこれは不可能っぽいです。実際、各アームはどっちの方向に動かしても偶奇は同じになるので、これは不可能です。
次に、実際の構築手順を考えていきましょう。
まず、制約条件 $m \leq 40$ 、 $1 \leq d_i \leq 10^{12}$ のあたりから、 $1, 2, ..., 2^{m-1}$ の腕を用意すれば良いのではないかと予想できます。
これの動かす範囲を考えていくと、原点から奇数の範囲にある任意の座標に移動できることが分かります。
後は実際に計算する方法ですが、長い腕から順に貪欲に目的の座標に近づくように組み立てていくと辿り着けます。
なお、全ての座標が原点から偶数の範囲にある時は、最初にアームをどちらかの方向に1伸ばすなどしてずらしておきましょう。
この場合でも、 $10^9 \leq 2^{30}$ より腕の本数には余裕があるので問題は無いです。

E - Tr/ee

まず、サイズ $i$ の連結成分を作った時もう片側は $n-i$ の連結成分になることから、各 $i$ について $s$ の $i$ 番目と $n-i$ 番目の文字が一致しないなら構築不可能です。
また、木の性質上ある辺を切った時になお連結成分が $n$ であることは不可能なので、これが'1'の場合も構築不可能です。
また、葉の無い木は存在しないので、 $1$ 番目の文字が'1'でない時も構築不可能ですね。
さて、残りの場合を考えます。
まず、 $\lceil \frac{n}{2} \rceil$ 以上の連結成分については考えなくても大丈夫なので、半分で考えましょう。
ここで、まず連結成分が一つ……すなわち $1$ と $n-1$ のみ作れば良い場合、これは簡単です。
1番目の頂点に残りの全ての頂点を繋げてしまえば良いのです。
では、作らなければいけない連結成分が $a_1, a_2, \cdots, a_m (a_1 < a_2 < \cdots < a_m)$ だったらどうすれば良いでしょうか？
ここで、まず簡単のために2個の場合、 $a_1, a_2$ について考えます。
これは、ある頂点に $a_1 - 1$ 個の頂点を繋げたものとある頂点に $a_2 - a_1 - 1$ 個の頂点を繋げたものの2つを用意し、それぞれを繋げれば良いです。
同様にして3個以上の場合も解くことができます。

F - Distance Sums

まず、 $D_i$ をソートして考えても良さそうなのでソートして考えます。後で復元する必要があるのでちゃんと元の座標の保存を忘れずに。
さて、サンプルを見ながら枝の繋がり方を考えます。
そうすると、葉の枝から繋がる頂点は全て自身から $N-2$ だけ引いた値であることが分かります。実際、これは常に成り立ちます。
また、同様に自身の下に $m$ 個の頂点を持つ頂点は、自身から $N-2(m+1)$ だけ引いた頂点に繋がっています。
これは、値を大きい方から順に確定させれば良さそうですね。
各頂点について、自身がつながる先は二分探索などで ${\rm O}(\log (N))$ で求めることができます。
また、自身の下にある頂点数は毎回辺を引くたびに辺の先に頂点数を渡してあげれば ${\rm O}(1)$ です。
これで、最後まで構築できれば無事にできました。