AOJ-ICPC難易度表 600まとめ

上から,反省もこめて
Merry Christmas(2251)☆
transitiveDAGの二部マッチングのアレ

Reverse Sort(2443)
半分探索,知らなかったので勉強になった
ちなみに始め単にdfsという解法に固執しまくっていて2443という数字を覚えてしまい、後日(Code Formula?)snukeのeditorの2443.cppという番号を見てこの問題だと気づいた ということがあった

Dangerous Tower(2293)
割り当てはmin_cosst_flowだよなあ?
縦と横を割り当てようとするんじゃなくて積み木と数字を割り当てようとするのが重要(かぶってはいけないのは数字なので)

Malfatti Circles(1301)
なんだっけ・・・三角形にうまく接する3つの円を入れるんだけど、一個目の円としてでかいのを入れると二個目が小さく、三個目が大きくなるのでC1とC3の距離が近すぎるとなるので、二分探索を二重くらいですれば良い.なんか適当な場合を除いてなくてバグりまくった記憶が・・・

10歳の動的計画(2335)
カタラン数的な話を知っていれば解ける.DPじゃない・・・

Three-way Branch(2397)
[0,W)の範囲で右下か左下に行ける,左上から右下へ行く方法は何通り?という問題.行列累乗の合間に適当に行列を掛けるだけ.ちょっとTLEがつらいかもしれない.

ハコの魔女(2313)☆
ちょっとずつフロー変えてく典型.a->bをつける時は残余グラフで流すだけ,a->bを消す時は残余グラフでa->bに流せればそれでok,流せなければa->s,t->bと押し戻しておく.
辺が増えたり消えたりするので,オーダーに問題がなければ隣接行列でedgeを持ちましょう.非常に書きやすい.

箱根駅伝(2439)☆
最近追加された光り輝く天啓DP.問題設定,解法共に素晴らしい.
今見ているものを左にやったり右にやったりしなければいけないような問題では,"ここまで処理したうちでここに来れるのは何個か"と"ここまでで埋めてない奴は何個か"を持てばいい感じになることがある.更新は"こいつをどこに埋めるか,左から来たやつを使うか"みたいなことを考える必要がある.
"ここまでのunmatchedな個数"という考えはSRM592Div1Medの"LittleElephantAndPermutationDiv1"も参照.

Strange Couple(2171)
溢れ出るICPC臭.掃き出し法を書くだけ.連結成分以外をあらかじめ除くと楽.

Testing Circuits(2348)
自明な構文解析とおもいきやまさかのスタックオーバーフロー.自前stackを書きましょうという激ムズ問題.解説スライドによると問題作成者は構文解析後の自明問を解くのが本質だと思っていたようだが全くそんなことはない.悪問と言いたいけどまあ自前構文解析の練習にはなるのでやりたければやって,どうぞ.

舞台装置の魔女(2318)
かんたんなdp.

スプリング・タイル(2336)
e="バネを踏んだ後の期待値"でにぶたん.eが真の値より小さいとして解くとそれによって出てきたe'はeより大きい.として解いたんだけど何でだっけ・・・.
解説スライドを見ると,よく考えるとバネに向かうかゴールに向かうかの差は整数なのでH*W通りくらいしかなく、全部確かめれば良いという解法でも良かったらしい.

Enumeration(2446)☆
包除だとそれぞれのsubsetに対し,subsetの要素のそれぞれが選ばれるか試してΣ(x∈P(a)) |P(x)|=3^|a|かかる(Pは冪集合).

• >高速ゼータ変換

"iビット目まではsubsetになっていて、iビット目以降は一致している"の総和をdpで計算して、i=nの時の値を見ればok.

Sliding Block Puzzle(1329)
探索.他に言うことはない.

ケーキ分割問題(2256)☆
左の値y1を変えていく時,直線がどのイチゴの間を通るか,が変わるのはイチゴやケーキの端たちによる直線と左の線の交点.y1を上記が変わらないように動かしている間は取りうるy2の値の範囲は"線形に"変化することに気づけば,y1として真ん中の値をとって区間幅をかければいいことがわかる.

RabbitWalking(2370)
dpへの帰着後,間に合わないことに気づいて固まる.
和が2nくらいのn個の正整数値があって和として(n以下らへんで)どんな値が取れるかを調べるのは愚直にやればO(n^2)かかるが,正整数値がO(√n)種類くらいしか無い(∵√2n以上は√2n個程度,以下はそもそも√2n種類しかない)ことに気づけば個数制限ナップザックでO(n√n)になる.

IkaNumber(2372)
"入力はイカの形式で与えられる"
フィボナッチ数の積として表せるn番目の値は?Fa*Fbがa+bが大きいほうがでかい(Fa,Fb>=2)とかそんな感じのことに気づけば偶奇で場合分けして終わり.

Driving an Icosahedral Rover(1319)
正二十面体を紙を切って作り,遷移規則を打ちこむだけ.プログラミングではない.

Runaway Domino(2346)
線分にそって動いていくドミノ(の倒壊)を二つ止める問題.倒壊より速く動けるので,できるだけ速く止めれば良いしそれはにぶたんで求まる.

Card(2436)
それぞれの数字がどこに何回足されるか,がわかればよい.その数字以外j個でi桁の数が何通り作れるか,がわかればよい.dpするだけ.0に注意(0を除いた奴の答えを引けば良い).

Ropeway(2229)
この問題の本質はClarを投げることです!!!
問題文に制約が全く書いてないという激ヤバ問題.AOJに入っているのでClarを投げるのは難しい.これが評価されて600点問題になっている.Clarを投げたら(あるいは解説スライドの1ページめを見るなどしたら)あとはやるだけ.

Usoperanto(2456) →550点へ
自明DP.適当にやるとスタックオーバーフローするので、先にbfsでもして順序を決めておくと良い.これ400点位だと思うなあ.

Symmmetry(2159)
n個の点集合が線対称であるか,+例外処理.線としてはnC2個くらいあって、それぞれで全点確かめるとO(n^3)で通らない.線対称であるときはそういう線はn/2個位ある(重要)ので、線をO(n)回くらい乱択すれば間に合う.皆あまり通してないけど自明枠だと思う.

Reverse a Road II(2594)
フローの残余グラフ考えるだけ.

Square in Circles(2593)
しゃくとりは難しいのでにぶたんしような.

True Liars(1238)
点数が変わった.
DP+復元で,本来DPの時可能かどうかのboolしか持たなくていいところを,どこから来たか(未だfalseなら-1)とかを持っとくと楽に復元できる.

Flipping Parenthesis(1351)
()を+-1に置き換え.(→)の時はleftmostの)をflipでよい(そのために')'のidのsetを持つ.)→(の時は,qから左で,"[l,q]の区間に0,1がない"ような最小のlのところをflip(このようなlがs[l]='('を満たすのは簡単にわかる).このためにstarry sky treeを持てば良い.

Pattern Language(2604)
1桁,2桁目が最大,それ以外,の3^mすべて試す.毎回unionfindしてそれぞれの連結成分であり得る最小と最大を持てばできる.

Tree Reconstruction(2564)
式を書いてちょっと考えるだけ

Almost Same Substring(2614)☆
SとTが1文字違い⇔prefixの長さとsuffixの長さの和がN-1となる.Z-algorithmを使えば各S[i...S.size()-1]とTとのprefixがわかるので出来る.

Medical Inspection(2558)☆
探索むずい.K点以下の点カバーは1.4^K*K^2+KNくらいで求められる.(K^2のところはカーネライズ(見るべきところだけ絞る)によって出た分 wataさんの指数アルゴリズム入門のやつをみてください)

Snake(2635)
変な幾何,考えると各iに対して,i-1までとi+1からのそれぞれの凸包にiが含まれてない が必要十分だとわかる.

Iyasugigappa(2557)
変なゲーム.そもそもゲーム内容を理解するのがむずい(英語がむずい).実は理解しても結構面倒(完全に思い込み状態での手,を見ることで相手の手を予測し,それによって自分の手を決める,みたいなのが必要)

Tournament(2646)
segtreeっぽくやるだけだけど愚直に全部メモるとMLEするっぽいので何回も計算するとこだけをメモりましょう.

今のところこの23問→25→27になった.おもしろいのは箱根駅伝で、ためになるのはハコの魔女かなあ.
もうちょっと増えた.Almost Same Subtstring(っていうかZ-algorithm)がおすすめ,Medical Inspectionは別におすすめじゃないけど多分解けないとまずい.