AtCoder Beginner Contest 157に参加しました。
成績
5完4ペナで282位でした。
微増。
A - Duplex Printing
。
B - Bingo
言われた通りにやります。こういうのはループを回すより全パターン手で打った方が早そうなので、縦横斜め8ラインを気合いでチェックします。
添字ミスで1WA。いやサンプル合うなや。
C - Guess The Number
BでいきなりWAを出してしまい、不穏です。
とりあえず、空いてる桁をなんとなくで埋めていったらなんとなくサンプルが通ったので、なんとなく提出。案の定WA…。
落ち着いて考え直すと、 なので、
桁の整数を小さい方から全て調べることができます。
桁の整数を小さい方から全て調べて、AC。
前半のくだりほんまにいらんかった。
D - Friend Suggestions
わからんわからんわからん。情報量が多すぎる。Eを見に行きます。
E - Simple String Queries
なんとなくいけそうなので、Dの前にこちらを考えることにします。
一点更新クエリ（type1）と区間についてのクエリ（type2）といえば、セグメント木です。26文字のアルファベットがある区間に含まれるか否かは、bitを用いて管理できそうです。解けました！！！（具体的には、区間orを計算できるセグメント木を用意して、'a' -> , ... , 'z' ->
として初期化します。そうすると、ある区間のorのpopcountがその区間に含まれる文字の種類数になります。）
0-indexedに直し忘れている箇所があり、1WA。そんな〜。
D - Friend Suggestions
結局求めたいものは 、各人の「友達の友達の…友達たち」のうち、「ブロック関係にある人」「直接の友達」「自分自身」を除いた人数だとわかります。これはUnion-Findを使うと高速に求められます。
配列の大きさが足りなくて1WA。そんな〜。
F - Yakiniku Optimization Problem
秒の調理で
枚以上の肉が焼きあがるような最小の
を求める、と考えれば、これは二分探索で求まります。
を固定したときに、最大で何枚の肉が焼きあがるかを考えます。
を変形すると
となるので、
枚目の肉が
秒以内に焼きあがるのは、熱源が中心
、半径
の円の内側にあるときだとわかります。あとは、
個の円が最も多く重なっているような点に熱源を置くだけ！！！
有名問題っぽいのでTwitterで調べてみると、この問題にたどりつきます。何人かの提出を読んで、熱源を置くべき点は円の中心か交点に限られるとわかったので、書きます。
交点の座標を求めるパートにかなり苦戦してしまい、コンテスト中にはACできませんでした…。先に交点を通る直線の方程式を求めてから、円と直線の交点として求めると楽でした。
