ABC174参加記
参加してきました。 全完84分 + 35分(7ペナ)でした。コンテスト中の思考とかを残しておきます。
A - Air Conditioner
https://atcoder.jp/contests/abc174/tasks/abc174_a
言われたとおりにif文書きます。
B - Distance
https://atcoder.jp/contests/abc174/tasks/abc174_b
言われたとおりにdの条件で判定しようとすると多分誤差で死ぬ（ちょびっとだけ足したりするとうまくいくと思います）ので、両辺2乗して
d^2 <= p^2 + q^2
を判定すればよいです。
C - Repsept
https://atcoder.jp/contests/abc174/tasks/abc174_c
剰余をとった時は余りを掛けたりしても大丈夫みたいな話。この数列は、前の項に10を掛けて7を足せばよくて、計算する度にmod kを取って、0になったタイミングで出力すればよいです。k <= 10^6なので、106回調べてmod kが1度も0にならないならどこかでループが始まってしまっているので-1になります。
D - Alter Altar
https://atcoder.jp/contests/abc174/tasks/abc174_d
石の色変えてる暇あったら、実質2個変えているのと同じ入れ替えをした方がいいなと思った。最終形はRRRRWWWWみたいな形。
左から進めるものと右から進めるものを準備して、左がW、右がRになったら適宜入れ替えていくと完成します。何かを勘違いして左右半分までしか探索しなくて全然通らず3ペナ。先にEを通して頭を冷やしたおかげでなんとか救われた感。普通に入れ替えるべき場所が右半分同士になることも左半分同士になることもありますね……
E - Logs
https://atcoder.jp/contests/abc174/tasks/abc174_e
蟻本で似たやつ見た！
蟻本ではk本の木材を作る場合に取れる最大の長さだった気がしますが、この問題もほぼ同じことです。全部がx以下になるように切ろうとした時、全部xの長さを切り出すような切り方でk回以内のカットで収まっているなら条件を満たせ、かつこの切り方がカット数を減らす観点からすれば最適になります。
あとは素直に二分探索をして、最大でどれくらいの長さの丸太がこの条件で切れるかを調べ、切り上げて答えにします。誤差周りで色々やろうとして2ペナ。
F - Range Set Query
https://atcoder.jp/contests/abc174/tasks/abc174_f
とりあえずざっくりこの2つの方針が思い浮かびます。前者だとしゃくとり？スライド最小値？うーんなんかうまく行かないような…となり、後者の方へ。
後者だと、例えば同じ数字がi=3, 5にあったとすると、l <= 3 かつ r >= 5の場合にこの数字において被りが生じるので、答えを引かないといけません。同じ数字が3, 5, 7とある時は、[3,5]と[5,7]という感じでやって区間を含むかどうか同じように処理すれば問題なくできそうです。クエリ区間に対して、対象の区間を含むかどうかをうまく調べる方法、ありそうだなーと思ってググるとありました。というか同じ問題のようなものが出てきました。
結局、区間を含む個数を引いてやる方法でもできそうですが、定数倍が重そうでpypyで通すの厳しいのではと思って、同じ問題のようなものの解き方でクエリをソートしてBITを使ってやりました。結局2TLEして微妙に改善頑張ってギリギリ通った。
参考にしたのはこちら
hama-du-competitive.hatenablog.com
提出一覧
All Submissions - AtCoder Beginner Contest 174
感想
Dで40分くらいロスしてるのがちょっと勿体無いけど久々に全完できてすっきり
