AtCoder Beginner Contest 172

2020-06-27

コンテスト中に挑戦した問題についての感想とか.

なお, 今回の結果はひどかった. 要反省.

A - Calc

まあ, さすがにそろそろA問題はやるだけ. でもちゃんと確認はしようとは思う.

多分, 他の言語だと浮動小数点数の問題などが有ると思うが, Common Lispはその辺り優秀なので, 書くだけ.

exptは整数, 自然数なら整数値が返ってくる.

制約から, 与えられた入力のうち違う文字の箇所を探せば良いだけということが分かる.

これについては, Aとは逆にCommon Lispならではの面倒臭さとして, tを変数名に使えないので注意.

貪欲法で出来るかなぁと思って, うまく行かず失敗した.

途中で累積和のことが頭に浮かんだが, 解答の様に使う方法は思い浮かばなかった.

Dもそうだけど, CとDは, 問題をどう読むかということが問われている気がする.

この問題も最終的な状態として, ２つのテーブルともに頭からある冊数(0冊含む)を選択するということに気付くことが一つ.

もう一つは, この時の計算量の問題. ２つのテーブルで総当りで考えると大変なことになるが,

から, テーブルAを0冊からn冊までなめながらBはm冊から0冊に下ると, Aでi冊でBのj冊まで調べたらAでi+1冊の時はBはj冊からスタートすれば良いことが分かる.

別の言い方をするとi冊, j冊の組で条件に合わなければ, i+1冊, j冊も条件に合わない.

これらを踏まえるとO(N+M)で計算できることが分かる.

Cに時間使いすぎて解けなかった. あとで解いたら出来た. 冷静になって考えるべきだったと思う.

Nまで一つづつ約数を調べていたら時間がかかり過ぎるので, 1からNまでの倍数になる数の方を考える. ただし, これもカウントしてしまうと間に合わない.

そこで, 2の倍数の和, 3の倍数の和の様に和を求めていく.

和は等差数列の和の公式で求まる.

これだと間に合う.