hogloidのブログ

へなちょこ

個人的良問リスト

少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます
良問、というより解く価値のある問題、といった方が正確かもしれません
2ヶ月ごとぐらいにアップデートする予定です
問題のリンクが貼ってあり、右に白い文字で解法の要素が単語で書いて有ります(マウスで囲うと見えます)
解法の要素は自分にわかるように作ったので不明な点があるかもしれません
☆は僕が初見では解けなかった問題たちです
一部、キーワードが変なひらがなになってるのがありますが、それははてなのキーワードに引っ掛けないためです

キーワードのみではわからないのも多いと思うのでなんか気になったら聞いてください(僕は全部解いているはずです)

問題たちには偏りがあります。今のところCF,USACO,Polish OIがほとんどです

誤解を招きそうな表現-> O(N)は問題の本質部分がO(N)で解けるということを言ってて、全体の計算量がO(N)というのを示すわけではないです


http://www.codeforces.com/contest/258/problem/D 確率 DP 数学 ☆
http://www.codeforces.com/contest/193/problem/D segment木 クエリ ☆
http://www.codeforces.com/contest/121/problem/E 平方分割・クエリ
http://www.codeforces.com/contest/191/problem/D サボテングラフ ☆
http://www.codeforces.com/contest/183/problem/D DP 確率 ☆
http://community.topcoder.com/stat?c=problem_statement&pm=12378&rd=15487 貪欲 文字列 辞書順
http://community.topcoder.com/stat?c=problem_statement&pm=12379&rd=15487 DP 指数時間 ☆
http://www.usaco.org/index.php?page=viewproblem2&cpid=225 UnionFind
http://www.usaco.org/index.php?page=viewproblem2&cpid=229 O(N) しゃくとり法
http://www.usaco.org/index.php?page=viewproblem2&cpid=231 セグメント木 set クエリ
http://www.codeforces.com/contest/264/problem/D 数学 文字列 数え上げ O(N) ☆
http://www.codeforces.com/contest/264/problem/E セグメント木 LIS ☆
http://www.codeforces.com/contest/261/problem/C DP ふらくたる
http://www.codeforces.com/contest/261/problem/D LIS DP ☆
http://www.codeforces.com/contest/261/problem/E 素数 DP しゃくとり ☆
http://www.codeforces.com/contest/266/problem/E セグメント木 ☆
http://www.codeforces.com/contest/269/problem/D セグメント木 区間 DP
http://www.codeforces.com/contest/269/problem/C グラフ
http://main.edu.pl/en/archive/oi/19/fes 牛ゲー 不等式 最短路
http://main.edu.pl/en/archive/oi/19/lit 文字列 交換 BIT
http://main.edu.pl/en/archive/oi/19/odl 素数 グラフ 幅優先
http://main.edu.pl/en/archive/oi/19/tou グラフ lowlink 貪欲 O(N) ☆
http://main.edu.pl/en/archive/oi/19/bon 調和級すう 素数
http://main.edu.pl/en/archive/oi/19/sza DP 走査 クエリー 先読み
http://main.edu.pl/en/archive/oi/19/squ 貪欲 ☆
http://main.edu.pl/en/archive/oi/19/wyr 貪欲 数学 階差 ☆
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho4 二分探索 文字列 ☆
http://joi2013ho.contest.atcoder.jp/tasks/joi2013ho5 セグメント木 平面 ☆
http://main.edu.pl/en/archive/oi/19/hur 貪欲 セグメント木
http://community.topcoder.com/stat?c=problem_statement&pm=12364&rd=15488 DFS 数え上げ ☆
http://www.codeforces.com/contest/273/problem/C グラフ 貪欲 ☆
http://www.codeforces.com/contest/273/problem/D 数え上げ DP imos法 ☆
http://www.codeforces.com/contest/273/problem/E DP ゲーム Nim 埋め込み
http://www.usaco.org/index.php?page=viewproblem2&cpid=248 imos法
http://www.usaco.org/index.php?page=viewproblem2&cpid=249 DP 実装注意
http://main.edu.pl/en/archive/oi/19/pre 貪欲 しゃくとり 文字列 ハッシュ☆
http://main.edu.pl/en/archive/oi/18/kon 貪欲 グラフ 数え上げ ☆
http://main.edu.pl/en/archive/oi/18/pio スタック 二分探索 ☆
http://main.edu.pl/en/archive/oi/15/pod 高速化 指数時間 省メモリ
http://main.edu.pl/en/archive/oi/15/tro 幾何 数学
http://main.edu.pl/en/archive/oi/15/kup グリッド スタック ☆
http://main.edu.pl/en/archive/oi/18/prz 貪欲
http://main.edu.pl/en/archive/oi/18/sej 素因数ぶんかい imos法?
http://www.codeforces.com/contest/280/status/D セグメント木 ☆
http://main.edu.pl/en/archive/oi/18/rot 木 logマージ BIT ☆

  • 追加 5/5

http://www.codeforces.com/contest/280/problem/C 木 確率
http://main.edu.pl/en/archive/oi/18/imp 貪欲 ☆
http://main.edu.pl/en/archive/oi/18/met BIT 二分探索
http://main.edu.pl/en/archive/oi/18/pro フロー 貪欲 X最小費用流 ☆
http://main.edu.pl/en/archive/oi/17/kor 調和きゅうすう ローリングハッシュ
http://www.codeforces.com/contest/283/problem/C DP
http://www.codeforces.com/contest/283/problem/E セグメント木 数え上げ ☆
http://joisc2013-day3.contest.atcoder.jp/tasks/joisc2013_cake 分割統治 実はO(NlogN) or セグメント木 ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_communication グラフ 木 Union-find 隣り合ったものがすべて繋がっていればOK ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_collecting セグメント木 包除 数え上げ
http://joisc2013-day2.contest.atcoder.jp/tasks/joisc2013_mascots DP 数え上げ 縦に伸ばす・横に伸ばす のみで十分
http://main.edu.pl/en/archive/oi/17/klo O(N) ☆ 取りうるものは階段上になる一部のみ
http://www.codeforces.com/contest/277/problem/E 最小費用流 O(N^3logN)
http://main.edu.pl/en/archive/oi/17/owc 円環 しゃくとり DP O(N^3)
http://main.edu.pl/en/archive/oi/17/tel 貪欲 グラフ O(N+M) ☆
http://www.codeforces.com/contest/286/problem/A 実験 O(N)
http://www.codeforces.com/contest/286/problem/B 調和きゅうすう ほとんどの場所は動かない O(NlogN)
http://www.codeforces.com/contest/286/problem/D 区間 重複を取り除く->イベント O*1
http://main.edu.pl/en/archive/oi/16/gas 木 貪欲 葉から貪欲に切り離す O(NK)
http://main.edu.pl/en/archive/oi/16/baj 回文の中心を決めて、幅優先。2ステップ一気にやろうとするとTLE O(NM+DM)
http://main.edu.pl/en/archive/oi/16/kon DP 1ステップに複数の移動候補がある方が、却ってメモリ面で優秀 O(N^2K)
http://main.edu.pl/en/archive/oi/16/arc リスト 省メモリ STD::リスト使える (広義)減少列に分割して、それぞれのステップで消すのは最初の減少列の最後 いれれーたで頑張る ☆
http://main.edu.pl/en/archive/oi/16/lyz セグメント木 ある区間の和が、区間の長さをD増やしても入らないならOUT と言い換えられる O((n+m)log n) ☆
http://main.edu.pl/en/archive/oi/16/slw 文字列 検索 貪欲? f^k(0)に含まれるなら、f^(k-1)(0)で 求められる文字列も定まる これをk=0になるまで繰り返す。途中で0が挟まったりするとアウト ☆
http://main.edu.pl/en/archive/oi/16/wsp 幾何 貪欲 スタック ある街からは、そこから一番首都側にいける辺以外は使う必要がない 最初は円環状に回るのをどんどんショートカットしていく感じ O(n+mlogm) ☆
http://main.edu.pl/en/archive/oi/15/blo dfs lowlink 関節点のみ、自明コスト以外に足す必要がある low[dst]>=pre[v] のとき、dstの先は上に戻れないので、通る必要のある組み合わせをたす O(E)
http://main.edu.pl/en/archive/oi/15/rob BFS imos法 タコ型状なので、上と下に分割する。上に凸な三角形っぽいものに分割すると、上から平面走査していき、一番後まで邪魔になるのは一番下にあるX これを利用してimos法などを使い、どこに入れないかを求める。 あとはBFSだけ O(N^2) ☆
http://main.edu.pl/en/archive/oi/15/bbb デック スライド最小値 累積和 k回revolveした時を考えると、その時預金額が最も少ないときから、いくつ変更するかが分かる O(N)
http://www.codeforces.com/contest/295/problem/D 数え上げ DP imos法 dp[高さ][幅] で、ピラミッド状の形をいくつ作れるかを数える 遷移で、一次関数状に値が増える感じの足し方をするが、imos法を2回やればOK caveの形は、最後の膨らんだところで分割して、ここでも多重imos法を使ってがんばる O(NM)
http://www.codeforces.com/contest/295/problem/E DP セグメント木 座標圧縮 列で持たずに、どこの場所がONになってるかを考える 更新も、(左ノードのコスト)+(左ノードが左の右端まで行く値)*(左ノードの数)+(左ノードの数)(右ノードの数)(左と右の間隙) ... のようにすればいける O(MlogN)
http://www.codeforces.com/contest/150/problem/E 木 セグメント木 重心分解 二分探索 定数倍  中央値k以上にできるか、という二分探索をする。 パスの中で、上方に寄与する辺が半分以上ならよい。 重心分解をして、重心からの距離がある範囲の中で最大に上方に寄与する頂点を求めたくなる。これはセグメント木で実現できる O(Nlog^3n) logはひとつ外れる。
http://main.edu.pl/en/archive/oi/14/drz セグメント木 コスト付けで問題になるのは それ自体の値、左、右の値 交換先の木の高さをxとして隣接する2つのコストの和のグラフを作ると、3つのパートから成る。  木の高さでソートし、 常に、交換相手にとって交換する木が、3つのパートのどこに位置するかを持っておく。 また、交換する木にとって相手が3つのどのパートにあるかも場合分けして求める。 これらをセグメント木を使って行う。 端の場合・隣接する2つを交換する場合に注意。 O(NlogN)
http://main.edu.pl/en/archive/oi/14/grz φ関数 整数 φ(k)*(a/k)*(b/k) の合計を求めることになる。 kを1...√b まで調べ、そのあとはb/kの値別に、kが√b以上のものを調べる。 O(N*B^0.5)
http://main.edu.pl/en/archive/oi/14/grz 素因数ぶんかい 文字列 クエリ 長さLの範囲のとき、Lの素因数について独立に切れるかどうか考えればよい また、Kの長さでに切れるかどうかは、 [0,L-K)==[K,L)を調べればよい O(NloglogN+QlogN)

POIとかむっちゃ難しいのでちゅうい
良問の基準も人によって違うので注意しましょう 僕は比較的甘いほうだと思うのでそこまで良くないのも混ざってるかもしれません

*1:Q+N)*log(Q+N