読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AOJ

AOJ 2439 Hakone

AOJ

問題 Hakone | Aizu Online Judge 解法 まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点で…

AOJ 2397 Three-way Branch

AOJ

問題 Three-way Branch | Aizu Online JudgeW*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか…

AOJ 2638 Hyperrectangle

AOJ

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

AOJ 2538 Stack Maze

AOJ

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

AOJ 2296 Quest of Merchant

AOJ

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

AOJ 2168 Luigi's Tavern

AOJ

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

AOJ 2305 Beautiful Currency

AOJ

問題 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] に…

AOJ 2326 Number Sorting

AOJ

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

AOJ 1302 Twenty Questions

AOJ

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

AOJ 2333 My friends are small

AOJ

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

AOJ 2222 Alien's Counting

AOJ

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

AOJ 2425 A Holiday of Miss Brute Force

AOJ

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

AOJ 2382 King Slime

AOJ

問題 King Slime | Aizu Online JudgeH*W のグリッド上に N 個の頂点がある。各頂点は, 上下左右いずれかの方向に移動でき, 移動する際は壁にぶつかるか別の頂点にぶつかるまで動き続ける。別の頂点にぶつかった場合, ぶつかった頂点同士は合体する。この移…

AOJ 2170 Marked Ancestor

AOJ

問題 Marked Ancestor | Aizu Online Judgeルートが頂点 0 の木が与えられる。頂点 0 の点は最初から黒く, それ以外の点は白い。これについて, 以下の二種類のクエリが投げられるので, 対応する。 頂点 v を選び, その点を黒く塗る。 頂点 v, もしくはその先…

AOJ 2182 Eleven Lover

AOJ

問題 Eleven Lover | Aizu Online Judge数字のみからなる文字列 s が与えられる。この中に, 連続した文字列でその表す数が 11 の倍数であるようなものは何通りあるか。ただし, 先頭が 0 であるような数は数とみなさないことにする。 解法 区間 [i, j] が 11 …

AOJ 1320 City Merger

AOJ

問題 City Merger | Aizu Online Judgen 個の文字列が与えられる(それぞれの文字は 20 字以下)。これら n 個を連続部分文字列として含む文字列を作りたい。この文字列の最小の長さはいくらか。 解法 bitDP します。dp[now][state] = (state にある文字列は作…

AOJ 2442 ConvexCut

AOJ

問題 ConvexCut | Aizu Online Judge 解法 答えがあるとしたら, それは重心以外ありえません。重心が答えになるとき, 図形は重心に関して点対称になっているはずです。素直にそれを実装しましょう。 typedef long double Real; Real eps = 1e-12; Real add(R…

AOJ 2157 Dial Lock

AOJ

問題 Dial Lock | Aizu Online Judgek 桁の数字が与えられる。もとの数 now から target という数を作りたいが, そのために以下の動作が許される。 動作: 区間 [s, t] および数 d を選び, その区間の数について, nxt = (prev+d)%10 とする。動作回数の最小の…

AOJ 2176 For The Peace

AOJ

for the peace という問題でキレてるの, 悲しみがある— マヨ子@大天使クサハエル (@mayoko_) 2016年6月27日 問題 For the Peace | Aizu Online Judgen 個の国がある。各国はいくつかのミサイルを持っているが, これを以下の条件を満たすようにすべて捨てたい…

AOJ 2383 Rabbit Game Playing

AOJ

問題 Rabbit Game Playing | Aizu Online Judge数列 D が与えられる。これに関して, 以下の条件を満たす並べ方は何通りあるか求めよ。 条件: 任意の i について, D[i] 解法 挿入DP というやつ?dp[i] = (i 番目までの並べ方の場合の数) というのが分かってい…

AOJ 2306 Rabbit Party

AOJ

問題 Rabbit Party | Aizu Online Judgen 匹のウサギがパーティーをする。各ウサギには友達度が定義されている(これが正の値を取るのは高々 m 個)。 ウサギ i がパーティーに参加した際の満足度は, パーティーに参加したウサギのうち, 友達度が最も低いもの…

AOJ 2249 Road Construction

AOJ

問題 Road Construction | Aizu Online Judge連結な無向グラフが与えられる。各辺には長さとコストが定義されている。このグラフを次の条件を満たすように変更したい。 各点 v の 0 からの距離(距離は辺の長さで定義される)が元のグラフと変わらない。 任意…

AOJ 1330 Never Wait for Weights

AOJ

問題 Never Wait for Weights | Aizu Online JudgeN 個の頂点があり, 各頂点には W[i] という特徴量がある。次の二つのクエリが与えられるので適切に処理せよ。 W[b] - W[a] = w という情報が与えられる。 a, b を与えるので, 今までの情報で W[b]-W[a] が求…

AOJ 1138 Traveling by Stagecoach

AOJ

問題 Traveling by Stagecoach | Aizu Online Judge 解法 bitDP 的なダイクストラやるだけ。 const int MAXN = 8; const int MAXP = 1000; const int MAXM = 33; const double INF = 1e18; int T[MAXN]; int dist[MAXM][MAXM]; double dp[MAXM][1<<MAXN]; int main() { int n, m, p, a, b; while (cin >> n >> m ></maxn];>…

AOJ 2224 Save your cats

AOJ

問題 Save your cats | Aizu Online JudgeN 頂点, M 辺の平面グラフが与えられる。平面グラフの面の数が 1 になるように辺を破壊したい。これを達成する最小コストを求めよ。 解法 下のスライドの前半を読めばすべてを察することができます。 平面グラフと交…

AOJ 2369 CatChecker

AOJ

最近のんびり過ごしています。 問題 CatChecker | Aizu Online Judge 解法 区間 dp をします。dp[l][r] = (区間 [l, r) が猫の鳴き声文字列になっているか?)というのを判定します。これは, s[l] = 'm', s[r-1] = 'w' s[m] = 'e' の時, dp[l+1][m-1], dp[m+1…

AOJ 2201 Immortal Jewels

AOJ

問題 Immortal Jewels | Aizu Online Judge 解法 ある最適な直線があったとします。この直線を少し動かしても結果は変わりません。結果が変わる直線の動かし方は, その直線が ある円の内部を貫くか, ある円の中心からの距離が Ri + Mi となるときです。なの…

AOJ 1295 Cubist Artwork

AOJ

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

AOJ 2403 The Enemy of My Enemy is My Friend

AOJ

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

AOJ 2629 Manhattan

AOJ

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

AOJ 2402 Milky Way

AOJ

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

AOJ 2312 Magical Girl Sayaka-chan

AOJ

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

AOJ 1182 Railway Connection

AOJ

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

AOJ 1132 Circle and Points

AOJ

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

AOJ VolumeACPC2015Day1 D : Checkered Pattern

AOJ

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

AOJ 2200: Mr. Rito Post Office

AOJ

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

AOJ 2022: Princess, a Cryptanalyst

AOJ

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

AOJ 1196: Bridge Removal

AOJ

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

AOJ 0519: Worst Reporter

AOJ

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

AOJ 2511 Sinking islands

AOJ

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

AOJ 2510: 双子の読書感想文

AOJ

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

AOJ 1168: ぐらぐら

AOJ

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

AOJ 1157: 大玉転がし

AOJ

問題 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-…

AOJ 1181: 偏りのあるサイコロ

AOJ

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

AOJ 2642: Dinner

AOJ

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

AOJ 2441: FizzBuzz

AOJ

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

AOJ 2640: Prowler

AOJ

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

AOJ 1175: そして,いくつになった?

AOJ

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

RUPC Day1 F : Relay

AOJ

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

AOJ 1178 A Broken Door

AOJ

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