mayoko’s diary

プロコンとかいろいろ。

2015-12-05から1日間の記事一覧

Codeforces Round #334 (Div. 1) C. Lieges of Legendre

問題 codeforces.com 解法 ゲームの構造的に, grundy 数が使えます。f(n) = (皿に石が n 個乗っている際の grundy 数) とすると, 皿に石が n 個乗っている状態からは, (a)皿に石が n-1 個乗っている状態, または (b)石が n/2 個乗っている皿が k 個ある状態 …

CODE THANKS FESTIVAL 2015 H - 穴あきケーキ

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 まず前計算として, (y0, x0, y1, x1) で決まる長方形内にある数字の合計, および 長方形内にある各数字の数, を求めておきます。そのあとはしゃくとり法です。問題文にあるように c と d を決…

CODE THANKS FESTIVAL 2015 G - カメレオン

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 基本的な方針は(頂点, 色)の組でまとめた頂点に対するグラフについてダイクストラやるだけです。ただ, 少し工夫しないと計算量やメモリが大変なことになるので少し工夫します。工夫1: (頂点, …

CODE THANKS FESTIVAL 2015 F - お祭りとお菓子

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ここでは「勝つ」というのは「実 1 を食べる」ということを指します。また, 「実(み)」と「頂点」はしばしば同じ意味です。まず, 頂点 1 の次数が 1 なら A さんは速攻で食べれば良いので A が…

CODE THANKS FESTIVAL 2015 E - ノイズ除去

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 文字列 S の start 以降の部分文字列を使うと, 文字列 T が表現できるとしましょう。このとき, S の start 以降の文字列は, T に現れる文字(例えば T = "abc" だったら a, b, c) を飛ばすこと…