問題 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 の遷移を限定するこ…

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

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

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

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

問題 Twin book report | Aizu Online Judge 解法 本を読む時間を最短にしないといけないことに注目します。とりあえず感想を書かなければならないことは忘れて, 読むことだけを考えましょう。ある一冊の本(A とする)を読むのにかかる時間が, 他のすべての本…

これ全然むずかしくないし 250 くらいで良いのでは…？ 問題 Off Balance | Aizu Online Judge 解法 言われたとおりやるだけです。ブロックを上から調べていき, それが地面にどれだけくっついているのかを調べます。 また, そのブロックの上に乗っかっている…

問題 Roll-A-Big-Ball | Aizu Online Judge 解法 大玉の通る線分 p1-p2 と障害物 minX-minY-maxX-maxY との間の最小距離は, p1-p2 と (minX,minY)-(minX,maxY) の距離 p1-p2 と (minX,minY)-(maxX,minY) の距離 p1-p2 と (maxX,minY)-(maxX,maxY) の距離 p1-…

問題 偏りのあるサイコロ | Aizu Online Judge 解法 実装するだけ。と言っても結構めんどくさいので実装方針を軽く書きます。サイコロのクラスを作って, init(t, f) … top と front を決めたらサイコロの状態を決定する rotate(dir)…回転させるというメソッ…

問題 Dinner | Aizu Online Judge 解法 食堂全振りをベースに考えます。ここから部分問題として, 「j 日目を自炊にしたらどうなるか」を考えてみます。 こうすると, 当然のことながら C[j] の幸福度はなくなります。また, j 日目までに自炊パワーは j 減って…

問題 FizzBuzz | Aizu Online Judge 解法 二分探索します。calc(x) = ([1, x] まで fizzbuzz を書いた時の文字数), とすると, これは [1, 10), [10, 100), ..., [10^(n-1), 10^n) , [10^n, x] の文字数をそれぞれ調べれば求めることが出来ます。これで calc(…

これめっちゃ難しいと思うんですけど… 問題 Prowler | Aizu Online Judge 解法 自分の周りの 8 マスの状況を全部考えてみると, 次に移動できるマスが一意に決まりそうなことに気づきます。よって, 素直に最短経路を求めてその時に通ったマスの数を求めれば良…

問題 And Then. How Many Are There? | Aizu Online Judge 解法 残っている円盤を状態としてメモ化再帰すればいけそうなんですが, AOJ のメモリ制限的に dp[1よく考えると, 毎回の遷移で円盤は 2 つ消えるので, 状態としては bit が偶数個/奇数個 立ったもの…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=F 解法 解説スライドを参考にして解きました。RUPCに参加してくださった方ありがとうございます！Day1の解説スライドを公開しました https://t.co/MOfSf8WrP9 #rupc201…

問題 A Broken Door | Aizu Online Judge 解法 前のドワコンの C 問題に似てるということで解いてみました。今回は前回のように二分探索で解くのではなく, ダイクストラっぽく解きたいと思います。ゴール地点からスタート地点に向かって探索します。ゴール地…

学校の別のコースの人の授業でやった問題らしいので軽い気持ちでやってみたけど, 全然わからなかった… 問題 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge 解法 まず基本的な考察をします。例えば 10 7 8 9 といった数列を考えると, 最…

問題 Angel Stairs | Aizu Online Judge 解法 後ろからたどっていけば良いです。 例えば, ひとつ目の入力例を見ていきましょう。C E D# F G A C E F Gまずそれぞれの配列を逆さまにします。A G F D# E C G F E Cまず G を作る必要があります。スタートが A …

問題 Chocolate | Aizu Online Judge 解法 まず, チョコレートを取る順番は上の行から順番で良いとわかります。これは 2 行目以降のチョコレートは必ずそれより上にあるチョコレートを取らないと取ることが出来ないことからわかります。ということで, 一番上…

前のこどふぉの問題を解こうとしたら Stern-Brocot 木というのを考えるらしいので AOJ で練習してみました。 Spaghetti Source - Stern-Brocot 木既約分数を探索するのに都合が良さそうですね。 問題 Rational Irrationals | Aizu Online Judge 解法 Stern B…

大学受験のとき使った参考書を引っ張ってきました。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335 解法 まず寄り道回数のうち左に移動する回数を i 回として横移動と縦移動を分けます。そして, 「横移動の場合の数」と「縦移動の場…

問題 Modular Query | Aizu Online Judge 解法 配列 c をソートしておき, 各クエリ q について, c[n-1] から余りを求めていくと考えます。このとき, c[i] を q で割った余りが p であるとすると, c[i]-p から c[i] までの数字は, 余りが p よりも小さいこと…

9だと思います。 問題 6/2(1+2) | Aizu Online Judge 解法 今までのように返す値を単なるintみたいな感じにしても上手くいかないのでsetを返すようにする。式を分析するときはそれぞれのoperatorがどの順番で使われるのかをnext_permutationで調べていく(た…

題名長いっすね。構文解析の練習です。だいぶ慣れてきた。 問題 How can I satisfy thee? Let me count the ways... | Aizu Online Judge 解法 formulaにしたがって構文解析する。 typedef string::const_iterator State; int formula(State& begin, int s);…

ACM-ICPCの模擬国内予選に参加しました。チーム(@haraduka_, @garasubo, @mayoko_)としてはA, B, Dの3問を解いてなるほど。といった感じでした。以前1年分やった感じでは4完はできると思っていたのでちょっと悲しいです。しかも僕が担当して解かれた問題は一…

デバッグに非常に時間がかかったけどなんとか出来た。 問題 Equation | Aizu Online Judge 解法 問題文中に最高のヒントが書いてあるのでそれを元に関数を作る。 <equation> ::= <formula> "=" <formula> <formula> ::= "T" | "F" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | </formula></formula></formula></equation>…