AtCoder Beginner Contest 409
こんにちは。
先日のABC409は不参加でした。
後日unratedでバーチャル参加し、ABCDEの5完（88分4ペナ）でした。
predictorによると1108パフォで少し負けてたらしいです。
今回はA~Eまでの感想を述べていきます。
A - Conflict
左から順に$T_i$と$A_i$がoで一致するかどうかを確認します。
oで一致している、という条件がなくてもサンプルが通ってしまうのがいやらしいですね。（１ペナ）
B - Citation
これは$A_i≦10^9$という制約に惑わされましたが、$N≦100$のため$x$は高々$100$ですので$x=0,1,\cdots, N$を全探索すれば良いだけでしたね（$101$回以上の要素が現れることはありえないため）。
あらかじめ$0,1,\cdots, N$までの数値が現れる回数を配列に格納し、$N$を超える要素は$cnt$に$+1$して数えておきます。
そうすれば、あとは$x=N,\cdots,0$まで順に$x$以上の要素の個数を得ることができるため、条件を満たした状態で即座に出力することによってACすることができます。（３ペナ）
function Main(input) {
input = input.split("\n").map((line) => line.trim());
const N = Number(input[0]);
const A = input[1].split(" ").map(Number);
const freq = new Array(N + 1).fill(0);
let cnt = 0;
for (let i = 0; i < N; i++) {
if (A[i] <= N) freq[A[i]]++;
else cnt++;
}
let ans = 0;
for (let i = N; i >= 0; i--) {
cnt += freq[i];
if (cnt >= i) return console.log(i);
}
console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));
C - Equilateral Triangle
円周上の点$a,b,c(a<b<c)$を頂点とする図形が正三角形をなすとき、線分$(a,b),(b,c),(c,a)$は等間隔となっています。すなわち、$a,b,c$が公差$L/3$の等差数列であるような組を求めればよいわけです。
なお、$a,b,c$は円周上の点なので$L$を法とする座標で考える必要があることに注意が必要です。
また、$L$が$3$で割り切れないときは正三角形となるような組はないので即座に$0$を出力します。（私は全ての辺を$3$倍して考えました）
D - String Rotation
辞書順に最も小さくなるように$l,r$を選択する方法として、まず$l$は$S_i>S_{i+1}$（不等号は辞書順を表すことにします）を満たすような最初の$i$を選べば良さそうです。
ここで、ccccbのように同じ文字が連続する場合にどうなるのか悩みましたが、$r$を一番右の位置とすれば、$S_i=S_{i+1}$となる位置でも、$S_i<S_{i+1}$となる位置でも、結局cccbcとなり変わりがありません。
次に、$r$の選び方ですが、これは$l>r$で初めて$S_l<S_{i+1}$となる位置を良さそうです。$S_{i+1}$を左にシフトするより、$S_l$をそこに入れた方が辞書順に小さくなるからです。
少し頭を使いますが、アルゴリズム的にはそこまで難しくないので茶色妥当でしょうか。
E - Pair Annihilation
これは難問でした。
処理自体は単純なdfsでしたが、dfsで良いと判断するのが難しいと思います。
dfsで良い理由ですが、葉っぱにある(陽)電子は親方向にしか移動できないためです。
葉っぱにある(陽)電子を親方向に移動させて、その親で対消滅できるものは消して、残った(陽)電子をその部分木のさらに親に伝播させる、、、という再帰的な処理をすることで最も効率よく(陽)電子を動かすことができます。
わかれば単純かもしれませんが、これが1000diffないというのは結構意外な気がします。
まとめ
今回はunrated参加のため解説があまりない感想回でした。
今月は仕事とプライベートが忙しすぎて全く精進できていません。
見ての通りprogress chartがスカスカです。
競プロだけじゃなく、もっと業務寄りの知識も得たいので本当に時間が足りないです。
社会人は大変ですね（泣）
今日はrated参加できそうなので、ぜひ頑張りたいと思います。
よ