TikZ

ARC091 F Strange Nim

https://arc091.contest.atcoder.jp/tasks/arc091_dK を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは,その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。 実験から…

SRM 729 Med. FrogSquare

問題概要 n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。 誤解法 四隅だけ使えばよく,到達でき…

状態がループするゲームの解析(後退解析)

状態がループするゲームは、DAG ではないため動的計画法が使えない。代わりに 後退解析 というテクニックを用いる。次のゲームを考えよう。n 頂点 m 辺の有向グラフが与えられる。最初、頂点 s に駒が置かれている。プレイヤーは駒を隣接頂点に動かすことが…

ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_bこの解説では、座標を(横,縦)で表している。$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。 $(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である…

CF #458 E. Palindromes in a Tree

重心を求めるコードが間違っていたので修正しました(sz[v] >= x / 2ではなくsz[v] > x / 2が正しい)。計算量に影響はないです。2018-01-22 21:25http://codeforces.com/contest/914/problem/E重心分解による分割統治法で解く。重心を c としたとき、回文パ…