問題 agc002.contest.atcoder.jp 解法 クエリが 1 個の場合を考えると, UnionFind を使うことで O((N+M)logM) ぐらいで答えを求めることができます(単体だけを考えたら O(N+M) でできそうだけどそれは今はいいです)。というのは, ok(m) = (辺の id が m の部…

問題 TopCoder Statistics - Problem StatementAlice と Bob がゲームをする。ゲームは交差しないいくつかの円が書かれた平面上で行う。 まだ円内に赤点がない円を選ぶ。 その円内に赤点をいれる。 赤点を入れることができないほうが負け。 両者が最適に動い…

問題文長すぎな。 問題 TopCoder Statistics - Problem StatementN 種類のボールがある。これらは以下のような特徴がある。 大きさが決まっている(medium と large の 2 種類がある) 種類ごとにいくつあるか決まっている 種類ごとに色が異なることは保証され…

問題 No.404 部分門松列 - yukicoder 解法 とりあえず配列 A は座圧しておきます。そうすると, 各 A[i] を真ん中とする門松列の数は, 基本的には (i より左側にある A[i] より小さい値の数) * (i より右側にある A[i] より小さい値の数) (i より左側にある A…

問題 arc058.contest.atcoder.jp 解法 余事象を考えます。つまり, 「XYZ が含まれない数列の数」を求めることを目的にします。これを dp で解くことを考えましょう。状態として, 直前の X+Y+Z 個の数字を持っておけば良いのはわかりますが, これだと 10^(X+Y…

問題 arc058.contest.atcoder.jp 解法 左上の座標を (1, 1), 右下の座標を (H, W) とします(座標は (y, x) )。y 座標が H-A+1 に初めて到達したときの x 座標の値で場合分けします。y 座標が H-A+1 に初めて到達したときの x 座標が i ( > B) であるとすると…

問題 TopCoder Statistics - Problem Statementあなたは K 回コインを投げるゲームをする。コインは表裏がそれぞれ 1/2 の確率で出る。ルールは以下のとおりである。 コインを投げてまだ何も書いてない面が出たら, その面に好きな数字を書く。 出た面に書か…

問題 TopCoder Statistics - Problem Statementグラフが与えられる。各頂点にはスコアがある。 このグラフから K 本の辺を選び, 以下のようにスコアを計算する。頂点から少なくとも 1 本の選ばれた辺が伸びている場合, その頂点のスコアを得られ, その和がス…

問題の勘違いはな。 問題 TopCoder Statistics - Problem Statement 以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。 文字列の長さは N 文字列は 'a', 'b' のみで構成される 配列 x が与えられる。長さ i+1 の部分…

初 HL 分解です。 問題 No.399 動的な領主 - yukicoder 解法 HL 分解を使います。下の記事が HL 分解については詳しいです。 math314.hateblo.jpまた, 以下で書かれていることは pekempey さんの記事でもまとめられています。 pekempey.hatenablog.com下のコ…

問題 agc001.contest.atcoder.jp 解法 想定解のほうで解きます。木の直径周りではいろんな定理が成り立っていて, この辺りは知っておいた方が良いかもしれません。定義 頂点 v からの距離が最大の点との距離が最小であるような頂点を木の中心という。 木の中…

問題 agc001.contest.atcoder.jp 解法 よくわからない理論で通ってしまったので後で想定解も書きます。ここでは本番に自分が書いた解法を書きます。頂点 v が, 木の直径をなす一つの頂点であるとします。このとき, v は葉になっていないといけないので, v か…

問題 agc001.contest.atcoder.jp 解法 こういうの, 直感的に gcd もしくはその考え方を使うような気がします。と考えて適当にやると解けそうです(本番そんな感じで適当に書いたら AC してびっくりしました)真面目な話をすると, 2 回光が反射したのちは, 必ず…

天才か… 問題 agc001.contest.atcoder.jp 解法 普通に計算しようとすると, (Ai + Aj + Bi + Bj)! / (Ai+Aj)! / (Bi+Bj)!を各 i, j について求めてその和を計算することになります。が, これだと間に合いません。そこで, 上の式をよく見ると, これは (0, 0) …

問題 Twenty Questions | Aizu Online JudgeN 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少…

問題 No.399 動的な領主 - yukicoder 解法 各頂点を通った回数が数えられれば, その頂点で合計かかった金額は, (cnt+1)*cnt/2 と求められます。よって, 各頂点の通った回数を求めることを目標にします。これは tree 上で imos 法をすると解けます。この発想…

問題 No.398 ハーフパイプ(2) - yukicoder 解法 dp します。dp[i][mini][maxi][sum] = (i 番目までで最小値が mini, 最大値が maxi, 合計が sum になっているような場合の数)とします。この dp は状態が O(6*W*W*6*W) で, 遷移に O(W) かかり, 結構計算量が…

問題 My friends are small | Aizu Online Judge 解法 ある集合が有効かどうかを調べるときは, 「まだ選ばれていないやつの中で一番重さの小さい友達をリュックの中に入れることができないか」というのが判定基準になります。そこで, 配列 w をソートしたの…

alien「ありえんよさみが深いw」— マヨ子@大天使クサハエル (@mayoko_) 2016年7月7日 問題 Alien's Counting | Aizu Online Judge宇宙人に N 本の指があり, この間に M 個の拘束条件が成り立っている。各拘束条件は, 「i 番目の指を曲げたら j 番目の指も自…

問題 No.393 2本の竹 - yukicoder 解法 想定解とはちょっと違う解法になりました。考察で, 「長さの短い竹をなるべく受け付ける方が良い」というのは変わりません。なので, 配列 A をソートしておけば, 選ばれる竹は, [0, upper) というような区間を選ぶこと…

問題 TopCoder Statistics - Problem Statement頂点の接続関係が与えられる。 以下の性質を持つような木の場合の数を求めよ。 葉を除くすべての頂点は, 子を 1 つか 2 つ持つ 木の根からの距離を rank とすると, rank = k の場所には 2^k 個(ただし rank が…

問題 TopCoder Statistics - Problem Statementチェスのナイトのようなものを考える。チェスのナイトは今いる位置から (+1, +2), (+1, -2), (-1, +2), (-1, -2), (+2, +1), (+2, -1), (-2, +1), (-2, -1) と動くことができるが, 今回のナイトは (+a, +2), (+…

珍しく秒で解ける問題でした(ここまで簡単じゃなくていいけどこういうの 1 つある方が参加する方も楽しくて良いです)。 問題 TopCoder Statistics - Problem Statementn 人の人がいる。それぞれの人には強さ s[i] が定義されている。n 人を 3 グループに分け…

問題 TopCoder Statistics - Problem Statement一列に並んだ N マスを指定された色に塗りつぶしたい(色の指定のない箇所もあるが, 何らかの色を塗る必要はある)。そのために, 以下の 2 つの操作をする。 まず, 長さ L のスタンプを作る。これには L * stampC…

こっちのほうが B っぽくない？(C++ でどうやるのか知らないけど) 問題 arc057.contest.atcoder.jp 解法 L とすると, L^2 となります。これが最小かどうかは分からないので, (L/10)^2 というように続いていきます。上の表記は実数で考えていますが, これを整…

全然解けなくて悲しい… 問題 arc057.contest.atcoder.jp 解法 sum = a1 + a2 + ... + an とします。K L x 日目以前では機嫌の良い日の日数は変わらない x+1 日目以降は全勝しているので, 勝率は常に上昇しており, 機嫌が良かったのに悪くなることはない。ま…

何か楽しそうなキャンペーンをやっていたので応募しました。プレゼントがほしかったのでみんなには内緒でこっそりやってました(といっても知ってる人多そう)。 問題 recruit.elysium.co.jp(もしかしたら このページが消えるかもしれないので問題文も書いてお…

この問題とは関係ないですが Typing War は楽しいです。 trap.tokyotech.org 問題 No.391 CODING WAR - yukicoder 解法 包除原理で解きます。N 人が M 問のいずれかに担当する場合の数は M^N 通りです。ですが, これだと N 人が M-1 種類以下の問題にしか割…

問題 No.389 ロジックパズルの組み合わせ - yukicoder 解法 sum = H1+H2+...+HK とします。すると, 塗られてないセルの数は M-sum になります。K 個の要素を分割するので, K 個の要素の間に塗られていないセルがいくつか必要です。これで合計 K-1 個の塗られ…

全探索お姉さんとアルゴリズムお姉さんはどっちが先だったんだろう？ 問題 A Holiday of Miss Brute Force | Aizu Online Judge 解法 時間に関しては 6 で割ったあまりのみを考えれば良いです。そう考えると, d[t][x][y] = (時間 t に x, y にたどり着けるよ…