問題 No.416 旅行会社 - yukicoder 解法 クエリを逆に読んでデータ構造をマージする一般的なテクを使えば解けます。まず消される辺についてはすべて消されてる状態にします。この際 0 と連結な頂点は答えが -1 です。で, クエリの後ろの辺から辺を追加してい…

med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。 問題 TopCoder Statistics - Problem StatementU さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして, 集合 S の中から何らかの数 X …

院試が終わりました。受かったらそれについてもなんか書きます。 問題 TopCoder Statistics - Problem Statement0 ～ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。 あなたは, 今までに買った商品の重さ…

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えます。dp[n][m][now] = (すでに n 回キーを押したときに, 目標の文字列と m 番目までは一致していて, 生成されている文字は now 個であるような場合の数) という dp をします。これは各状態で 0 を…

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えてみますと, dp[i][rest] = (i 番目まで考えた時点でべき乗する数が C から rest まで減っているような時の和) というのを考えると, この i 番目でべき乗する数をいくつ使うかで場合分けして A[i]^…

問題 Hyperrectangle | Aizu Online Judge 解法 まず, このページを見ると d 次元の立体における体積の求め方が分かります。各辺の長さが 1 の三角錐(?) の体積は 1/d! なんですね。 単体 (数学) - Wikipediaで, 後は包除原理です。例えば 各辺の長さが {2, …

問題 Stack Maze | Aizu Online JudgeH*W の迷路が与えられる。この迷路には小文字のアルファベットで表される宝石と, 大文字のアルファベットで表されるそれに対応する宝石を埋め込む穴がある(例えば 'a' とそれに対応する 'A' がある, という感じ)。あなた…

Merchant, かわいい(小並感) 問題 Quest of Merchant | Aizu Online Judge 解法 すごく複雑そうな問題に見えますが, 落ち着いて問題を分解すると一個一個は大したことありません。まず, 1 回の出張で訪れる町の集合がわかったら, その町の集合へ訪れる最短時…

問題 Luigi's Tavern | Aizu Online JudgeH 人の勇者, W 人の戦士, C 人の僧侶, M 人の魔法使いがいる。以下の条件を満たすパーティは最大いくつ作れるか。 パーティには必ず勇者がいなければならない。 同じパーティの勇者と戦士は仲良くなければならない。…

この問題実は btk さんから相談をもらっていたんですけど時間内に解けなかった…(主に蟻本を探していた) 問題 No.409 ダイエット - yukicoder 解法 dp[i] = (i 日目に最後にドーナツを食べる際の最小体重)とします。この発想の時点で結構頭良い気がします(こ…

問題 No.408 五輪ピック - yukicoder 解法 「頂点 1 からの距離が 2 の頂点 a, b が辺でつながっていたら, 1 -> c -> a -> b -> d -> 1 みたいな感じでループにならない？」っていうのが基本的な発想です。つまり, 各頂点について「1 からの距離が 2 になり…

問題 Beautiful Currency | Aizu Online Judge要素数 n の数列 a が beautiful であるとは, 1 以上 n-1 以下の任意の i について, a[i+1] % a[i] == 0 となることである。数列 a のいくつかの数を入れ替えて, a を beautiful にしたい。a[i] の値を b[i] に…

問題 Number Sorting | Aizu Online Judge 解法 dp[i] = (A+i 番目の数字から始まる数列の数) とします。B-A 例えば 792 という数字の次に来るものを考えると, 8**, 9** となるもの i.e. [800, 1000) 79* となるもの i.e. [793, 800) というように, 各桁を 1…

問題 TopCoder Statistics - Problem Statement白い頂点と黒い頂点が与えられる。白い頂点からなる線分と黒い頂点からなる線分で, 交差するものは存在するか。 解法 実は, 線分が交差する場合, 白い頂点の線分か黒い頂点の線分のいずれかはその凸包のいずれ…

問題 TopCoder Statistics - Problem Statementクリップボードが与えられる。これは H*W 個のセルがあり, それぞれのセルは透明か RGB いずれかの色をしている。このクリップボードを, 左上が(0, 0), (1, 1), ..., (T-1, T-1) になるように (0, 0) が一番下…

問題 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 で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少…