エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）参戦記

はじめに

2021年5月22日21:00-22:40に開催された表題のコンテストに参加しました。
結果は，64分42秒3完　5189位／8714位　パフォーマンス410でレーティングは前回902から-41の861となりました。

f:id:chacoder:20210523084705p:plain

A問題

サイコロを３回振り，出た目の反対側の目の合計を出力する問題です。
1分05秒で提出。

B問題

B - 180°

０，１，６，８，９からなる文字列を１８０度反転させて出力する問題です。
3分55秒　通算5分00秒で提出。
ここまでは順調でした。

C問題

C - Made Up

問題文を理解するのにちょっと手間取りました。
愚直にやるとTLEしそうなので，どう計算量を落とすか悩みましたが，少し悩んで思いつかなかったので，先にD問題以降をやろうと思い飛ばしました。

D問題

D - aab aba baa

A個の a と B個の b からなる長さ A+Bの文字列のうち、辞書順で K番目のものを求める問題です。
これもまともにやるとオーバーフローもしくはTLEしそうだったのでO（１）解法を探すべく小さめのABで少し実験しましたが法則性を思いつけず。飛ばしてＥ問題へ。

E問題

E - Count Descendants

最近力を入れて勉強しているグラフ問題だったのでこの問題に賭けました（賭けに負けました）。
最短パスがDiである頂点の出力はDFSで容易にできましたが，根への最短パス上にUiが存在することをO（１）で求める部分に失敗しました。

最初に考えたのは，ある頂点までに通ってきた頂点を頂点毎に配列で保持する方法ですが，これだと根への最短パス上にUiが存在することを判別するのに各頂点毎にO（N）を要し，Nもクエリ―も１０＾５なのでTLE必至です。

次にある頂点までに通ってきた頂点をmapのベクターで保持する方法を考えましたが，これが意外に難しくうまく実装できませんでした。うまく実装できていればO（N）・O（logN）で間に合っていたつもりです。

だいぶ苦闘しましたが結局解ききれず。

途中で順位表見るとC問題がけっこう解かれているので，せめてC問題だけでも解いておこうと思い，C問題を解きました。見返してみると配列BCだけをつかった前計算をしておけばよいことに気づきました。飛ばさずに解いていたら１０～１５分くらいだったでしょうか。ぎりぎりパフォ８００ぐらいのラインで，いずれにしても冷えていました。