すごく好きなタイプの問題です。 問題 No.321 (P,Q)-サンタと街の子供たち - yukicoder 解法 a*P + b*Q は, P と Q の最大公約数 G に関して, c*G (c は整数) という整数値すべてを取ることはよく知られています。 今回も似たようなことが出来ますが, (c*G, …

問題 arc046.contest.atcoder.jp 解法 貪欲にやっていきます。男性を年収が低い順, 女性を希望年収が低い順に並べておきます。 で, 男性の年収が低い順に以下のことを調べます。1. 今考えている男性を man とする。 2. man の年収で OK な女性を set に詰め…

問題 No.320 眠れない夜に - yukicoder 解法 フィボナッチ数列の第 n 項を fib[n] とします。 を計算する際に間違えて -1 したとすると, そのマイナスの影響は, 第 m+n 項には fib[n] になって帰ってきます。なので, やることとしては, 第 N 項の数をフィボ…

coderunner 2015 に参加しました。もうちょっと順位上げられたなぁとは思うんですが本戦自体も, その後の懇親会もとても楽しめました。 来年ももしあったらぜひ参加したいです。このページでは本戦の問題の紹介と自分の考えたことを書きたいと思います。問題…

問題 No.318 学学学学学 - yukicoder 解法 解法はこの問題に似ている気がします。 mayokoex.hatenablog.com大きい数が最後に挟み撃ちするということは, 要するに大きい数のほうが優先的に採用されるということなので, 大きい数から順番に数を決定していきま…

いろいろ勉強になりました。良い問題。 問題 No.317 辺の追加 - yukicoder 解法 よくある計算量の短縮で, 「 が に収束する」というのがあります。今回はこれを利用しましょう。まず UnionFind を使ってグラフ上の連結成分, およびその連結成分の頂点数を求…

SRM 675 に参加しました。 easy まぁまぁの点数で出せたのにしょうもないミス…なんか最近 med は計算量落とし問題が多くて雰囲気変わったなぁって思いますね。 問題 TopCoder Statistics - Problem Statement 解法 まず, 頂点 0 から 頂点を 2 つずつ生やし…

問題 codeforces.com 解法 最小全域木を作るときは, 小さいコストの辺を優先して選んでいき, もしその辺を追加してもループが得られなかったら木の辺として追加する, というアルゴリズムを使いますが, この問題の基本的なアイデアはそれです。頂点 1 にすべ…

Codeforces Round #335(Div. 2) に参加しました。また D 問題の実装が詰め切れず 3 完…ていうか今回 A 問題が一番難しくて B 問題が読解困難, C が一番手をつけやすかったという。 問題 codeforces.com 解法 例えば 9 3 4 5 6 7 8 2 1 という数列を考えると,…

問題 No.315 世界のなんとか3.5 - yukicoder 解法 まずよくある桁 DP っぽく考えると, dp[n][big][exist3][mod3][modP] = (n 桁目で元の数が今作ってる数より大きくなっているフラグが big で 3 が数字に含まれているフラグが exist3 で 3 で割った余りが mo…

問題 TopCoder Statistics - Problem Statement 解法 合ってるとは言ってないですが最後の結構硬そうなサンプル通ってるので多分合ってると思います(珍しく #include とか省略しないで書いてるので誰か確かめてほC)。 提出できました。まず蟻本を思い出すと,…

うーん, SRM のコード提出できないんですが…(なぜかこのコードは web arena で提出したら AC した) あとで div1 med も解説載せますがこっちは AC したことを確かめてないです(というか誰かに確かめて欲しい) 問題 TopCoder Statistics - Problem Statement …

問題 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) を飛ばすこと…

問題 No.309 シャイな人たち (1) - yukicoder 解法 この問題に考え方が非常に似ています。mayokoex.hatenablog.com各行について「手をあげる人の集合」を考えると, これは別の場合と独立に考えることができるので happy ということです。 具体的には, dp[r][…

D 問題にしては簡単すぎない？ 問題 codeforces.com 解法 k = 1 の場合のみ特別な場合分けが必要ですが, 基本的な方針は以下のとおりです。k != 1 のとき, f(0) != 0 であるとすると矛盾するので, f(0) = 0 です。a を任意の非ゼロ自然数として, a*k^b (b は…

問題 codeforces.com 解法 x と y の文字列の長さを求めます。で, その最小公倍数を求めます。その値が g であったとすると, x の i+a*g (0 なので, それらの値を足し算して求めれば良いです。 const int MAXN = 1000010; int alpha[MAXN][26]; int main() {…

問題 codeforces.com 解法 2 通り解法を紹介します。一つは vector を使う方法で, もうひとつは set を使う方法です。vector を使う方は, next[i] = (i の次にトーナメントに残ってる人) というのを保持しておきます。最初は next[i] = i+1 ですが, 各クエリ…

問題 No.308 素数は通れません - yukicoder 解法 w = 1, 2, 3, ... と調べていくとわかるのですが, w = 7 までは, 素数に囲まれて 20 程度までしか辿り着けません。 一方で, w = 8 になると, n が 32 以上になれば必ず 8m+2, 8m+4, 8m+6, 8m+8 の列にたどり…

出るつもりだったのに開始時間を勘違いして出れなかったこどふぉ。 問題 codeforces.com 解法 もっと簡単に解けるらしいですが, dp で解きました。dp[now][start][use] = (now 番目の数字を見ていて, 最初の数字は start にするつもり, 反転させているフラグ…

問題解くより入力の処理の仕方に対応するのに時間かかった。 stringstream 使って getline の流れは覚えておいたほうが良いかも。 問題 TopCoder Statistics - Problem Statement 解法 最小全域木やるだけ。 struct UnionFind { vector<int> par; int n, cnt; Uni</int>…

SRM 674 は不参加です。まだ easy しか見てないですが easy は早解き出来そうな雰囲気だったので出たかったなぁ。 問題 TopCoder Statistics - Problem Statement 解法 まず, num[i] は各頂点 i の次数を表していることに気が付きます。 与えられたグラフが…

昔の easy は簡単(最初に考えた方針が間違えていて, しかもサンプルが無かったら絶対 WA してた)。 問題 TopCoder Statistics - Problem Statement 解法 n = (木の本数) とします。 まず, 答えが n-1 以下になることは明らかです。一番低い木に合わせて他の…

問題 TopCoder Statistics - Problem Statement 解法 気づくべきなのは一つで, 答えは必ず K 以下になる, ということです。かっこ良く言うと鳩の巣原理からわかりますが, まぁ明らかでしょう。 ということで, dp[n][state] = n 番目の文字を見ている時点で, …

問題 TopCoder Statistics - Problem Statement 解法 正方形を作る際, 左下の点を決定すれば, どのような正方形になるかは一意に決まります。ということで, 左下の点がどこに来る可能性があるのかを考えると, これは各 (x[i], y[j]) (0 こころとしては, 位置…

SRM 400 番台の easy は簡単(ホントか) 問題 TopCoder Statistics - Problem Statement 解法 まず, 一回の白石の移動で目的の場所まで動かせたら Romeo の勝ちです。そうでない場合は, Romeo は負けないように動かします。どんなふうに石を動かしても次に St…

してやられた！という感じです。 問題 TopCoder Statistics - Problem Statement 解法 当然すべての場合を考えていると間に合わないので, 見方を変えます。ランダムに選ばれた結果, 木の高さがそれぞれ h[0], h[1], ..., h[n-1] になったとします。 整数の組…