bouzuya.hatenablog.com

ぼうずやのにっき

アルゴリズムと数学 演習問題集 062, 063 を解いた

アルゴリズムと数学 演習問題集 062 - Teleporter を解いた。 ABC167 D でもある。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc167_d

K <= 10^18 という制約から K 回のテレポートを愚直にシミュレートすると間に合わない。町の個数 N は N <= 2 * 10^5 なので鳩の巣原理 https://ja.wikipedia.org/wiki/%E9%B3%A9%E3%81%AE%E5%B7%A3%E5%8E%9F%E7%90%86 で K 回の訪問のうち N 回を超えるものは必ずある町に複数回訪れる。要するにどこかでループに入る。このループをぐるぐる回る部分を省略できれば間に合う。

K <= N の場合は愚直にシミュレートしても間に合う。そうでない場合は N 回のテレポートをシミュレートしてループに入るまでの町の個数とループに含まれる町の個数 (ループの長さ) を数える。ループに入る前とループに入った後の町の個数でシミュレートする。ループに入った後の町の個数は K からループに入るまで町の個数を引いて残りをループの長さで割った余りとして求められる。

ABC167 のときは WA 出さなかったけど今回は WA を出した。 K <= N の場合をなぜか K <= 100_000 にしていたことによる。せめて 200_000 にしていれば WA はなかった。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29793728

アルゴリズムと数学 演習問題集 063 - Move on Squares 2 を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bb

例題。小さい N で実際に書いてみると……。右へ突き当りまで進んだあと下で突き当りまで進んで左にひとつ進んで上で突き当りまで進む……というジグザグで進む。問題になるのは最後に左上へ折り返す方向でジグザグが終わるかどうか。ジグザグ (上下に進む回数) が偶数なら良いので N % 2 == 0 なら Yes になる。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29792429

昨日からだけど例によってひな人形を出している (2021-03-03, 2020-03-03, 2019-02-20) 。

今日のコミット。