エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）の感想
エイシングプログラミングコンテスト2021に参加してきました！結果はA,B,Cの3完でしたが、低難易度の問題に時間をかけてしまいパフォーマンスは449。再び借金生活に逆戻りです；；以下簡単にコメントしていきます。
A - Three Dice
3つのサイコロを投げたとき、サイコロの裏面の数の総和を求めよという問題。
サイコロには対面の数の和が常に７になる性質があるので、サイコロの目をa,b,cとすると、(7-a)+(7-b)+(7-b)を計算して終了。
特に詰まることはなく1分ちょいで提出。いい感じ。
B - 180°
与えられる文字列を180度反転させよという問題。
入力される数字を後ろから順に選んできて、操作に書いてある通りの変換をif文で行って終了。
基本的な文法が分かっているかのチェック問題に５分かけるのはちょっとダメかも。
C - Made Up
長さNの数列A,B,Cが与えられたとき、Ai=BCjを満たす( i , j )の組を求めよという問題。
まずiとjを全探索する方針が簡単そうだけど制約が10^5なので間に合わなそう(O(N^2)となるため)。これは工夫して全探索のパターンだと思い典型90問を思い出してみると、変数が複数存在するように見えても実は1つの変数に注目するだけで解けるケースがあったなーと気づいた。そこで今回はiに対して全探索を行う方針を取ることにした。
今回は条件が複雑そうな数列Bに注目してみた。iが定まると
- B[i]の数
- 数列Cのうち、i (index)を指定する項数（＝C[j]の項数）
- 数列Aのうち、B[i]を指定する項数(＝A[i]の項数)
の３つを得ることができる。下2つはそれぞれA.count(B[i]) C.count( i )で求められるのでこの積をとってAC！！
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
O(N)なのでTLEにはならないと思ってたんだけどこの方針間違ってた？？？なんて思って迷走していたら、
for文の内側でのカウントが原因でした。for文の外側で collectionsのCounterを用いて前もって計算を済ませて置き、for文の中では掛け算するだけに変更したら無事AC。
ここまで46分。PythonとPyPyでそれぞれ誤答を投げてしまったので計2ペナで合計56分です・・・。
D - aab aba baa
A個のaとB個のbを並び替えてできる文字列のうち、辞書順でK番目のものを求めよという問題。
制約が小さければ中高の入試で出題されてもおかしくない重複順列の典型問題。基本方針は文字列を左から決めていき、一番左の文字がaの時に後ろに来る文字列のパターン数がKより大きければaで確定される。そうでなければbが一番左の文字となる。これを文末まで繰り返していけば解けそう。
問題に取り組んで5分ほどでこの方針に行きついてサンプル１は合わせられたものの、サンプル２が全く合わせられずにコンテスト終了。
公式解説はDPによる実装でしたが、ユーザー解説は同じ方針を取っていたのであとは実装力ですね。
まとめ
前回のようなD問題で手も足もでないような状況ではなかったので、あまり感触は悪くありませんでした！（パフォはあまり出ていませんが💦）それにしても今回のC問題はあまりに多くの人が解いててびっくりしましたね。Bまではそこそこのペースで解けていたせいもあり、やっとのことでCをACしたもののほとんど順位が上がらなくてちょっと悲しかったです・・・。
