AtCoder Beginner Contest221に参加しました。
結果
A,B,C,D問題の4問正解でパフォーマンスが1308でした。 D問題が割と早く解けたおかげでパフォーマンスが良かった！ E問題はあと少し時間があればAC解けそうな気がした。後でできなかった部分を実装して提出しておこう。
A - Seismic magnitude scales
問題文のとおりに計算する。
AとBの差をxとするとを計算するだけ。
B - typo
色々やり方はありそうな問題。
SとTを先頭からチェックしていき一致していない場所が何箇所あるかを数えて、 0のときYes。1のときNo。3以上のときNo。として処理終了。 2のときは、最初に一致していない場所をxとしたときS[i]とT[i+1],S[i+1]とT[i]が一致することを確認する。 一致するならYes,一致しないならNoを出力させる。
C - Select Mul
制約を見るとNは以下なので9桁程度の整数。つまり最大で9つの整数を2つに分けて数字を作って積の最大値を求めれば良い。
bit全探索とかでNの数字を2つに分けて、各グループの中でソートとかグループ内の数字だけで作れる最大の整数を作る。その後、作った2つの数の積を計算して最大値を更新していく。
D - Online games
ログインユーザーの累積和を計算して、各kに対してログイン人数がk人の日が何日あるかを数えて出力する。
最初は累積和をimos法で計算しようとしたけど、A,Bの最大値がなのでimos法で各日にちに対して線形に処理しているとTLEする気がしたので解き方を考え直した。
プレイヤー数Nに対してA、Bが十分大きいのでもしもの配列で累積和を計算したとしてもほとんど値の変化がなくて無駄が多そう。なので
日に人が増えた、
に人が減ったというイベントドリブンでシミュレートすることにした。何人の状態が何日間続いたかをイベントの度に計算して記録していき、最後に各k毎に出力する。
E - LEQ
もう少し時間があれば解けそうな問題だった。
に何番目のAを持ってくるのかを決めればA'に含められるAの候補が何個あるのか決められる。Aの候補がx個あったとすると
通りのA'が作れることになるので、
が
の場合から
の場合まで順番に計算すれば解けそう。
が
の時A'に含められるAが何個あるのかを事前に計算しておくとかして簡単に取得できるようにすれば、たぶんTLEせずに解けると思う。
