117. AtCoder参加記録（AtCoder Beginner Contest 254）
22回参加でレート 1225 です。
今回はパフォーマンス 1254 です。
ABCEを通して、FGExは未解答です。DはTLE、Eで1ペナ。
各問題の感想など。
A
1分16秒。
ゼロ埋め出力の方法をググるのが面倒だったので、string で取って出力しました。
B
4分36秒。
見た目難しいですが、書いてある通りに実装すればよいです。
C
8分42秒。
発想でしかない問題。Cにしては難しくない…？と思いましたが、通してる人数を見るとそうでもなさそうでした。
バブルソートみたいな処理ができるのですが、観察すると入れ替えられるのはインデックスを で割った余りが等しい箇所のみだと分かります。逆に、そのような箇所であればバブルソートと同じ操作なので、自由に入れ替えられます。
よって、まず昇順ソートして各要素が の剰余インデックスに何個あるかカウントした後、元々の数列の剰余インデックスを求めて先ほど求めた数を引いていき、上手くいかない箇所があれば No、最後まで上手く行けば Yes となります。
最初のソートがボトルネックで、計算量は 。
D
最初の提出まで34分7秒。
難しい…。色々やりましたが、結局 TLE は取れませんでした。早く E へ行くべきでした。
E
初回提出23分21秒、そこからACまで2分19秒。
制約に「与えられるグラフの各頂点の次数は 3 以下」「」という非常に怪しいものがあるので、これに注意します。
入力例の図を書いて考えてみます。 なので、ある頂点から距離 3 以内の頂点のみ見ればよいです。これは幅優先探索をすればよいだけです。各頂点の次数は 3 以下なので、高々 39 本の辺しか見ることはないです（
）。ということは、すべての頂点についてこの操作を行っても
の計算量となり、間に合いそうです。
ただ、若干定数倍が重そうなので念のため実行時間制限を見ると、やや長めになっています。つまりこれが想定解っぽいです。
というわけで、予め各頂点について距離 3 までの頂点番号の総和を求めておき、クエリが来たらここから で返答することにしました。
初回提出は距離 3 で幅優先探索を打ち切るのを忘れていて、メモ用配列の範囲外アクセスで RE でした。
F, G, Ex
見てないです。
今日はなんだか心がざわついており、あまり集中できない回でした。全体的に難しかったということもありますが…。
Dに固執してしまったのが最大の反省点。詰まったときにEも少し見ていたのですが、チラ見したときは の制約に気付いていなくて「こんなのどうやれば良いんだ」となっていました…。早く D を切るべきだった。
前回がたまたま簡単だっただけで、今回は最近の難易度が戻ってきたなー、という感想でした。次の目標は青パフォ安定ですが、まだまだ遠そうです。
