問題 Cubist Artwork | Aizu Online Judge箱を並べる。これを前から見ると D 列のキューブが X1, X2, ..., XD 個並んでいるように見え, 横から見ると W 列のキューブが Y1, Y2, ..., YW 個並んでいるように見える。 これを満たすようなキューブの並べ方のう…

問題 The Enemy of My Enemy is My Friend | Aizu Online Judge 解法 半分全列挙しました。まず, N 頂点を半分ずつに分けて, dp[s] = (集合 s だけを使う場合の軍事力の最大値) を計算します。で, これらを合わせるときは, 前半の頂点と隣り合っていない頂点…

問題 Manhattan | Aizu Online Judge 解法 一方の点 A は x 軸と平行な直線の上に乗せて考えても問題ありません。こうすると, もう一方の点 B の位置によって場合分けができます。B が y 軸と平行な直線の上に乗せられている場合 この場合は, A の位置をうま…

問題 arc053.contest.atcoder.jp 解法 まず, (a1, b1) (ただし a1 b2) という二つの組があった場合, (a1, b1) を先に並べるのが得です。 これは, max(a1, a1-b1+a2), max(a2, a2-b2+a1) を比較すればわかります。(a1 ということで, 並べ方としては, (a, b) (…

問題 TopCoder Statistics - Problem StatementH*W の長方形に, 以下のように数字が書いてある。 (1 行目): 0, 1, ..., W-1 (2 行目): W, W+1, ..., 2*W-1 ... (H-1 行目): (h-2)*W, (h-2)*W+1, ..., (h-1)*W-1ここからうまいこと長方形の区間を取って, その…

問題 TopCoder Statistics - Problem Statementw だけ離れて二本の柱が立っている。 一方の長さは 1, 2, ..., x の長さを等確率で取り, もう一方の長さは 1, 2, ..., y の長さを等確率で取る。二本の柱の先端距離の期待値を求めよ。 解法 1 本目の柱と 2 本…

問題 Milky Way | Aizu Online Judge 解法 各星の間の距離は, 線分と線分の間の距離の問題に帰着されます(5*5 の線分の対の距離を測って, 最小のものが星の距離と考えれば良い)。これは以前別の問題でやりました。 mayokoex.hatenablog.comあとはダイクスト…

問題 Magical Girl Sayaka-chan | Aizu Online Judge 解法 サンプル 1 みたいな感じで, K は 山のような形(小 -> 中 -> 大 -> 中 -> 小) になっているのが良さそうな気がします。実際にこれは正しいです。雰囲気証明すると, a [(Sa+...+Sb)/L] + [(Sb+...+Sc…

問題 鉄道乗り継ぎ | Aizu Online Judge 解法 めんどくさいダイクストラみたいな感じです。ダイクストラするとき, d[v][c] = (直前に乗った電車が c であって今いる頂点が v であるようなものの最短距離) というのが一番わかりやすそうですが, r_jk が単調減…

問題 Circle and Points | Aizu Online Judge 解法 ある円が答えだったとします。この円を少し動かしても, この円が最適であることに変わりはありません。この円を適当に動かして, 初めてある点とぶつかったとき, 円をこの点からはみ出さないように動かすと,…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2015Day1&pid=D 解法 適当に実験すると答えがわかります。自明っぽいところから攻めて行きます。 まず, g = gcd(h, w) とすると, (h/g, w/g) の長方形を g 回同じように繰り返している…

問題 Mr. Rito Post Office | Aizu Online Judge 解法 普通に dp しようとすると dp[次目指す場所][今いる位置][船の位置] みたいになりそうですがこれだと状態数多すぎで間に合いません(というか dfs だとループになりそう)。そこで, dp の遷移を限定するこ…

問題 Dashboard - Round 1C 2016 - Google Code JamA 枚のジャケット, B 枚のパンツ, C 枚のシャツがある。これらを適当に組み合わせて, (a, b, c) というようなペアにして服を着る。 ところでこの世界にはファッション警察がいて, (a, b, c) というペアの服…

GCJ はなんか苦手(得意なのもないけど)。 問題 Dashboard - Round 1C 2016 - Google Code JamB 個の頂点からなる有向グラフを考える。頂点 1 から頂点 B までの経路の数を M 個にしたい。これを満たすグラフは作れるか。作れるなら 1 つそのようなグラフを示…

問題 Princess, a Cryptanalyst | Aizu Online Judge 解法 N! 通りの並び方を試します。で, apple, length の "le" のように前の文字の後半, 後ろの文字の前半で一致しているところがあったら applength のようにつなげて考えればいけます。…と言いたいとこ…

問題 abc037.contest.atcoder.jp 解法 dp の本質は DAG って話を思い出せば簡単に解けます。 d.hatena.ne.jpこの問題では, あるマスから遷移できるマスは一方通行的なので, DAG であると考えることができます。その上での経路数はまさに上の記事の言っている…

人の不幸で飯がうまい 問題 TopCoder Statistics - Problem Statement数 n が与えられる。n 以上の数で, 以下の条件を満たす最小の整数を求めよ。 10 進法で表したとき, その数には count1 個以上の digit1 が含まれる。 10 進法で表したとき, その数には co…

問題 TopCoder Statistics - Problem Statement数 X から始まる数列を以下のように定義する。 X が偶数なら, 次の要素は X/2 X が奇数なら, 次の要素は X-1 これを無限に繰り返す 最初の要素が [A, B] のもののうち, 数 K が少なくとも一つ含まれるようなも…

問題 codeforces.com例によって正しいかっこ列 CBS を定める。 このかっこ列に対して, あるポインタ p から次のように操作をしていく。 L: p を 1 つ左に移動させる。 R: p を 1 つ右に移動させる。 D: p に対応するかっこが必ずある。p 番目のかっことそれ…

問題 橋の撤去 | Aizu Online Judge 解法 スタートする頂点を全部試すとして, 各頂点について O(N) で橋の撤去にかかる最小費用を求めれば良いです。まぁ木DP ですよね。サンプル見ればわかりますが, この問題でポイントなのは p -> v と訪れた後, 必ずしも …

問題 Worst Reporter | Aizu Online Judge 解法 順位表の再現はトポロジカルソートをすれば簡単にできます。あとは複数通りのトポロジカルソートがあり得るかですが, ここでトポロジカルソートのアルゴリズムを見てみましょう。 L ← トポロジカルソートした…

問題 TopCoder Statistics - Problem Statement有向グラフ G について, p(G) は, 「頂点 (v, u) について, v -> u のパスがあるような組み合わせの数」と定義する。今, 無向グラフで木のグラフが与えられる。このグラフのそれぞれの辺の向きを決め, 有向グラ…

問題 1, 2, ..., 100 が書かれたカードを使って A 君と B 君がゲームをする(カードはそれぞれ 1 枚ずつ)。ある数 N, K が与えられて, A 君は K 枚のカードにかかれている数を足し引きして合計を N にしたい。 B 君はカードを上手く選ぶことによって A 君がど…

エディタいじってたら一日が終わっていました。 問題 Sinking islands | Aizu Online Judge 解法 まず, 最初から連結でない場合は橋を架ける必要がないので答えは 0 です。他の場合は, どの時点で橋が連結でなくなるのかを調べます。 橋が連結でなくなったタ…

問題 TopCoder Statistics - Problem StatementL*H のグリッド平面が与えられる。以下の条件を満たす K 個の点の組は何通り考えられるか。 K 個の点は同一直線上にある 上記の直線は, y = 0 において x 座標が整数になる 解法 K=1 の場合は, 答えは明らかに …

問題 TopCoder Statistics - Problem Statementa, b, c, ... (a から n 番目の文字) を 1 回ずつ使って長さ n の文字列 s を作る。このとき, 以下の条件が成り立つようにしたい。 s は minStr よりも辞書順で後ろ s は最低でも minInv 個の反転文字を持つ(i …

問題 arc052.contest.atcoder.jp 解法 K の値に応じて場合分けします。K が小さい場合は, 桁dp で解けます。よくある dp[桁][あまりの差][smallFlag] ってやつです。K が大きい場合は, 各桁の和がせいぜい 100 であることを利用します。すると, 解の候補は i…

問題 arc052.contest.atcoder.jp 解法 まず自明な解法として, d[v][b] = (頂点 v までに, b 回タイプ B の道を通る場合の最短距離)というのがあります。b は N より大きかったらどこかの頂点を複数回通っていることになるので, 頂点の個数は O(N^2) でダイク…

この問題とは関係ないですが windows でそれっぽくプログラミングができるようになりました。 問題 Dashboard - Round 1B 2016 - Google Code Jam前半, 後半に分かれたワードの組が N 個与えられる。 あるワードの組 (s, t) について, 「すでに s と同じ文字…