AtCoder Beginner Contest #106 参戦記
AtCoder Beginner Contest 106 に参加して、なんとか全完しました。問題の簡単な解説と感想を書いていきます。筆者の提出はこちらです。
A問題 Garden (100点)
長方形の畑に十字の道を作ったとき残りの畑の面積は？ という問題。算数です。
B問題 105 (200点)
約数がちょうど8個の整数の個数を数える問題。
調べる範囲が小さいので制限時間的にはかなり余裕があり、実際に約数を数えていけばOK。
C問題 To Infinity (300点)
1123のような数字からなる文字列Sが与えられる。各数字を1なら1、2なら22、3なら333、といった文字列に置き換える操作を5000兆回行ったものをTとする。TのK番目の文字が何かを答えよ、という問題。
Tを文字列ではなく文字とその反復回数の列として持てば、例えば 1123 -> (1, 1), (1, 1), (2, 2^(5,000,000,000,000)), (3, 3^(5,000,000,000,000)), ... のような形式にすれば、1文字ずつ調べなくて済むのでK文字目はO(N)時間で求まります。ただし 2^(5000兆) は必ずKより大きいので、この冪の値は計算する必要なし。
D問題 AtCoder Express 2 (400点)
N個の都市 1, ..., N があり、都市の間には合計でM本の列車が走っている。都市 p, q のペアがQ個与えられるので、そのそれぞれについて、都市 p と都市 q の間にある列車の数を求めよ。という問題。厳密な話はリンク先を参照。
制約を見ると、列車数 M やクエリ数 Q は大きいので O(MQ) 時間のアルゴリズムはTLE。都市数 N は小さいので O(N^2) は許される。何らかの事前計算をして1クエリあたり O(N) ぐらいで求めたい。
最初、昨日参加した Codeforces の問題に似てると思って、同様の解法で提出したんですがWAでした。(たぶん列車の区間に重なりがあるからダメだった。)
次に、以前なんかの問題でやった覚えがある解法を試しました。列車を出発都市ごとに分類して、到着都市についてソートしておく。クエリに対して、出発地点を全列挙すれば、到着都市は二分探索で求まる。全体としては O(Q N log M) 時間、という解法。これは1個だけTLEでした。よくみたら二分探索は必要なく、累積和にしたところACになりました。
もう少し掘り下げて累積和を2段階に使うようにすると、実装はかなり単純になります。2次元累積和やるだけ。考察を深めると実装が軽くなるの好き。
振り返ってみると、発着都市が同じ列車は (重複度を除いて) 同一視していいというのに気づいていれば回り道せずに累積和にいけたかなと思います。
この記事が気に入ったらサポートをしてみませんか？