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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ

AOJ2594 Reverse a Road Ⅱ

AOJ

この問題好き 問題文 Reverse a Road II | Aizu Online Judge久々に訳書きます 有向辺グラフとスタート,ゴールが与えられる. スタートからゴールまで,道が一つも被らないルートが最大でいくつあるか求めたい(頂点は被ってもよい) ただし,一つの辺だけ…

AOJ2638 Hyperrectangle

AOJ

考察に3時間ぐらいかかった気がするのでコンテスト中に解けなさそう... 問題文 Hyperrectangle | Aizu Online Judge 解法 まず,全てのについての場合について考えると,2次元なら長さsの正三角形,3次元なら正三角錐,,,d次元の正三角錐(三角錐かどう…

AOJ2312 魔法少女さやかちゃん

AOJ

多分勉強会の問題の中で開いてから解くまでが最速だった.(これは罠で,日本語の問題だからという説がある 問題文 Magical Girl Sayaka-chan | Aizu Online Judge 解法 輪というのが考えにくいのでなんとか区間というか数を一列に並べる問題にならないか考…

AOJ2538 Stack Maze

AOJ

勉強会の問題がICPCっぽく(悪い意味で)なってまいりました. 問題文 Stack Maze | Aizu Online Judge 日本語訳が欲しい方は「mayoko stack maze」とかで検索するとよいです. 解法 最初に思いつくのはdp(r,c,今持っている宝石のスタック)というDPだと思い…

AOJ2296 Quest of Merchant

AOJ

頑張るだけ 問題文 Quest of Merchant | Aizu Online Judge 解法 色々眺めていくとナップサック以外考えられなくなると思うのでナップサックで考える. まず初めの考察として,原点から出発して再び原点に返ってくる操作を1セットとできそう.では1セットに…

AOJ2224 Save your cats

AOJ

薔薇園の魔女に比べたら11454倍楽 問題文 Save your cats | Aizu Online Judge 解法 閉路を含まなくするためにできるだけ少ない長さの辺を削りたい. すなわち,できるだけ辺の総和が長くなるように閉路を含まないグラフを作りたい よって最大全域森を作れば…

AOJ2310 薔薇園の魔女

AOJ

二度と解きたくない 問題文 Rose Garden Witch | Aizu Online Judge 解法 全探索をします. といっても直線を引く候補が無限個あるので,少し考察をします.最適解の直線があったとして,分割する数を減らさないように少しずつ直線の角度をずらしていくと,…

AOJ2168 Luigi's Tavern

AOJ

マッチングかー,フローっぽいなあ,どう見てもフローじゃん みたいな感じだった 問題文 Luigi's Tavern | Aizu Online Judge 解法 パーティーを沢山作りたいので,各パーティーに役職はそれぞれ高々一人でいいことが分かります. それで,人を頂点,友好関…

AOJ2305 Beautiful Currency

AOJ

Beautifulのスペルが覚えられないのは私だけじゃないはず. 問題文 Beautiful Currency | Aizu Online Judge訳は載せませんが,美しい通貨群にするために必要な各々の変動レートの"最大値"を求める問題です. 総和と勘違いしてサンプルが合わず丸一日悩みま…

AOJ2326 Number Sorting

AOJ

問題文 Number Sorting | Aizu Online Judge 解法 制約を見ると, という怪しい制約があるので,とします. まずこの時点で想定解法はかとかその辺を疑います.(桁DPの可能性もありますがこの制約である必要があまりなさそうなので切り捨てました.)小さい…

AOJ1302 Twenty Questions

AOJ

SRM694Div1Med「Distinguishable」に似ていたので誤読をした(というより同じ問題だと思ってしまった.) 問題文 Twenty Questions | Aizu Online Judge 例によって日本語訳はないです. 解法 どんなオブジェクトも与えられた質問によって一つに特定できるこ…

AOJ1330 Never Wait for Weights

AOJ

問題文 Never Wait for Weights | Aizu Online Judge 日本語訳は他の方のブログ見てください 解法 !を頂点の連結クエリ,?を連結成分内のrankの差を取得するクエリとしてみてみましょう. Union-Findしたい気持ちになってくると思います. Union-Findについ…

AOJ2333 僕の友達は小さい

AOJ

問題文がなかなかキチってて好き 問題文 My friends are small | Aizu Online Judge 解法 ナップサックで解けそうな気がしてくるので,DPで考えてみます. すると,(選んだ友人の高さの合計)が選んでない人の高さの最小値未満なら条件を満たすことが分かると…

AOJ2222 Alien's Counting

AOJ

最近出次数1のグラフ問題やりすぎて慣れてしまった 問題文 Alien's Counting | Aizu Online Judge 解法 出次数が高々1という制約があるので TopCoderのSunny Graphと同じように考えると,一つの連結成分は1つの単純閉路といくつかのパスを繋げたような形にな…

AOJ2200 Mr. Rito Post Office

AOJ

ICPC国内予選の過去問ですね 実は去年解いた記憶があります(まあ去年は青コーダーでしたし激遅だったのでいい復習になりました 10分で解きたい問題 問題文 Mr. Rito Post Office | Aizu Online Judge 解法 あらかじめ,陸路のみ,海路のみの全頂点間最短路…

AOJ2306 Rabbit Party

AOJ

問題文 Rabbit Party | Aizu Online Judge 解法 全然関係ない話をすると,グループに含まれる頂点集合からなる完全グラフのMSTのスコアがそのままそのグループのスコアになる(本当に関係ない)グループが既にあったとして,そのグループに一人追加すること…

AOJ1132 Circle and Points

AOJ

問題文 Circle and Points | Aizu Online Judge 解法 ある点群を囲っている単位円について考えると,円から点がはみださないように円を動かしたとき,やがて円と2点がぶつかる. このことから,いずれか2点がギリギリ円に含まれている全状態を考えれば漏れな…

AOJ2425 全探索お姉さんの休日

AOJ

問題文 A Holiday of Miss Brute Force | Aizu Online Judge 解法 (x,y,t)の3状態からコスト0とコスト1の辺をもってダイクストラするだけ ただし,tは[tex:mod 6}で考えないと色々計算量が大変なことになるので注意注意点としては,x座標の偶奇で座標の遷移…

AOJ2441 FizzBuzz

AOJ

問題文 FizzBuzz | Aizu Online Judge 解法 コードを見ながら必死に解法を思い出しているのですが, まあ制約的に二分探索だとおもいます. 下の桁から丁寧に数え上げてやるとある数までにいくつ文字を出力したかがで求められるので,境界を求めてやってあと…

AOJ2382 King Slime

AOJ

問題文 King Slime | Aizu Online Judge 日本語訳は略 解法 個の頂点があったときに,それを1点に集合させるまでに必要な移動回数の下界は回でとなる. これは,各頂点からの移動を辺で表せば木となることから明らかである.というわけで,木を構成する方法…

AOJ2170 Marked Ancestor

AOJ

問題文 Marked Ancestor | Aizu Online Judge 日本語訳は他に書いてる人が沢山いるのでそちらをご参照ください 解法 便宜上,祖先を取得するクエリをQ,頂点をマークするクエリをMと略します.頂点に対するクエリQが飛んできたとき,何を求められればいいかを…

AOJ2182 Eleven Lover

AOJ

2進数における3の倍数の求め方と同じですよねこれ 問題文 Eleven Lover | Aizu Online Judge 80000文字以下の数字のみからなる文字列が与えられる. 連続した部分文字列について,10進の数字として先頭が0でないかつ11の倍数であるようなものの個数を求めよ…

AOJ2317 Class Representative Witch

AOJ

問題文,闇に包まれすぎ 問題文 Class Representative Witch | Aizu Online Judge 英語よりも辛いと思いますが問題文についての説明はしません() 解法 が成り立つとき,区間をとすると,値の小さいほうが使い魔の持つ端点として統一でき,魔女の座標は0に…

AOJ1320 City Merger

AOJ

問題文 City Merger | Aizu Online Judge n個の文字列が与えられる. 全ての文字を連続部分文字列として持つような文字列のうち,最小の長さを求めよ. 解法 nが14以下なのでbitDPを疑います. まず初めに,どの文字列がどの文字列を完全に含有しているかの…

AOJ2442 ConvexCut

AOJ

間違えてこっちの問題を解いて満足していたけどマヨ子さんのブログを見て違うことに気が付いた 凸多角形の切断 | 計算幾何学 | Aizu Online Judge 問題文 ConvexCut | Aizu Online Judge 解法 点Pが多角形に存在するとします. 多角形を点Pを通る2つの直線で…

AOJ2157 Dial Lock

AOJ

計算量の解析がよくできないシリーズ 問題文 Dial Lock | Aizu Online Judgek桁10進のダイヤル錠がある. 最初の状態と最終状態が与えられたとき,ダイヤルを回す必要のある最小の操作回数を求めよという問題です. ただし,1回の操作では,連続した桁を同…

AOJ2176 For the Peace

AOJ

多分英文を読解するのに一番時間を費やしたと思います(真顔) 問題概要 問題文:For the Peace | Aizu Online Judge個の国がある. 各国はそれぞれ威力の異なるミサイルを順に作る予定である. 世界の均衡を保つため,いかなる瞬間においても各国がもつミサ…

AOJ2383 Rabbit Game Playing

AOJ

とある勉強会に参加したので,そこで解いた問題の解説を暫くやっていこうと思います. 問題概要 問題文:Rabbit Game Playing | Aizu Online JudgeN個のゲームがあります.各ゲームには以上以下の難易度がつけられている. N個のゲームを順に全てプレイしたい…

AOJ 0068 - Enclose Pins with a Rubber Band

AOJ

趣向を変えてAOJの問題を解きます。 この問題で使うアルゴリズムが次に解く予定の問題に必要なので確認のために解きました - 問題概要 n個の釘のxy座標が与えられます。 すべての釘を一本の輪ゴムで囲んだとき、輪ゴムに触れていない釘は何本あるか。 - 解法…