ferinの競プロ帳

競プロについてのメモ

AOJ

バグ記録

AOJICPCを解いてたら思ったより手こずったのでその反省 AOJ2904 GuruGuru RLLLRRR みたいなのを数えて1WA 問題文に書かれていることをちゃんと書く AOJ2846 Slimming Plan 1週目だけで達成できるパターンを忘れてた 二分探索の結果が oxxxxxoooooo みたいな…

AOJ2632 Dense Amidakuji

問題ページ 解法1 横棒の消去を無視すると周期 で同じ列に戻ってくる.ある横棒 を消す場合,その横棒の左端/右端にくる列が何列目なのか求め,その位置をswapする.左端/右端にくる列を求めるには,0列目/w-1列目に当たるまで上に戻るを繰り返すことで で求…

AOJ2749 ぼくのかんがえたさいきょうのおふとん

問題ページ ぬくもり需要 をソートしておくと,おふとんを増やす操作のみに置き換えられる.したがっておふとんを積む順番は記録せずに,使ったおふとんの集合だけ記録すればよくなる. 日目使った布団の集合 最小の不快度の和としたDPを考える.このDPの遷…

aoj2397 Three-way Branch

問題ページ 障害物がなければ行列累乗をすればよい.障害物に対応するため障害物が存在する行ごとに区切って考える.行列累乗で 列目に到達する方法を求めたあと,障害物が存在する位置に到達する方法を0通りに置き換える. で解けた. #include <bits/stdc++.h> using name</bits/stdc++.h>…

AOJ2256 ケーキ分割問題

問題ページ 直線 上の点 を決めたときに, 上のどの位置に点を置けば2等分できるか? を原点として 点を偏角でソートする.このとき 番目と 番目の点の間を通るような線分を引くと,2等分することができる. と 番目の点を結ぶ線分が のときに取る 座標 から…

AOJ2376 DisconnectedGame

問題ページ 連結成分が2個のグラフが与えられたときを考える.各連結成分の大きさを ,辺の数を とすると,操作できる回数は 回である.よって,この回数の偶奇でどちらが勝つか判定することができる. の偶奇は で判定でき,0もしくは1のときは偶数で,2も…

AOJ2401 Equation

問題ページ 解法 変数は高々10種類なので'T'と'F'の割り当ては2^10通りしかない。=で分割しておけばequationを用意する必要はない。構文解析はO(|S|)でできるので割り当てを全通り試して等しくならないものがあれば'NO'、そうでなければ'YES'を出力する。以…

AOJ2613 Unordered Operators

問題ページ 解法 まず演算子の優先順序が*>+>-となっている場合のBNFを書いてみる。左再帰と演算子の優先順序に気をつけつつ書くと以下のようになる。 <expr1> = <expr2> ['-' <expr2>]* <expr2> = <expr3> ['+' <expr3>]* <expr3> = <factor> ['*' <factor>]* <factor> = '(' <expr1> ')' | <number> 他の優先順序の場合についても同様にBNFを書ける。</number></expr1></factor></factor></factor></expr3></expr3></expr3></expr2></expr2></expr2></expr1>…

AOJ2236 Rabbit Plays Games!

問題ページ Rabbit Plays Games! | Aizu Online Judge 考えたこと 項目が多すぎるのでまとめたい まず敏捷sについて関係あるのは自分より早く動くか遅く動くかだけ 敏捷の差とか考えたくないので無視したい 戦闘前に自分より早く動くやつにダメージをもらう…

AOJ2596 Points and Lines

問題ページ Points and Lines | Aizu Online Judge 考えたこと BNFがパッと目に入って明らかに構文解析 幾何の操作がBNFの形で与えられるのでその結果を求める 幾何の操作は2点から直線を作る操作とreflectionと直線の交点 割と単純な操作でライブラリを貼れ…

AOJ2712 Escape

問題ページ Escape | Aizu Online Judge 考えたこと 閉路が存在すればそこでUターンできる つまり1->閉路->1みたいな移動ができる 閉路にたどり着くまでの頂点は必ず訪れることができる 閉路の先にある頂点の集合は最後に取ることしてどれか一箇所しか取れな…

AOJ2784 Similarity of Subtrees

問題ページ Similarity of Subtrees | Aizu Online Judge 考えたこと 各頂点xを根とした部分木について配列v_xを考える v_x[i]=(深さiの頂点数)とする v_xが等しければその部分木は等しい v_xが等しい頂点の数がa個であればa(a-1)/2個の条件を満たすペアがあ…

AOJ2447 A Two Floors Dungeon

問題ページ A Two Floors Dungeon | Aizu Online Judge 解法 制約を見るとSがかなり小さい。盤面の状態の変化を全て持つと2^(50*50)で明らかに持てないがスイッチのON/OFFの全通りの2^Sであれば十分持てる。こうすると d[スイッチの状態][x座標][y座標][何階…

AOJ2741 インビジブル

問題ページ インビジブル | Aizu Online Judge 考えたこと ゲーム系だけど制約が小さいので全探索系っぽい minmaxをする感じで考える 持ちたい状態を考えると山札の何枚目を見ているか、スタックに何枚あるか、どっちのターンかあたり スタックにある枚数を…

AOJ2606 Perm Query

問題ページ Perm Query | Aizu Online Judge 解法 各iについて周期が高々40以下といういかにも使えと言っている制約があるので使う。各iについて周期がcnt[i]、1周期でretに加算される合計をsum[i]とする。すると各iを繰り返す回数は区間[l,r]のcnt[i]のlcm…

AOJ1350 There is No Alternative

問題ページ There is No Alternative | Aizu Online Judge 解法 ある最小全域木Tの辺をひとつ交換して構成できる全域木が最小全域木であれば、その辺はno alternative bridgeではない。ある辺を除去したときに代わりに加えたときに全域木になる辺を列挙した…

AOJ1246 Concert Hall Scheduling

問題ページ Concert Hall Scheduling | Aizu Online Judge 考えたこと 区間が飛んでくるのでとりあえず終端でソートする 区間が3つ以上かぶるような日があるとだめ 今までに選んだ区間ですでに2つかぶっているような日が存在 その日よりも始点が前の区間を使…

AOJ 2306 Rabbit Party

問題ページ Rabbit Party | Aizu Online Judge 考えたこと 入力がグラフっぽい グラフとしてサンプルを書いてみるけどグラフの知ってるもの(最大安定集合とか)に帰着できない DPを考える dp[i匹目まで][j匹選んだ] みたいなの 今までに選んだうさぎの部分集…

AOJ1604 デッドロック検出

問題ページ Deadlock Detection | Aizu Online Judge 考えたこと とりあえずサンプルを読む あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック あるuから次のuまでに同じ数字が2回以上出てくる→デッド…

AOJ2585 一日乗車券

問題ページ 1 Day Passport | Aizu Online Judge 考えたこと とりあえず入力で何がくるのかちゃんと読む 会社の数の制約が小さい dp[S] = (会社の集合Sを乗り放題にするために必要な最小コスト) を求めておく これは簡単なbitDPでできてO(2^KP) 会社の集合S…

AOJ1330 Never Wait for Weights

問題ページ Never Wait for Weights | Aizu Online Judge 考えたこと bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる 重さの差を測るクエリ…

AOJ2200 Mr. Rito Post Office

問題ページ Mr. Rito Post Office | Aizu Online Judge 考えたこと 人がx、船がyにある状態を(x,y)と書くことにする ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(…

AOJ2642 Dinner

問題ページ Dinner | Aizu Online Judge 考えたこと すべての日で自炊するとする このときの幸福度は簡単に求まる ある日を自炊から外食に変えると変化する幸福度は(外食の幸福度)-(その日の自炊の分)-(その日以降で自炊する日数)*(定数) i日目以降で自炊をj…

AOJ2310 薔薇園の魔女

問題ページ Rose Garden Witch | Aizu Online Judge 考えたこと 左下からの線分の偏角を微小量dtごとに変化させて全部試すみたいな解法を考える 判定部分でdfsでO(HW)かかるのでとてもじゃないけど精度がたりなさそう 線分を引く位置はどうせ少ないとかがな…

AOJ2510 双子の読書感想文

問題ページ Twin book report | Aizu Online Judge 考えたこと まず本を読む時間を最小化することを考える 感想を書く時間を無視して読書にかかる時間の方だけ考える とりあえずソートしたい気持ちになる いろいろ試してると大体 sum(r) で読書が終わりそう …

AOJ1318 long distance taxi

問題ページ Long Distance Taxi | Aizu Online Judge 解法 拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。 d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。 入力が面倒だっ…

AOJ0343 プログラミングコンテスト II

問題ページ Programming Contest II | Aizu Online Judge 解法 (点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧して…

AOJ0570 ジグザグ数

問題ページ ジグザグ数 | Aizu Online Judge 考えたこと 桁DPなのは知ってたので桁DPを考える dp[i桁目][B以下が確定か][mod M][最後に選んだ数][ジグザグ数になってないか上昇か下降か] を書く mod Mを上の桁から取るのが面倒そうだけどよくよく考えると mo…

AOJ2304 Reverse Roads

問題ページ Reverse Roads | Aizu Online Judge 考えたこと 有向グラフの辺を反転することでs-tフローを最大化する 与えられた辺を無向辺のように扱って両方の向きに辺を張ってフローを流す 最大フローの値はこれで求まる 反転すべき辺を求めるのには残余グ…

AOJ2382 KingSlime

問題ページ King Slime | Aizu Online Judge 考えたこと 縦横で同じ軸にいるスライムは移動1回でくっつけられそう sample1を見ると縦横で同じ軸にいるスライムをつないでいってその連結成分にいるスライムは移動1回でまとめられそう つまり(連結成分の大きさ…