107. AtCoder参加記録（AtCoder Beginner Contest 249）

16回参加でレート 1056 です。

そろそろパフォーマンス全部載せるのが厳しくなってきたので、今回分のみ。

今回はパフォーマンス 1204 です。

ABCDを通して、EGExは未解答です。Fは通せず。Dでとても痛い2ペナ。

各問題の感想など。

A

5分23秒。

いや、普通に難しすぎる。

入力が横に長過ぎて用意していたユーティリティでは間に合わなかったので、入力のパースから書いてました。そこからも割と難しくて、1秒ずつシミュレートして実装しました。歩く時間と休憩時間を足した剰余で今が歩く時間か判定する感じです。

B

3分25秒。

char 配列にバラして HashSet に突っ込み、長さが一致していることが必要条件。あとは大文字と小文字が両方含まれているか確認すればOK。

C

12分14秒。

問題文が意味不明で、何度考えても理解できなかったので書かれているとおりに実装することにしました。

好きな個数選ぶ → bit全探索

というわけで、ここから英小文字の種類ごとに Dictionary を作って $K$ 個登場した数を数えて最大値を出力。アルファベットの種類数を $A$ として $O(AN2^{N})$ で間に合いそうなのでこれでOK。問題文を考えている時間が無駄だった…。

D

初回提出25分41秒、最終提出41分0秒（2ペナ）。

今回の最悪ポイント。 $A_i = A_jA_k$ のような形で考えて、これを満たす組がいくつあるか、という問題にしました。重複ありなので数列の要素がそれぞれいくつ登場するのか、ということが重要になるのでそれを Dictionary で保持。ここから、要素の昇順に見ていって、 $A_j \times A_k$ を計算し、この答えが $\max A$ 以上であれば早々にループを抜けてよいです。

あんまり計算量を見積もれていなかったのですが、約数の少なさとループの早期脱出からたぶん間に合うでしょ、と提出。すると 1WA。全部 1 とか特殊ケースで引っかかってるのかな…といろいろ考えるも、手元のテストは全部合ってそう。よくよく見ると、計算途中で int 同士の掛け算になっている箇所があり、最悪ケースを考えると int では足りない値が出ることに気付き、ここを直すだけで通せました…。

ちなみに、一発で通せていればパフォ 1394 だったみたいです。悔しすぎる。