2015-12-05から1日間の記事一覧
問題 codeforces.com 解法 ゲームの構造的に, grundy 数が使えます。f(n) = (皿に石が n 個乗っている際の grundy 数) とすると, 皿に石が n 個乗っている状態からは, (a)皿に石が n-1 個乗っている状態, または (b)石が n/2 個乗っている皿が k 個ある状態 …
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 まず前計算として, (y0, x0, y1, x1) で決まる長方形内にある数字の合計, および 長方形内にある各数字の数, を求めておきます。そのあとはしゃくとり法です。問題文にあるように c と d を決…
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 基本的な方針は(頂点, 色)の組でまとめた頂点に対するグラフについてダイクストラやるだけです。ただ, 少し工夫しないと計算量やメモリが大変なことになるので少し工夫します。工夫1: (頂点, …
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ここでは「勝つ」というのは「実 1 を食べる」ということを指します。また, 「実(み)」と「頂点」はしばしば同じ意味です。まず, 頂点 1 の次数が 1 なら A さんは速攻で食べれば良いので A が…
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 文字列 S の start 以降の部分文字列を使うと, 文字列 T が表現できるとしましょう。このとき, S の start 以降の文字列は, T に現れる文字(例えば T = "abc" だったら a, b, c) を飛ばすこと…