AtCoder Beginner Contest 145：D - Knight

問題

https://atcoder.jp/contests/abc145/tasks/abc145_d

解法

各移動で原点から x, y 座標合わせて 3 は増加するから，(X + Y) が 3 で割り切れないとき，答えは 0 通り．

そうでないとき，操作の回数 n は (X + Y) / 3 回であると分かる．n が偶数のとき，|X - Y| は偶数になり，n が奇数の時は奇数になる．このようにならない場合は答えは 0 通り．

2 種類の操作はそれぞれ (n - |X - Y|) / 2 回と (n + |X - Y|) / 2 回行われると分かるので，前者を用いて C(n, (n - |X - Y|) / 2) 通りが答えとなる．コンビネーション計算は逆元を使う必要がある．

解答

https://atcoder.jp/contests/abc145/submissions/9001104

AtCoder Beginner Contest 146：F - Sugoroku

問題

https://atcoder.jp/contests/abc146/tasks/abc146_f

解法

辞書順最小にしたいので，マス N からマス 0 に向かって「ゲームオーバーマス」を避けながら，すごろくの目を最大化しながら進んでいけばよい．途中「ゲームオーバーマス」が M マス以上連続している場合，ゴールすることが不可能．O(N)．

解答

https://atcoder.jp/contests/abc146/submissions/8988127

AtCoder Beginner Contest 146：E - Rem of Sum is Num

問題

https://atcoder.jp/contests/abc146/tasks/abc146_e

解法

K = 1 のとき，答えは 0．

そうでないとき，各 A_i から 1 を引き，累積和を求めておくと，「A の空でなく，長さが K 未満である連続する部分列で，要素の和を K で割った余りが 0 になるものの数」を求める問題になる．これは，左端から map で各数字の登場回数をメモしておき，A_k と等しい値が A_(k - K) ~ A_(k - 1) の間にいくつ表れているかを答えに加算していくことで求められる．O(NlogK)．

解答

https://atcoder.jp/contests/abc146/submissions/8987815