ABC(AtCoder Beginner Contest)106 解説 - しゅういちのぶろぐ

はじめに

結構時間に余裕を持って全完できたため、初めて解説記事を書くことにした。帰宅TLEしたのにこの成績なので少し嬉しい。

A - Garden

https://beta.atcoder.jp/contests/abc106/tasks/ghi_q

はい。小学校か中学校の文章題ですね。道をスライドさせたら面積は(A-1)*(B-1)ですね。最初謎に道がダブっているところを足さなければ...と変なことを考えてしまい少しロス。

B - 105

はい。奇数だけをまずは見てあげたらいいことは自明です。また、制約がN<=200なので、該当するものに対してそれぞれ愚直に2重ループなどで約数が存在するかチェックし、その個数を数え上げ、条件に合えばカウントでOK。

C - ToInfinity

C - To Infinity

最初問題を見ると、なんかめっちゃ増えていくなぁというのがわかります。次に5000兆日後の文字列を想像すると、それぞれの数字を5000兆乗した個数分の数字が文字列のもともとあったものと交換されることがわかります。2^{5000000000000000}だなんて、明らかに10¹⁸を超えますね。しかし1はどれだけ掛けても1なので、文字列の最初から何個1が続いているか数えてあげて、それよりkの値が小さければ1、そうでなければ1の次にくる別の数字が答えとなります。

D - AtCoder Express 2

問題を読んでみると明らかにグラフ問題で、クエリで出された範囲内のうち、1以上のものを数えてあげればいい(同じ路線を通るやつがいるので、重み付き有向グラフにした)という双子の優しさに満ち溢れた問題だなと思いました。蟻本で一応確認してから、隣接行列を作って愚直に実装して3msだしO(10⁹)だけど通る気がするという謎の自信で提出すると当然TLE。あっ、やべぇと思いながらも高速にするよう考えていました。まず最初に出発時点からの本数の合計値を配列に入れて前処理してループを1周だけしたら計算量落ちるでしょ！wとしてみるもサンプルが合わない(これは当然で、到着地点が範囲内に入るように設定していないため)。そこでふと前処理と言えば最近累積和多いなと思い出しました(エスパー)。とりあえずググって内容だいたいなるほどね(あまり理解していない顔)と思いながら2次元累積和を実装してみるとサンプルが合ったため提出するとAC(67:17)。そりゃ皆さん早いわとなって終了しました。

感想

久しぶりの競プロだったけど解けて嬉しかったし、ブログ書くことで理解度増した気がする。