AtCoder Beginner Contest 276に参加しました。

結果

A,B,C,D問題の4問正解でした。E問題がちょっと上手い方法を思いつかなかった… 何も考えずに幅優先探索とは深さ優先探索をするとTLEになりそうだったので他の方法を色々考えてみたけどいけそうな方法が思いつかなかった。

A - Rightmost

問題文の通りに処理して結果を出力する問題。

ちょっとだけ工夫して、文字列の後ろからaを探していき、1番後ろのaが後ろから何文字目なのかと文字列全体の文字数をもとに、文字列最後のaが先頭から何文字目かを計算して出力した。

与えられる文字列が高々100文字程度なので大人しく先頭から探索していくので十分だとは思う。

B - Adjacency List

setの配列を使えば簡単に処理できる問題。

道路の元に対応するsetへ道路の先の都市を入れていけば、setのサイズ=都市iと道路で直接結ばれた都市の数になり、setの先頭から順番に要素を出力すれば昇順になっている都市の番号となる。

setを使わないならたぶん配列で処理することになるけど、重複の考慮とソートするっていう処理が入ると思う。 B問題なら多分TLEになることはないとは思う。データ構造を工夫してシステム側に処理を任せられる部分は丸投げにしたほうが心配することが少なくて気が楽だけど。

C - Previous Permutation

Nが最大で100と小さいので $N ^ {3}$ の解法でも間に合うかなと思って1回愚直に解いてみた。（TLEだったけど。）

１～Nまでを順番に追加した配列を用意して1個前の配列を保存しながらPと完全一致するまでnext_permutationを繰り返し、完全一致したときに保存しておいた1個前の配列の中身を出力した。

計算量的に大丈夫だと思って愚直に解くとTLEだったので他の方法を考えてみたけど、少し調べたらprev_permutationという関数が見つかった。辞書順で1個前の順列を取得できるらしいのでPに対してprev_permutationを実行して結果を順番に出力した。

$a _ {i}$ を $2 ^ {x} \times 3 ^ {y} \times X$ と言う形式で表したときにすべての $a _ {i}$ に対してXが同じなら $a _ {1} = a _ {2} =...=a _ {N}$ を満たす状態にできると言える。ただ、答えは必要な操作の最小回数なので全部Xになるまで操作を行うと、本来は操作しなくても良かった操作を何回か行ったことになるかもしれない。