AtCoder Beginner Contest 174
2020-08-03
コンテスト中に挑戦した問題についての感想とか.
結果, 初めて緑になりました. しかし, Dに時間かけすぎたことと, E解けなかったことが心残り.
A - Air Conditioner
比較演算子の使い方を覚えましょう. 問題分を読んで端点が含まれるかどうかはしっかり確認しましょう.
B - Distance
数えましょう. 平方根の計算は誤差が生じることがあるのでこの問題のような条件では, 二乗和と二乗の比較にすると良い.
C - Repsept
順に計算していくだけ. 上限は, 数学的考察によって求まる. (私コンテスト中には分かってなかった.)
オイラーの定理を参照.
大きな数の剰余は大変なので、剰余を求めながら進むと良い.
D - Alter Altar
コンテスト中は, いろいろ考えて時間を使ってしまった.
最終的に左側にRが右側にWが並ぶと良いので, Rの数をxとすると左端からxこの中にあるWを左端からX+1個目以降のRと入れ替えるという操作が最少ステップとなる.
うまく走査すると一回の走査(読み込み時にそれまでのW出現数を保存した配列の作成とRの数を数えるを行う)と配列アクセスで答えが出る.
2回走査するなどで求めても間に合う.
E - Logs
二分探索で求まることに気づかなかった.
最大の丸太の長さをXにするにはL回必要を求めるという問題の読み替えで解ける.
この手の問題の読み替えをきっちりこなしていきたい.