コミックマーケット100参加します!(ファミコンエミュレータ本目次 & サンプル)
参加します!サンプルギリギリになってすみません!ファミコンエミュレータを自作する本です。おしながきは以下に貼ったツイの通りです。
エミュレータの実装のうち、コントローラ、カセット、CPU、PPU、APUの5つをそれぞれ解説してます。なかなか丁寧な解説になった & インターネット上で情報収集してて情報が足りず困った(特に APU)箇所を補完できる技術書になったと思いますので、メインの買い物のついでにお立ち寄りいただければと思います!
基本的には C/C++ がある程度書ける方を対象としていますが、ファミコンにおける各モジュールの挙動を解説してから実装に入るようにしていますので、ファミコン、ひいてはコンピュータがどう動いているんだろう?というところに興味のある方なら楽しんでいただけると思います。
【C100 お品書き】
— やむどぅ→C100一日目西す-12b (@ymduu) 2022年8月8日
1日目西す12b #edge_case お品書きです。
新刊「LayerWalker」ではファミコンエミュレータの実装方法を解説し、サウンド付きで某ゲームが遊べるようになるところまでをサポートします。https://t.co/cA1XXy2Jz3 pic.twitter.com/VwUD4CeQgQ
エミュレータ本体のリポジトリは以下になってますので、筋力がある人はこのコードを読み解くことでもエミュレータ作れると思います。(雑)
cmake でビルドできるようになっているので、 Visual Studio のソリューションを cmake で生成して Visual Studio でコード読んだりビルドしたりする想定です。
以下目次 & サンプルになります。簡単ですみませんが、当日はよろしくお願いします!
競プロでツイートしたものをスクラップする場所
名前がついてないけど典型っぽいやつ 置き場所だけ作る 適宜追記していく
N2 の区間全探索を高速化したい
N^2区間全走査を高速化するテクみたいなのをまとめると強かったりするかな、パッと思いつくあたりだと
— やむどぅ→技術書典13 (@ymduu) 2021年10月19日
- 単調性(二分探索 or しゃくとり)
- N個くらいに分類できてそのなかから端点を選べばよい(zero sum ranges)
- 変数分離(条件に区間長を含むパターンが多い)
くらい ほかにあるかな
- 実はN2のまま間に合う
- 単調性 で二分探索するときもあるあるだが、左端を固定して右端を全探索すると見通しがよい
- 高速化とは違うけど、これを忘れると茶diffでハマったりするので持っておこう
- Mandarin Orange https://atcoder.jp/contests/abc189/tasks/abc189_c
- TLと制約が厳しくて、logを付けると落ちるので、累積minしながら区間全探索するとよい
- 単調性
- なんかあるだろ、しゃくとりが使える問題全般
- Zero Sum Ranges 系
- https://atcoder.jp/contests/abc158/tasks/abc158_e
- Multiple of 2019 https://atcoder.jp/contests/abc164/tasks/abc164_d
- mod 2019 の世界で zero sum ranges やるだけ
- 変数分離 + 内側のΣを事前計算
- https://atcoder.jp/contests/arc116/tasks/arc116_b
- ソートすれば N2 区間全探索になる
- Rem of Sum is Num https://atcoder.jp/contests/abc146/tasks/abc146_e
- 条件に区間長を含むので、立式して変数分離 和が K を超えるときは NG になってしまうので注意
- This Message Will Self-Destruct in 5s https://atcoder.jp/contests/abc166/tasks/abc166_e
- 条件に素直に数列のインデックスを含む
- https://atcoder.jp/contests/arc116/tasks/arc116_b
- 実は特定の小さいケースだけみればよい
- アンバランス https://atcoder.jp/contests/arc059/tasks/arc059_b
- ある長さ4以上の文字列がアンバランスであるとき、かならずアンバランスな部分文字列
oo
かoxo
を含むので、長さ 2 or 3 だけ見ればよい - TODO: 大きいケースは小さいケースに何かを付け足したもの であるので、小さいケースに帰着できる みたいなのは典型な気がするけど抽象化がうまくいっていないので、いつか抽象化する
- ある長さ4以上の文字列がアンバランスであるとき、かならずアンバランスな部分文字列
- アンバランス https://atcoder.jp/contests/arc059/tasks/arc059_b
- 寄与
- https://atcoder.jp/contests/abc091/tasks/arc092_b?lang=ja
- これ寄与かな……(?)
- Second Sum https://atcoder.jp/contests/abc140/tasks/abc140_e
- これは完全に寄与、ある x が2番目になる区間がいくつあるかを数え上げる。 "自分より大きいもの"のインデックスがわかれば計算できるので、これは大きい順に index を set に入れていくことで計算できる(更新順を工夫)
- ↓の制約が2つ にも該当(Pi の値が x より大きい && i に一番近いインデックスのものを検索)
- https://atcoder.jp/contests/abc091/tasks/arc092_b?lang=ja
- 制約(不等式とか)が二つ -> 片方を処理順 もう片方をデータ構造で解決
数え上げたい対象に制約が2つある → 片方の制約を処理順で解決、もう片方をデータ構造で解決 の教訓が活かされたところだけよかった
— さはら (@shr_pc) 2019年8月4日
- 後述の 更新順を工夫する のサブセット(そのものかも)、処理順をうまくすることで一つ目の制約を満たすものしか含まれない世界を作り、データ構造で二つ目の条件を満たすものを数え上げるイメージ
- その他
- https://atcoder.jp/contests/abc150/tasks/abc150_e
- なんか最終的に二重Σが出てくる wolframalpha に投げると1重になる(は?)
- https://atcoder.jp/contests/abc150/tasks/abc150_e
区間 * 大量が与えられた
区間もしくは締め切りがたくさんある
区間や締め切り(例: 時刻tまでに終わらせなければならない仕事)がたくさん与えられたら区間スケジューリング問題的な貪欲を疑う
区間 * 大量を見たら終端でソートする、という典型があるが、それ
締め切りがはやいものを選ぶと後に残せる選択肢が多くなる、という気持ちらしい
知ってれば簡単だからか難易度のわりにdiff低くなりがち、気づけないとガチャガチャやっても解けないので破滅の原因になりがち(個人の感想)
亜種として大量の区間を全部切る Islands War がある(TODO: 書く)
- Megalomania https://atcoder.jp/contests/abc131/tasks/abc131_d
- 締め切りが近い順にしばくのが最適
- 7 https://atcoder.jp/contests/abc225/tasks/abc225_e
連続部分列を取る操作、連続部分列に関する情報が与えられている
連続部分列を取る操作をグラフの辺とみなす
- 操作で[l, r)の連続部分列(部分文字列)を取るとき、 l -> r のような有向辺を追加したグラフを考えるとよいことがある。
- Strings of Eternity https://atcoder.jp/contests/abc135/tasks/abc135_f
- 上記考察をすると、有向グラフの最長パスを求める問題になり、これは有名問題(トポロジカルソート + DP でとける)
- Range Sums https://atcoder.jp/contests/abc238/tasks/abc238_e
- 累積和上で考えると2点関係になる -> グラフと発想できるが、連続部分列を辺とみなす の気持ちでいると思いつきやすいかも、本番では未証明でエスパーしてグラフを作った人もいた様子
- Strings of Eternity https://atcoder.jp/contests/abc135/tasks/abc135_f
区間和が与えられた時も累積和(区間和を求めるときだけじゃない)
累積和の上で考えると区間和は2点関係になって、2点関係 * 大量 = グラフとみなす のテクがつかえることがある
- Range Sums https://atcoder.jp/contests/abc238/tasks/abc238_e
- 区間和 * 大量が与えられるが、累積和の上で考えると2点関係 * 大量 になってグラフの気持ちになれる
区間に対して加算したい
区間に対して加算したいときはセグ木、imos法などがよくあるが、それらは自明なので割愛
区間に対して加算したいが、インデックスの範囲が巨大(1e9とか)
インデックスの範囲が巨大なとき、セグ木に乗らず困ってしまう。座圧してもいいが、実装とデバッグが大変になりがち
問題によってはイベントソート(index, 加算値)のペアを保持してシミュレーションすることでうまくいくことがある。 変化点に着目 の亜種でもある
このとき、半開区間で処理するとうまくいく。(複数のイベントが同時に起こることがあるが、その区間は長さ0の区間として処理されるため)
- Snuke Prime https://atcoder.jp/contests/abc188/tasks/abc188_d
- 座圧 + imos でも解けるが、イベントソートなら実装が軽い。これくらいの問題を爆速で解けると勝ちやすいので……
- 座圧ってバグったときしんどいし……
DP
選択を繰り返す → DP
独立でない(過去の選択によって状況が変わる)選択を繰り返して最適化(例: 最小化、最大化)をするとき、保持しておかなければならない条件を添え字にした DP ができることがある(ナップザック問題とかもそうだな)
各選択が独立なら、各選択で最適なものを選ぶ貪欲法ができる
- Payment https://atcoder.jp/contests/abc155/tasks/abc155_e
- 貪欲したくなるけれど、すでに支払うべき値を超えているかどうかで分岐する必要があり、それを添え字にすることで解ける
貰うDP にすると都合がよくなることがある
とりあえず dp[S] := S -> T まで遷移するときのスコア なDPテーブルの定義をスクラップ行きにして、どういうときに使ったかをリストアップしたらなんか共通点とか見えてくるかな
— やむどぅ→技術書典13 (@ymduu) 2022年9月7日
初手はとにかく慣れてる & 一番素直に感じる 過去から配る で試してみる、ダメなら状態のスコアが未来に依存していないか、未来から貰うと楽にならないかを気にしつつ件の定義を使って 未来から貰う にしてみる かなあ
— やむどぅ→技術書典13 (@ymduu) 2022年9月7日
dp[S] := 状態 S に着くまでのスコア というのと dp[S] := S からゴールに着くまでのスコア という定義は意味としては同じだけど、遷移は違うので、貰うを配るにしたり配るを貰うにしたりすることができて、遷移の構造によっては片方の方が都合がいいことがある くらい?
— やむどぅ→技術書典13 (@ymduu) 2022年8月27日
そして今回なんで配るが苦しいんですか?と言われると、遷移グラフに自己辺があるせいで dp[i] から配りたいときに dp[i] の値が決定しておらず、つらいという感じで、貰うなら自分から貰うケースを式変形で潰すことができる
— やむどぅ→技術書典13 (@ymduu) 2022年8月27日
スタートから S までのスコアと S からゴールまでのスコアが常に意味として同じかというとそうではなさそうで、特に期待値とかの場合は S からゴールまでを求めたいときは S から行ける先からゴールまでのスコアさえあればいいけど、スタートから S までだと
— りあん (@rian_tkb) 2022年8月27日
スタートから S に来れる元のスコアだけではなくて「その状態にどれだけなりやすいか」みたいなのがないとスタートから S までのスコアが復元できない(逆に S からゴールまでという定義の場合はそこは気にしなくて済む)のが違い?
— りあん (@rian_tkb) 2022年8月27日
普段は dp[S] := 開始状態 Init から状態 S まで到達した時の最大スコア などとするが、 dp[S] := 状態 S から目標状態 T まで到達した時の最大スコア とすることで遷移を簡単に書けることがある。 多分要件は今の状態のスコアが未来に依存する(ゲーム) or 未来の状態で記述した方が楽(等確率に遷移する期待値の問題で、未来から貰うなら等確率なので楽だが、過去から配るならその状態に到達する確率を求めなければならないなど)とかなんだけど、どう使い分けるのがいいかはまだよくわかっていない
Sugoroku 3 https://atcoder.jp/contests/abc263/tasks/abc263_e
- dp[i] := i からゴールにいくまでにさいころを振る回数の期待値 とすると、自己辺の遷移が式変形で潰せたりiに止まる確率を考えなくてよくなったりしてらく
Game in Momotetsu World https://atcoder.jp/contests/abc201/tasks/abc201_d
- ゲームは1手先の評価値がわかっている必要があるので、こういう定義が刺さる
ゲーム → 後ろから DP
後ろから DP というのは難しく見えるんだけど、dp[S] := S から目標状態 T まで遷移したときのゲームのスコア(↑の一種) という貰う DP を書くと、各プレイヤーは S から遷移できる状態の中からスコアが一番よいものを選ぶ、という遷移が書けて解ける。
- Game in Momotetsu World https://atcoder.jp/contests/abc201/tasks/abc201_d
- スコアを高橋君の得点 - 青木君の得点 として、高橋君は最大化、青木君は最小化するような選択をすればよい。右と下の遷移先のスコアがわかっていれば、どちらが最適化は大小比較で求まる。
DP の更新を時がくるまで保留したい
更新に影響が出るのが嫌なのであるタイミングまで更新を保留したい -> 更新したくなるまで何かに差分を貯めておけ
— やむどぅ→技術書典13 (@ymduu) 2021年10月23日
- https://atcoder.jp/contests/abc224/tasks/abc224_e
- 考察すると、a の降順に r と c のそれぞれの最大値を更新していけばいいという気持ちになるが、 a が unique でない かつ問題の条件より、同じ a を見ている間は dp テーブルを更新したくない。 差分を貯める nr, nc を用意して、ある a についての処理が終わった後に差分を適用する。
桁 DP で leading-zero が許容されない時のテク
桁 DP で leading-zero が許容されないとき、以下の点に注意する必要がある。以下、すでに小さいことが決まっているかのフラグを smaller と呼ぶ。1-indexed。
- 左から 1 桁目を決めているとき、0を使ってはならない。
- 配る DP をしているとき、条件が i + 1 == 1 の時 になることに気を付ける(i は i 桁目まで決定しているときを表す)
- 2 桁目以降のとき、そこから始めることができる。
- 実装上は 2 桁目以降なら入れられる任意の値を smaller = true で入れてよい、とするのがらく。
- 実装例
- Variety of Digits https://atcoder.jp/contests/abc235/submissions/28568786
順列全探索高速化 → bitDP
順列全探索を要求されるが N=16 のとかのとき。末尾だけ など限定された属性が次の状態に影響するとき、今まで訪れた集合と末尾だけ保持して状態数を圧縮する。「過去を忘れる」
TSP の bitDP とかそんな感じだけど、キモは 順列 → 集合 + 追加情報 にすることで順列に含まれていた順番情報を忘れて状態数を圧縮すること。追加情報がいらないこともある。
- Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e
- Ci -> Cj にいくときのコストは適当にダイクストラとかで計算できる。あとは C1...CK の並び順を全探索すればよいが、これは順列全探索なので、 TSP の bitDP と同じようにできる。 dp[S][i] := 集合Sの石を含んでいて、末尾が i になるときの最小個数。
bitDP で集合を分割したい、部分集合を全探索したい
bitDP で dp[S] を求めたいとき、部分集合 T を用意して T と S ^ T に分割した結果を全探索して最適解を求めたくなることがある。
これはうまく実装することで O(3N) の計算量になる。
EDPC U のフレンズさん解が実装楽 & 割とそのままコピペして使える感じで良
- Close Group https://atcoder.jp/contests/abc187/tasks/abc187_f
- dp[S] := 集合 S の頂点を条件を満たすようにしたときの連結成分の個数 として上記 DP をすればとける
更新順を工夫する
よく考えると 自分より{大きい, 小さい}人しか選べません -> {大きい, 小さい}順に集合に追加していくことで常に自分より{大きい, 小さい}人だけがいる世界で計算できます も典型っぽい
— やむどぅ→技術書典13 (@ymduu) 2021年10月23日
自分より{小さい, 大きい}何かだけが操作の候補になる みたいな状況はよくある。そういう時は適切な順番で集合に追加していくとうまくいくことがある。
- https://atcoder.jp/contests/abc214/tasks/abc214_d
- 自分の重み以下の辺だけを使って行ける範囲というのを求めたい。重みが小さい順にグラフに追加するとOK
- https://atcoder.jp/contests/abc224/tasks/abc224_e
- グリッドを二部グラフとして見ると、自分の重みよりも大きい辺だけ使えることになる
- Integer Cards https://atcoder.jp/contests/abc127/tasks/abc127_d
- C が大きい順に処理していくと、処理されたカードについては今後考える必要がなくなる。前から上書き -> 後ろから確定 の亜種でもありそう
- MST + 1 https://atcoder.jp/contests/abc235/tasks/abc235_e
- 重み w の辺 (u, v) が MST に含まれる ⇔ w 未満の辺を全部入れて(≒クラスカル法を途中までやって)、 u と v が繋がっていない
追い越しが起きない
操作をして要素を動かしたりする場合、要素同士の追い越しが起きない(もしくは、しても損をするだけ)ことがある。 その場合、操作前と操作後のある値について、1対1対応をつくれることがある。
- https://atcoder.jp/contests/arc119/tasks/arc119_b
- ある 0 は、他の 0 を追い越さない限り1手で自由に移動することができる。各0を区別すると、その順序は変わらない。
最大化最小化問題は初手で二分探索を考える
自分は最大化最小化といわれてすぐに何も出てこなかったら、初手としてにぶたんの形にして考察しますね
— ますぐれ@競プロ (@masutech_compro) 2022年1月23日
今回ので言うと
中央値: 情報を01に圧縮できて個数問題になる
平均値: Xを決めておくとA_iを選ぶことをA_i-Xを足しておくと言い換えられて個数回りの面倒がなくなる
辺りが旨味です
熨斗くんがいってたと思うんだけど、求値問題よりも判定問題の方が真に優しいので落として考えるのは良いという話を知ってから割とにぶたんはすぐ考えるようになった
— ますぐれ@競プロ (@masutech_compro) 2021年11月13日
にぶたんの方が情報量が増えているので基本得みたいなスタンスでいると、かなり最初の方に考える手になって良いかもです
— ますぐれ@競プロ (@masutech_compro) 2022年1月23日
{最大値, 最小値} を求める問題は 解を K {以上, 以下} にすることができるか?という判定問題にすることで無料で二分探索でとける形にすることができる。
判定問題の方が真に易しいので判定問題で考えて損をすることはないという気持ち?
二分探索は思いついたけれど、判定問題を5分考えてわからないので捨てちゃう、みたいな負け筋がある(もっと掘り下げるべき)気がするので、判定問題のほうが易しいという気持ちを持っておくのは有効そう
最大化最小化といわれてすぐに何も出てこなかったら初手としてにぶたんの形にして考察、なるほどー、単調性については最大化最小化だったら判定問題を x {以上, 以下}にできるか?にすれば常に単調になると思ってるんですが、見るところあったりします?
— やむどぅ→技術書典13 (@ymduu) 2022年1月23日
その考え方で基本いけますね。怪しいやつだと、判定問題が構築で、構築方法がXの値そのものに依存する場合は怪しいです。gcdが絡む系とかですね
— ますぐれ@競プロ (@masutech_compro) 2022年1月23日
(その他メモ)
- Average and Median https://atcoder.jp/contests/abc236/tasks/abc236_e
- 判定問題に落としても難しいので二分探索をすててしまった回
- 中央値 平均値 は解({中央値, 平均値}そのもの)を固定すると有利になりがち(TODO: 書く)
二分探索 Tips
解を決め打つとあまり自明ではない圧縮?ができるやつとしては MAD TEAM(https://t.co/1UohIcu0vE) があるけど、こんな感じで抽象化してスクラップ行きかも
— やむどぅ→技術書典13 (@ymduu) 2021年11月13日
問題文から二分探索の気配がする(例えば、最大化 or 最小化問題で、単調にできる場合など)のに判定関数が思いつかない場合、解を決め打ったときに都合のいい圧縮ができることがある。
- https://atcoder.jp/contests/abc227/tasks/abc227_d
- ある解 x が達成できるか?を判定したいとき、 x を超える値はすべて x に丸めてしまってよい
- https://atcoder.jp/contests/zone2021/tasks/zone2021_c
- ある解 x が達成できるか?を判定したいとき、人間を x 以上の能力を持つ or 持たない の 5bitの状態に圧縮できる
中央値を見たら二分探索
https://atcoder.jp/contests/abc203/tasks/abc203_d
↑の都合のいい圧縮 の亜種(というかそのもの)だけど、よく言われてるので独立させとく。
解 X を決め打ったとき、 X より大きいかどうか? の 01に潰すことができて、うれしくなりがち
が詳しいんだけど、一個誤植?があって、「中央値は X 以下である」ことと、「 X 以上の要素が半数以上存在する」ことは同値 ではない。このことは、
1,1,1に対して中央値は1000以下だけど1000以上の数は0個である
が反例。 (Thanks iry)
https://t.co/2MS5KM2hfO
— やむどぅ→技術書典13 (@ymduu) 2021年11月18日
を参考にしたんだけど、
「中央値は X 以下である」ことと、「 X 以上の要素が半数以上存在する」ことは同値です。 って本当?(直感的には、「中央値は X 以上である」ことと、「 X 以上の要素が半数以上存在する」ことは同値 な気がする)
おきもち(やっぱそうな気がする) pic.twitter.com/TfGWa7Ixw5
— やむどぅ→技術書典13 (@ymduu) 2021年11月18日
グリッド / 座標平面
x 軸と y 軸を独立に考える
- 操作する問題などでは、 x 軸方向に対する操作と y 軸方向に対する操作を独立に考えられることがある。2乗オーダーだったものが線形に落ちたり、2次元DPが1次元に落ちたりする。
- https://atcoder.jp/contests/abc082/tasks/arc087_b
- Rook Path https://atcoder.jp/contests/abc232/tasks/abc232_e
- まさにそのもので、 x y 別々に考えて後からマージできる。
- https://atcoder.jp/contests/abc127/tasks/abc127_e
- x y 分離した後寄与を考える必要がある
- マンハッタン距離が出てきたら x y 分離チャンス
問題文に x y が出てきたらそれが (行, 列) なのか (列, 行) なのかを気を付ける
スクラップする場所にグリッドの座標でxとかyとか言い出したらめちゃくちゃ気を付けるというの追加しておくか(ヤケクソ)
— やむどぅ→技術書典13 (@ymduu) 2021年12月19日
- AtCoder では x: 縦軸 y: 横軸になることがあって、 x だから横軸という気持ちでいるとこわれてしまうことがある 簡単な問題で沼にハマると破滅しがち
- Rook Path https://atcoder.jp/contests/abc232/tasks/abc232_e
二部グラフにする
- 市松模様 -> 二部グラフ
- TODO: 具体例探す
- x軸ノードとy軸ノードに分けて二部グラフにする
- Must Be Rectangular! https://atcoder.jp/contests/abc131/tasks/abc131_f
操作が定義されている
操作によって2状態の入れ替えや flip が起こる(カードの裏表が変わるとか)
- 操作によって入れ替えが起こる場合はパリティに注目するとうまくいくことがある
- 操作をした後にもう一回操作すると元に戻るので0回操作した時と同じになる
- https://atcoder.jp/contests/arc128/tasks/arc128_a
- 銀->金にした後金->銀にすることは操作をしないことと同じ。
- https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d
- 順列全探索を bitDP に落とせることはすぐにわかる。問題はカードの裏表だが、それは移動前と移動後のインデックスの差のパリティでわかる。
操作によって過去の結果が上書きされる
- 前から上書きしていく操作を逆順にすると確定する操作になって見通しがよくなる。
操作が k 回行われる
操作が何度も行われるとき、{変,不変}量に着目するとうまくいくことがある。
特に不変量に着目するパターンは多い気がする(TODO: 探す)
- Roaming https://atcoder.jp/contests/abc156/tasks/abc156_e
- 操作が1回行われるごとに空く可能性のある部屋が1つ増える
区間に対して範囲攻撃を行う
- 攻撃対象を座標でソートしたとき、攻撃範囲の左端に対象をとらえて死ぬまで攻撃すると最適であることが多い
- https://atcoder.jp/contests/abc153/tasks/abc153_f
- 上記考察ができれば遅延セグ木貼るだけ
- https://atcoder.jp/contests/abc230/tasks/abc230_d
- 範囲攻撃版 islands war なので、上記考察ができれば islands war
- https://atcoder.jp/contests/abc153/tasks/abc153_f
ゲーム
- とりあえず grundy 数を計算して法則性をエスパーする
- 自分が得るスコア - 相手が得るスコア を計算してみる
- 特徴的な値が増えたり減ったりしないかを考える(単調減少だととくにうれしい)
- https://atcoder.jp/contests/agc033/tasks/agc033_c
- 直径が 1 or 2 減る
- https://atcoder.jp/contests/agc033/tasks/agc033_c
暫定解が簡単に作れそうなら暫定解をつくって更新してみる
- 適当に作った(貪欲とか、全部選ぶとか)解に対してある操作をすると解を改善できる場合(?)暫定解を作って更新していくことで最適解が求まることがある
- https://atcoder.jp/contests/agc018/tasks/agc018_b
- ある解のスコアが Q であるとき、改善するのなら Q 人参加する競技は開催されなくなるはず
- https://atcoder.jp/contests/agc013/tasks/agc013_b?lang=ja
- 初期解辺1本から端点に繋がっている、まだパスに含まれていない頂点をひとつ追加することを繰り返していくと、いつかはそのような頂点がなくなることがわかる
- https://atcoder.jp/contests/abc116/tasks/abc116_d
- 貪欲においしい順に食べる -> 2回以上食べているネタを1回も食べていないネタに入れ替えていく
- Pure https://atcoder.jp/contests/abc142/tasks/abc142_f
- 閉路のうち、これ以上小さくできないものを求める問題。ショートカットのある閉路に対してそのショートカットを使って短い閉路を構成することを繰り返す。
- 最小重み閉路は、辺 (u, v) を削除 -> uvの最短経路問題を解く ことでも求められる。
- https://atcoder.jp/contests/agc018/tasks/agc018_b
数学
n が巨大な nCr(r <= 105くらい)
n が巨大な nCr を計算するときは n! を前計算することができないのでこまってしまう。
小学校とかで組み合わせを計算するときは
みたいな公式で習った気がするけど、それをするとO(k)でいける。正確には
もっといろんなのがあるページ
- Bouquet https://atcoder.jp/contests/abc156/tasks/abc156_d
- n巨大nCr計算したくなるね
二項係数に対してシグマを計算したいときは式変形でpowの形にできることがあり
証明は二項定理から。
知ってるかゲーではあるので知ってればOK
- Bouquet https://atcoder.jp/contests/abc156/tasks/abc156_d
- 全事象求めるパートで使う
最大公約数
- 数列 A の最大公約数を g にできる ⇔ Ai は g の倍数
- Max GCD https://atcoder.jp/contests/abc136/tasks/abc136_e
- 言われてみればそれはそうだけど、気づきづらい、↑の問題はそこからさらに境界全探索の典型も必要
- Max GCD https://atcoder.jp/contests/abc136/tasks/abc136_e
条件式が合同式で表せて、法が変数(k)
法が変数(kとする)のとき、条件式を N ≡ 0 mod k の形で表せれば、k は N の約数となり、O(sqrt(N))でもとまる
- Division or Subtraction https://atcoder.jp/contests/abc161/tasks/abc161_f
- 一度割り切れなくなったらそこから新たに割り切れるようになることはないので、Kの候補は
- N ≡ 1 mod K (つまり、 N - 1 ≡ 0 mod K)
- Nの約数のうち、NをKで割れるだけ割ったものをMとして、 M % K == 1
- それぞれ O(sqrt(N-1))個、O(sqrt(N))個なので間に合う
- 一度割り切れなくなったらそこから新たに割り切れるようになることはないので、Kの候補は
N を割り切るものだけが候補になる
N を割り切る -> N の約数(それはそうだろ)
- Division or Subtraction https://atcoder.jp/contests/abc161/tasks/abc161_f
- 一度割り切れなくなったらそこから新たに割り切れるようになることはない
- つまり、割り算パートが入るのは K が N の約数の時だけ
- こっちはおまけだと思う
- 一度割り切れなくなったらそこから新たに割り切れるようになることはない
包除: x 個以上の条件を満たすものの個数を数え上げるのは簡単だが、重複を除くのが難しい → 包除
題の通り、条件 * 大量があって、 x 個以上の条件を満たすものの個数を数え上げることはできるが重複を除くのがたいへんなときは包除がつかえることがある。
普通に x 個の条件を満たすものの個数を数え上げると、 "x個の条件を満たし、他の条件を満たさない" ものを数え上げることになる。
数え上げのときに条件を満たさないというのは扱いづらいがち。
そこで、包除を考えると、 x 個の条件を満たし、残りの条件はドントケア(満たしても満たさなくてもよい) にすることができる。ドントケアになることによって見通しがよくなり、問題がとけることがある。
ABC172-Eの解説動画がわかりやすくておすすめ https://www.youtube.com/watch?v=v8ppNGf49Nk
- NEQ https://atcoder.jp/contests/abc172/tasks/abc172_e
- そのもの。とりあえず k 個一致するものの個数を数え上げたくなるが、素直にやると k 個一致するように配置したあと、のこりの N - k 個を一致しないように配置する必要があり、厄介。そこで、k個以上一致するものの個数を数え上げることにすると、前半の k 個一致する だけ考えればよくなって楽。 それらの重複を除くのに包除原理が使える。
- 撹乱順列 というキーワードも覚えておくと吉そう
約数系包除: パラメータが k の倍数
でぐわーさんの pdf の受け売り
「数え上げテクニック集」を公開しました - DEGwerのブログ
数え上げ問題を解くとき、 あるパラメータが k の倍数であるときの個数を数え上げられる場合、簡単に重複を除くことができる
降順に、あるパラメータが k の倍数であるときの個数を求める -> 既に求まっているはずの 2k, 3k...の個数を引く を繰り返す、計算量は調和級数から NlogN
- Sum of gcd of Tuples (Hard) https://atcoder.jp/contests/abc162/tasks/abc162_e
- そのもの
- gcd が k の倍数になる ⇔ k の倍数のなかから N こ選んだものの個数(これは単なる組み合わせ) -> それにこの典型を適用すればOK
mod N の世界で M を足していくやつ
通称"プラベで9人3ルールで回していると毎回同じ人が同じルールで観戦になってしまうやつ"
M と N が互いに素なら kM mod N(kは整数)で [0, N) のすべての値が出てくるが、そうでない場合は mod gcd(M, N) が同じ値しか出てこない。
証明がむずくて、後ろに多分拡張ユークリッドの互除法がある。(雰囲気で式変形をしているのでまさかりを投げないでほしい)
拡張ユークリッドの互除法についてはこの辺も見るとよい。 (∵拡張ユークリッドの互除法 の部分で下の議論を使っている)
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
{i, j | i < j}
なもののシグマを求めたい と言われたら条件 i < j
を除いて考えられる
みたいなのを見かけたら、
を求めて、
を引いて2で割れば OK、長方形領域の対角線より上の範囲の和を求めたいとき、長方形領域を求めて、対角線部分を引いて、2で割るイメージ
- Xor Sum 4 https://atcoder.jp/contests/abc147/tasks/abc147_d
- とある桁が 1 になる組み合わせの個数着目するが、これをすると見通しがよくなる(これってこの数と組み合わせていいんだっけ?を考えなくてよくなる)
- TODO: なんか ARC のむずめのやつであった気がするのを思い出して書く
平均値を見たら総和に言い替える
- n 個の平均値が a といわれたら、 n 個の総和が na と言い替えると見通しがよくなることがある
- 高橋君とカード https://atcoder.jp/contests/arc060/tasks/arc060_a
- 上記考察ができればあとは素直な部分和 DP
- 高橋君とカード https://atcoder.jp/contests/arc060/tasks/arc060_a
偶奇に着目する
- 〇〇が偶数である、とか奇数である、とか言われたら疑う
- Even Relation https://atcoder.jp/contests/abc126/tasks/abc126_d
- 距離が偶数である -> 偶奇にしか興味がないので距離を mod 2 してよい。 1 を通った時に色を反転させればOK
- Even Relation https://atcoder.jp/contests/abc126/tasks/abc126_d
0 xor 1 xor ... 2N-1 == 0 である
- 2べきまで xor で疑うといい?
- ビットごとに、[0, 2N) に含まれる 1 の数の総和は偶数なので、[0, 2N) までの xor をとると0になる。構築で使ったりするほか、この性質を問う問題を見たことあるような(TODO: 探す)
- 二進数を7くらいまで書き出してみると自明
- XOR Matching https://atcoder.jp/contests/abc126/tasks/abc126_f
- そのもの
xor (ビット演算全般も?)を見かけたら1桁ずつ独立に考えてみる
見たら真っ先に考えるようになっているとは思うけどかなりよく見るので一応
and, or, xor あたりのビット演算は二進数の桁ごとに独立に考えられる、そうすると見通しがよくなることがある
- Xor Sum 4 https://atcoder.jp/contests/abc147/tasks/abc147_d
- そのもの、桁ごとに1になる組み合わせがなんこあるか?を計算できる、寄与でもある(桁ごとの寄与を考える)
- Sum Equals Xor https://atcoder.jp/contests/abc129/tasks/abc129_e
- 各桁について、 XOR の値が 1 になるか 0 になるか で遷移を分けて桁 DP できる。 XOR は繰り上がりのない足し算 も典型。(下)
xor は繰り上がりのない足し算
二進数において、 xor は繰り上がりのない足し算とみなすことができる。a + b == a xor b みたいな時に役に立つ。(これが成り立つのは、くりあがりがない ≒ a と b で両方立っているビットがない とき)
- Sum Equals Xor https://atcoder.jp/contests/abc129/tasks/abc129_e
- そのもの、 a + b == a xor b となるのは、くりあがりがない ≒ a と b で両方立っているビットがない とき
floor(N, i) が大量に出てきたら floor(N, i) の値で分類して状態を潰してみる
{floor(N, i) | Nは適当な定数、 1 <= i <= N} をたくさん(1012個とか)扱いたくなった時のテク。 理由は以下のツイート。
x <= √Nのときはxの値が、 x > √Nのときは[N/x]の値がO(√N)しかない が本質か
— やむどぅ→技術書典13 (@ymduu) 2022年1月20日
floor(N, i) の種類数はO(√N)なので、単純に全列挙できなくても種類ごとになら全列挙できる。
実装方法はけんちょんブログが詳しくて、けんちょんさんのコードをライブラリ化してコメントをつけたものが以下
// {floor(N, i) | 1 <= i <= N} は O(sqrt(N)) 個しかないことを利用して、 整数 [1, N] について、floor(N, i) の値で分類する。 // (floor(N, i) の値, [1, N] の間にそのような値がいくつ含まれるか) のペアの vector を返す。 // 計算量: O(sqrt(N)) vector<pint> ClassifyByFloor(int N) { vector<pint> res; for (int i = 1; i <= N;) { // intfloor(N, i) の値で分類 int j = N / i; if (i <= j) { // 前半 // (i <= N / i) つまり、 i * i <= N つまり、 i <= sqrt(N) のとき、該当の値は1個しかない res.push_back({ N / i, 1 }); i++; } else { // 後半 // (i > N / i) つまり、 sqrt(N) より大のとき、該当の値は複数個あるかも // ここで、 i は N / x == j なる最初かつ最小の x 、 N / j は N / x == j なる最後かつ最大の x になってるはず(文字のまま考えるといまいちピンとこないが、具体的な値で実験してみるとピンとくるはず) // N/x == j なる最大の x は N/j ですよね(floor だからややこしい感じがするけど) // 閉区間になっていることに気を付けつつ個数をかぞえる [i, N/j] int cnt = N / j - i + 1; res.push_back({ N / i, cnt }); // i を次の最小値(今の最大値 + 1)にする i = N / j + 1; } } return res; }
- Fraction Floor Sum https://atcoder.jp/contests/abc230/tasks/abc230_e
- そのもの、↑のコードを貼るだけでとける
- Small Products https://atcoder.jp/contests/abc132/tasks/abc132_f
- 素直な DP を書いてテーブルの中身を眺めると、上記の圧縮をしたい気持ちにはなる。 圧縮した後手で実験すると、確かにレイヤー(N/x が同じ数の集合をこう呼ぶことにする) i の次にこれる数はレイヤー M - i 未満の数である となっていることがわかり、これは DP を BIT とか累積和で高速化すればOK
- 本質は i * j <= N ⇔ N / i * N / j >= N かなあ(これは問題固有の考察な気もするけど)
2つの数列 A, B においてマッチングを考えて、 Ai * Bj の和を最小化したい場合、A を昇順、 B を降順にして組み合わせると最適
A と B の長さが2の場合について 大-大、小-小 のように組み合わせた時、大-小 小-大 のようにすることで改善できることが証明できる。
直感的にそうだけど、無証明だとバグった時にノイズになるので証明できるとよい
(雑な証明、中学校の証明問題っぽい感じ)
貪欲の証明において、交換することで必ず改善することができるので最適性が言えるパターン
Change a Little Bit https://atcoder.jp/contests/abc150/tasks/abc150_e
- 直感的に Ci が小さい順にやっていくと最適だが、その証明ができていないと不安になる
- その先の式変形が大変
- 直感的に Ci が小さい順にやっていくと最適だが、その証明ができていないと不安になる
負数あり & 公差1の等差数列の和を考える時、負数のことは考えなくてもよいことがある
よって、負数のことを考えなくて済む。個数を数え上げたいときは最後に2倍すればOK
- Staircase Sequences https://atcoder.jp/contests/abc190/tasks/abc190_d
- 負数のことを考えなければ、数列の長さはO(sqrt(N))なので全探索できる
- 素直に立式すれば約数列挙に落とせて、そちらの方が筋がいいですね……
幾何
偏角
座標平面上で点や図形がたくさん与えられるとき、偏角に着目すると有名アルゴリズムを適用できることがある
- 偏角を区間とみなす
- 偏角ソート
- TODO: 問題を見つけて貼る
平面グラフのs-tカットをしたいときは双対グラフの連結性判定
抽象化すると 平面グラフっぽいものを切りたい -> 双対グラフの連結性問題 というのだけど(解説動画の受け売り)、これと次に出会うのはいつ
— やむどぅ→技術書典13 (@ymduu) 2022年5月16日
ABC181-F の円で通路を埋め尽くす問題で出会ったので幾何にいれとく。グラフかも。まあ直下がグラフだからいいよね
図形で道を塞ぎたい(≒平面グラフのような形)時は、双対グラフ(グラフの辺でかこまれた部分(面)を頂点、面に接する辺を辺と見たグラフ)の上で連結性判定をすればよい。
解説動画の 2:07:00 あたりがわかりやすい
https://www.youtube.com/watch?v=b0VIYIYB5v0
どういうときに使えるかというと、
- ABC181-F みたいに平面図形で何かを通行不可能にしたいとき
- 最小カットを求めたいけどいつものアルゴリズム(フロー)だと間に合わないとき平面グラフじゃないかを考える
くらい?
- Silver Woods
- ↑の初めて出会った問題、釘を半径rの円、動かす円を点とみなすようにすると上記のテクニックが使える。
グラフ
変形
- 1手でいける範囲を直接辺でつないだグラフを考える
- Travel by Car https://atcoder.jp/contests/abc143/tasks/abc143_e
- 1回の給油でいける頂点にコスト1の辺を張って、そのグラフの上で最短経路問題
- 高橋君が壁を破壊できる問題もこれだった気がする(うろ覚え)
- Travel by Car https://atcoder.jp/contests/abc143/tasks/abc143_e
- 頂点倍加
- Hopscotch Addict https://atcoder.jp/contests/abc132/tasks/abc132_e
- いまけんけんぱの何個めかを頂点で表す。 DP の添え字を増やすのとまったく同じ。(そもそもダイクストラはDP)
- Hopscotch Addict https://atcoder.jp/contests/abc132/tasks/abc132_e
2つの関係 * 大量が与えられたときグラフにできないか疑う
- 1 or 2 https://atcoder.jp/contests/abc126/tasks/abc126_e
- グラフに見えれば UF やるだけ
- 数列に対して swap(i, j) 操作(Ai と Aj をスワップ)がたくさん行われるとき、(i, j) に辺を張ると各連結成分は自由に移動できる
- TODO: 問題を探す
条件として奇閉路がない が与えられた
奇閉路がない ⇔ 二部グラフ。
- Classified https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d
- 奇閉路がない ⇔ 二部グラフを知っていれば再帰的に半分にしていこっかなという気持ちになる
木
木はつよい条件
部分木を考えたとき、その部分木に含まれない残りのほうも木だし、一意
あたり前なんだけど出てこないがち……これが出てこないと難しい問題を解こうとしてハマりがち
とくに "ある辺を切って木を2つに分割" みたいなシチュエーションでよく見る
- Through Path https://atcoder.jp/contests/abc187/tasks/abc187_e
- ある辺で切って、片方の部分木に含まれる頂点に数を足すみたいなクエリがやってくる。木を切ったら木 * 2 になるのでできる。
- 根つきにして部分木の根(部分木のうち、根にもっとも近い頂点)に足す -> 木DP が常套手段だが、根側に足すときは 根に足す -> 部分木の根から引く ことで達成できる
- 一時期のコドフォでよく見た
部分木クエリはオイラーツアー
部分木に対してなんかしてくれと言われたらオイラーツアーをすることで、部分木クエリを区間クエリに落とすことができたりする、実装たいへんなのでライブラリ化したい
- Count Descendants https://atcoder.jp/contests/abc202/tasks/abc202_e
木の上でおいかけっこをするとき捕まらないための条件
高橋君と青木君が木の上で追いかけっこ(自分も相手も1Tに1手うごくことができる みたいな)をするとき、高橋君が青木君に会わずに行ける頂点の条件は (高橋君からの距離 < 青木君からの距離) である。
木の上で相手に会わずすれ違うことはできないのでそうなる
- Playing Tag on Tree https://atcoder.jp/contests/abc148/tasks/abc148_f
- 高橋君が行ける頂点がわかるので、そのうち青木君からもっとも遠い頂点に行けばOK
- Fennec VS. Snuke https://atcoder.jp/contests/abc067/tasks/arc078_b?lang=ja
- 忘れたけど、本質はこれだったような記憶
木(数直線でも)上で追いかけっこをするとき、距離のパリティが保存
相手も自分も動かなければならない場合、{両方離れる方向に移動: +2 両方同じ方向に移動: +0 両方近づく方向に移動: -2}なので、そうだね
- Playing Tag on Tree https://atcoder.jp/contests/abc148/tasks/abc148_f
- 高橋君と青木君が出会うのはどこになるか?を詰めるのに使う
木DP 根から埋めるか葉から埋めるか
木で、再帰的に各ノードに対する結果を求められそうなときは木DPが使えることがよくあるが、根から埋めるパターンと葉から埋めるパターンがある。両方あることを意識しておかないと解ける問題を落としがち
親兄弟の情報だけで子が求められる: 根から
子が全部分かれば親が求められる: 葉から
というイメージ(こう書くと それはそう だな……)。根からの時は木DPと呼ばない宗派もある???
- 根から
- Virus Tree 2 https://atcoder.jp/contests/abc133/tasks/abc133_e
- 素直に木を根から舐めていけばOK
- Virus Tree 2 https://atcoder.jp/contests/abc133/tasks/abc133_e
- 葉から
- Subtree K-th Max https://atcoder.jp/contests/abc239/tasks/abc239_e
- 子が分かればそのノードの上位20個がわかるので、葉から順番に埋めていけばOK
- Distributing Integers https://atcoder.jp/contests/abc160/tasks/abc160_f
- 子の情報を順番に親にマージしていく木 DP ができる。すべての頂点を根にした時の答えを要求されるので、全方位木DPが必要そうで、そこから逆に発想することもできる
- Subtree K-th Max https://atcoder.jp/contests/abc239/tasks/abc239_e
根からすべての頂点までのパスについて何かを計算するとき、あるノードの計算が終わった後に巻き戻すテクニックが使えることがある
本質はスタックの dfs と同じだと思う……差分更新とそれを戻すことを繰り返すイメージ?
LIS みたいな列に対するアルゴリズムを木に使いたいとき、行きがけ順に普通に計算、帰りがけ順に結果を1手戻す、とするとうまくいくことがある。"計算"と"戻す"がそれぞれO(1)でできる必要がある
- LIS on Tree https://atcoder.jp/contests/abc165/tasks/abc165_f
- そのもの、パス (1, v) について結果が求まったら、 dfs を抜ける前に v の影響を巻き戻しておく(スタックっぽい操作)
全方位木 DP が必要そうなときは葉から決める木DP を考える
全方位木DPの気配を感じたら(これはたやすい)葉から決める木DPを考えるとするだけで勝率上がりそうな気がしてきた(スクラップ行き)
— やむどぅ→技術書典13 (@ymduu) 2022年3月12日
全方位木 DP の実装とその使い方は
が詳しい。ここの実装を使うと、子の情報から親の情報を求める DP を全方位木 DP に拡張できそうだということがわかる。
全方位木 DP が必要そうだと思ったら(≒木のすべての頂点を根としてなにかの値を求める必要があるなら)葉から決める木 DP を疑うとよい
- Distributing Integers https://atcoder.jp/contests/abc160/tasks/abc160_f
- 問題文から明らかに全方位木DPが必要そうで、葉から決める木DPができないか?と思うと、できる
DAG
DAGも強い条件、トポロジカルソートできるぞ
トポロジカルソートできれば超実装軽い DP とかできることがあるので、有向辺(u, v) で u < v とかの見慣れない制約があったら疑ってみるとよい
依存グラフ解析系の問題は DAG じゃなかったら解なしとかある(循環依存になってしまうので)
- Peddler https://atcoder.jp/contests/abc188/tasks/abc188_e
- DAG なので、トポロジカルソートして DP でその町までに買える金の最安値を計算できる
- League https://atcoder.jp/contests/abc139/tasks/abc139_e
- DAG なら解が存在、 DAG の最長パスはトポロジカルソートして DP で求まる
グラフに対する操作
ある条件の時辺を追加できる -> 再帰的に辺を追加できて最終的に完全グラフになる みたいなの他にも見覚えがある気がするわね(すぐには出てこないけど)
— やむどぅ→技術書典13 (@ymduu) 2021年12月18日
- 条件を満たす頂点間に辺を追加する操作
- 再帰的に辺を追加していくと実は 完全グラフ とか完全二部グラフ になることがある
- 追加した辺によって新たに条件を満たす頂点対が現れて……みたいなことを繰り返す
- 3 Steps https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
- あるパスに辺を追加すると、そのパスの長さを2減らすことができるので、再帰的にある頂点からの距離の偶奇が同じ頂点間を全部繋げる -> 二部グラフかどうかで場合分け
- Must Be Rectangular! https://atcoder.jp/contests/abc131/tasks/abc131_f
- グリッドを二部グラフに言い替える奴をすると、完全二部グラフになるまで辺を足せる
- 再帰的に辺を追加していくと実は 完全グラフ とか完全二部グラフ になることがある
境界全探索
- ある条件を満たすか満たさないかで扱いが変わる時(表現がむずい)、その境界を全探索できることがある
- Max GCD https://atcoder.jp/contests/abc136/tasks/abc136_e
- 最大公約数 g を全探索するとき、 mod g の値をソートすると、ある場所より左は0に寄せて、ある場所より右は g ≡ 0 mod g に寄せるのが最適
- mod g の値でソートして、ポインタ二つ(l, r)用意して、l が 0 になるまで、 r が g になるまで操作することを繰り返すと解けるけど、これは正当なのかな
- 最大公約数 g を全探索するとき、 mod g の値をソートすると、ある場所より左は0に寄せて、ある場所より右は g ≡ 0 mod g に寄せるのが最適
- Max GCD https://atcoder.jp/contests/abc136/tasks/abc136_e
構築
グラフを構築しろと言われた
- パスグラフ、スターグラフ、二部グラフ、完全グラフなど特徴的なグラフから「暫定解を改善」して作れないか考える
- Friendships https://atcoder.jp/contests/abc131/tasks/abc131_e
- 直感的にスターグラフの時最大になる気がする。(これを思いつくのがつらい)スターグラフなら葉(?)を繋ぐことで距離2の頂点対をひとつ減らせる
- Friendships https://atcoder.jp/contests/abc131/tasks/abc131_e
クエリ(もっといい分類あるかな……)
数列のうち一つだけを消す→左右から累積
数列が与えられて、ある一つの要素を消した時のナニカ(gcd とか)を求めてくださいみたいな問題、ありがち
左と右から累積ナニカを計算しておいて、それをうまく合体させると解になることがある
- Yutori https://atcoder.jp/contests/abc161/tasks/abc161_e
- あるマスについて、左右からそのマスを除いた最適解を事前計算しておいて、それらの和が K 未満ならそれは必須
- GCD on Blackboard https://atcoder.jp/contests/abc125/tasks/abc125_c
- 数列において、ある数 Ai を削除したときの最大公約数の最大値を求める。
- 左右から累積 GCD を計算しておいて、あるマスの左右の 累積 GCD を合体(gcd をとる)させればよい。セグ木でも OK
その他言い替えなど
必ず使われる要素を求めよ → 消してみて不都合がないか?を調べる
表題の通り、必ず使われる要素 → 消して不都合が出る。背理法的な感じ
必ず使われる は難しい条件なのでこういう言い替えをするといいって感じ? 1つ以上使う は難しいから余事象を考える の亜種みたいな?
- Yutori https://atcoder.jp/contests/abc161/tasks/abc161_e
- この言いかえが難しい、この言いかえができれば、ある o の日に働かないことにして働き方を構成できるか?という問題になって、まだ取り付く島がありそうな気がする
- ここから 数列のうち一つだけを消す→左右から累積 の典型を使うのが天才を要求されなくていいと思う
問題が解けない時に考えること
実は数や探索空間がすくなくて全探索できないか?
- ABC-D ABC-E くらいで詰まったら
- https://atcoder.jp/contests/abc235/tasks/abc235_d
- まさにABC-D、出てくる数は全部 106 未満(106 を超えたら解になりえない)なので BFS で全探索できる
- Many Requirements https://atcoder.jp/contests/abc165/tasks/abc165_c
- 要素が M 以下、長さNの単調増加列は NM ではなく、枝を狩ることで減らすことができる。
- 全探索できないか?と思ったら最大ケースでの計算量を計算するプログラムを書いてみるとよい、サボらない
- I hate Factorization https://atcoder.jp/contests/abc166/tasks/abc166_d
- 同上、探索範囲を絞って X になりうる かつ X が 109 以下である値の個数を調べる -> 探索範囲を広げてもその個数は増えないことを観察できれば、ワンチャン投げられる
- 式に n乗 が出てきてたら探索範囲は n乗根 で抑えられることがおおい気がする
- https://atcoder.jp/contests/abc235/tasks/abc235_d
1変数固定できるならしてみる
1変数固定して全探索すると見通しがよくなることがある。見えない時は見えない。
3変数のときは真ん中(AとB、BとCが影響しあっているならB)を固定すると都合がよくなったりする。裏技ちっく。
こういうの割と強い人でもハマるので、持ってると稼げるかも。
- RGB Coloring 2 https://atcoder.jp/contests/abc199/tasks/abc199_d
- 赤く塗る頂点を固定すれば二部グラフ判定でOK。
ハッシュ(mod N とかも含む)を衝突させる組を一つ見つけよと言われたら鳩ノ巣原理
ハッシュを衝突させる組を一つ見つける問題は鳩ノ巣原理を考えると楽になることがある。ハッシュの集合の元が N 個あったら、 N + 1 個のハッシュを生成すればどれか一つは衝突している。
- Happy Birthday! 2 https://atcoder.jp/contests/abc200/tasks/abc200_d
- DP 復元でも解けるけど、鳩ノ巣が見えれば全探索するだけになる。実装量が段違いなので速度差がついてしまう……
1対1の割り当て(例: アルファベットに数字を入れる)の場合、種類が少ない方を全探索すればよい
(特にABC-Dくらいまでの低難易度で)1対1の割り当てを考える場合、種類が少ない方を全探索できることがある。例えば、a-zに互いに異なる0-9を割り当てる場合、アルファベット側が11個以上ある場合は割り当てを作れないので考えなくてよい。(例外処理は必要) こうすることで実は全探索することができることがある。
- Send More Money https://atcoder.jp/contests/abc198/tasks/abc198_d
- アルファベットに互いに異なる0-9を割り当てる問題。アルファベットが11種類以上ある場合割り当てられず、10種類なら順列全探索でいける。
思いつかない時は数え上げ対象を可視化して特徴を探す
数え上げで方針が見えない場合、賢い言い替えが必要なことがある。賢い言い替えは睨んでいても出ないがちなので、可視化して攻めると良い
- Roaming https://atcoder.jp/contests/abc156/tasks/abc156_e
- 構成できる条件は、空き部屋の個数が min(n-1, k) 以下 と言い替えられる。これに気づくのはけっこう大変なので、k回操作したときの状態を列挙すると空き部屋はk以下だと気づけるかも
- 厳しい重複除去が必要になったら負け筋かも
典型90で自力できなかった問題リスト
2週目やらねばならぬリスト的な。多分もっとあるはずだけど、とりあえず今残ってるのだけ。(ほんとは★7はほぼ全部解説ACな気がする)
005 Restricted Digits(★7)
023 Avoid War(★7)
049 Flip Digits 2(★6)
057 Flip Flap(★6)
062 Paint All(★6)
065 RGB Balls 2(★7)
083 Colorful Graph(★6)
するめうめ
これはなに
をやる
SRM 715 MaximumRange
max(+ の個数, - の個数)
class MaximumRange { public: int findMax(string s) { lint p = 0, m = 0; for (char c : s) { if (c == '+') { p++; } else { m++; } } return max(p, m); } };
SRM 735 PalindromeSubsequence
aのみ、bのみを取り出すとそれは回文なので、答えのサイズは 2 以下。 1になるのは s が回文の時だけなので、その通り実装する。
class PalindromeSubsequence { public: vector<int> optimalPartition(string s) { auto t = s; reverse(ALLOF(t)); if (s == t) { return vector<int>(s.length(), 1); } vector<int> ans; for (auto c : s) { if (c == 'a') { ans.push_back(1); } else { ans.push_back(2); } } return ans; } };
SRM 729 MagicNumberThree
dp[i][j] := i 番目まで見て、余りが j になる場合の数として素直にDP
mint dp[100][3]; class MagicNumberThree { public: int countSubsequences(string s) { rep(i, 100) { rep(j, 3) { dp[i][j] = 0; } } int len = s.length(); s = "*" + s; dp[0][0] = 1; rep(i, len) { int si = s[i + 1] - '0'; si %= 3; rep(j, 3) { // いれる dp[i + 1][(j + si) % 3] += dp[i][j]; // いれない dp[i + 1][j] += dp[i][j]; } } return dp[len][0].x - 1; } };
SRM 748 EraseToGCD
dp[i][j] := i 番目まで見て gcd が j である場合の数。 空集合の gcd は 0 である(gcd の単位元は 0 ) とすると都合がよいことに注意する
mint dp[510][1010]; class EraseToGCD { public: int countWays(vector<int> S, int goal) { rep(i, 510) { rep(j, 1010) { dp[i][j] = 0; } } int N = S.size(); dp[0][S[0]] = 1; dp[0][0] = 1; rep(i, N - 1) { rep(j, 1010) { // 入れる dp[i + 1][euclidean_gcd(j, S[i + 1])] += dp[i][j]; // 入れない dp[i + 1][j] += dp[i][j]; } } return dp[N-1][goal].x; } };
SRM 755 OneHandSort
- Each element of target will be between 0 and N-1, inclusive.
- All elements of target will be distinct.
なので、 i は i 番目(0-indexed) にくることがわかる。
よって、
i 番目にある値を 空きマスに退避
i を↑で開けたマスに移動
を繰り返せば OK。(idx[i] := i のインデックス の実装で頭を壊してしまったが、N <= 500 なのだから、テーブルを持たずに愚直をやってもよかった……)
class OneHandSort { public: vector<int> sortShelf(vector<int> target) { int N = target.size(); vector<int> ans; vector<int> idx(N); rep(i, N) { idx[target[i]] = i; } auto processed = target; processed.push_back(-1); int blank = N; rep(i, N) { if (processed[i] != -1) { // i えらぶ ans.push_back(i); // 今入ってる数の場所を更新 idx[processed[i]] = blank; swap(processed[i], processed[blank]); blank = i; } // idx[i] えらぶ ans.push_back(idx[i]); // 今入ってる数の場所を更新 swap(processed[idx[i]], processed[blank]); blank = idx[i]; idx[i] = i; //cout << processed << "\n"; } return ans; } };
精選100問をやる
これはなに
ABC の 400 500 が埋まり、 experimental でない 水 diff が埋まり、experimental でなく AGC でもない 青diff もだいぶ埋まり、蟻本類題も中級までやったため精進の方向性が迷子になってしまった…… 次はなにをやろうかなと思ったところで、今足りていないのは何かを考える。
- 知識はある程度身に着いた気がする
- 思いつく能力みたいなのは全然足りていないけど、これは粛々と数をこなすしかない気がするので保留
- なんとなく現状速さと正確さがが足りない気がしている
- 今の知識セットのまま速くなればレート200は盛れる気がするし、正確さを得れば爆死が減って精神によい(ハードル走の反省……)
その辺を色々考えて、イカの精進が思いついた
(要するにちょっと下くらいの問題を時間を計って短時間で解いてみようという試み)
- experimental な 水 青 diff埋め
- experimental difficulty は一色ぶんくらい高く出ているような気がするので、下埋めの狙い
- 平成ABC(ABC041以前)の D 埋め
- 実は実質 experimental な 水 青 diff埋め
- 精選100問 埋め
- 目指せ水色コーダー の記事なので、やっぱり下埋めの狙いなのだけど、"100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。"らしいんで、信じるのだ……
思いついた中で、現環境に合わなかろう古い問題を埋めるよりも赤い人のおすすめ100問のほうがコスパがよかろうということで精選100問をやることに。
レギュレーション
- 時間を計る
- 速さを定量的に評価するため。
- ライブラリ禁止
- 実装の筋トレも目的のひとつなので。
- ただし非本質部分(ダイクストラに対するグラフテンプレート部分とか)はオッケー
- 蟻本写経はオッケー
- 自己流の悪い実装をしてもしかたないので……
- 解いたら時間、自力 or not、感想をここに書く
- ボトルネックにならない程度に……
- できれば朝やる
- 基礎力トレーニング
- とか言いつつ、おせんべいが やや難問 とか言って登場したりするのでできる限りで
- できれば疑似コードを手で書く
- バックスペース禁止はむりだけど……
結果
num | time | submit | 感想(どういうバグらせをしたか等) |
---|---|---|---|
1 | 4:30 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4556791#1 | 重複NG とかを読み飛ばしてちょっと戻った |
2 | 7:56 | https://atcoder.jp/contests/abc106/submissions/14085318 | 奇数 を読み飛ばして合わず、変数名を間違えて合わず をした(考えながら実装をするな) |
3 | 5:55 | https://atcoder.jp/contests/abc122/submissions/14085853 | 疑似コードを書くようにした 一度も戻らずAC |
4 | 7:51 | https://atcoder.jp/contests/pakencamp-2019-day3/submissions/14086112 | 疑似コードというか C++ のコードを手書きしているんだけど…… |
5 | 8:32 | https://atcoder.jp/contests/abc095/submissions/14086472 | max と min を間違えて1回休み |
6 | 11:03 | https://atcoder.jp/contests/sumitrust2019/submissions/14104743 | 3桁決め打ち、フラグ立てる時どこまで埋まっているかを見ず1回戻り |
7 | 21:27 | https://atcoder.jp/contests/joi2007ho/submissions/14148247 | 面白い、頂点 P, Q, R, S のうち2点を決めれば正方形が定まるので、全探索するのはN2でOK |
8 | 15:33 | https://atcoder.jp/contests/s8pc-6/submissions/14169626 | 興味があるのは 人が行きうる座標だけなのでそれを全探索 手戻りなし(のわりに遅い?) |
9 | 16:04 | https://atcoder.jp/contests/joi2008yo/submissions/14190764 | 手戻り無し のわりに遅いかなあ。 JOI、座標好きがちなのでベクトルのライブラリがほしくなってくる |
10 | 4:05 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4572490#1 | 手戻り無し |
11 | 10:07 | https://atcoder.jp/contests/abc128/submissions/14401968 | 条件が若干複雑なので紙で条件を整理すると事故らなくてよいですね |
12 | 11:45 | https://atcoder.jp/contests/abc002/submissions/14422184 | 集合の中にいる人の組を全探索するときに同じ人間の組み合わせを許容してしまい1回戻り |
13 | 10:10 | https://atcoder.jp/contests/joi2008yo/submissions/14442890 | 手戻り無し |
14 | 23:34 | https://atcoder.jp/contests/s8pc-4/submissions/14462776 | 累積 max を持っておくと実装が楽。編集していいビルを全探索するか見えるビルを全探索するかで迷った、コストを計算する式を間違えてコストが負になった |
15 | 11:30 | https://atcoder.jp/contests/abc145/submissions/14601298 | 添字を2回間違えて時間を食った、1回目は1->2->3 のルートの長さを6回足してた(なんで) |
16 | 6:35 | https://atcoder.jp/contests/abc150/submissions/14626459 | フラグを書き換える場所と辞書順の値を誤って1回戻った |
17 | 31:56 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4625270#1 | 言われて見れば順列全探索だなあ、と思い next_permutation を書き、バグらせて結局dfsを書いた。グリッド上の斜めはx座標とy座標の和または差が一定。 |
18 | 6:09 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4628621#2 | 手戻り無し、次の数の場所を探すときにupper_boundが使える |
19 | 23:37 | https://atcoder.jp/contests/joi2009ho/submissions/14875840 | 各クエリで二分探索して 家 の左右の店を見つければよい。(番兵として距離dにも店を置いておく)、== と = を間違える古典的なやつをして1バグ |
20 | 7:23 | https://atcoder.jp/contests/abc077/submissions/14894821 | 固定するのは直接影響する要素が多いもの(今回はB)がよい、 + と * を間違えて1バグ |
21 | 19:39(+2WA) | https://atcoder.jp/contests/abc023/submissions/14958761 | H_i > k なる k は達成不可能なのを見落として1WA、デバッグ中に1WA |
22 | 41:11 | https://atcoder.jp/contests/arc054/submissions/15034683 | 謎の定数(迫真) 二分法は初めてだったので時間がかかった 追記: 2.164042560698 は3 / (2log2) で、fx = x + P(2x/1.5) の第二項目にあたる |
23 | 13:52 | https://atcoder.jp/contests/joi2008ho/submissions/15057057 | N = 1000 なので半分全列挙して相方を二分探索。全列挙した配列をソートし忘れて1バグ |
24 | 32:17 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4651272#1 | 問題の読解が難しかった、出次数0の点を展開するのに1かかるなどを見逃してハマった(適当に時間を増やしたり減らしたりして通してしまった節がある、問題文から何をすると時間が経つのか読み取れなくない?) |
25 | 10:08 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4656192#2 | 手戻り無し |
26 | 9:23 | https://atcoder.jp/contests/abc138/submissions/15214611 | 手戻り無し |
27 | 43:21(+3WA) | https://atcoder.jp/contests/joi2009yo/submissions/15232708 | x と y を間違える、nx と x を間違える、そのマスの探索が終わったらそのマスの visitedフラグを折る(これが本質)を忘れるなどしてハマった、depth を最初引数にしなかったのも混乱を助長した、多少冗長でもわかりやすさを優先した方がよい |
28 | 5:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4671578#1 | while の条件書き忘れ(そんなことある?)と != と == を間違えて(そんなことある?)2回バグらせたけどどちらも一瞬で解決できた |
29 | 8:38 | https://atcoder.jp/contests/abc007/submissions/15249845 | 壁かどうかを見るのを忘れて1回バグった(そんなことある?) |
30 | 16:38 (+ 1TLE) | https://atcoder.jp/contests/joi2011yo/submissions/15325682 | visited な場所はキューに入れない から大丈夫と思ってキューから出したもののvisitedチェックをサボったらTLEした(同じマスに同じ距離で到達するパスが複数ある場合、同じマスからのパスを複数回数えてしまう) |
31 | 42:54 | https://atcoder.jp/contests/joi2012yo/submissions/15340713 | W と H を取る順番を間違えて1回戻った、純粋に六角形の遷移を考えるのに時間を食った |
32 | 24:59 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4692845#1 | 普通に bfs だけど壁の扱いが厄介、h と w を 1か所間違えて1回戻り |
33 | 13:10 | https://atcoder.jp/contests/abc088/submissions/15373165 | 普通に bfs 、スタートとゴールのことを忘れて1回戻り |
34 | 1:53 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704355#1 | 手戻り無し |
35 | 23:06 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704427#1 | ナップザックの大きさを勘違いしていて1WA、デバッグに苦労した |
36 | 4:38 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706743#1 | 手戻り無し、個数制限がない場合は遷移の方法を少し変えることで対応できるのであった。 |
37 | 8:01 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706794#1 | 手戻り無し、36 の個数制限なしナップザック問題の気持ちになるとOK |
38 | 18:29 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706913#1 | 1-indexed にする時にstring::length を先頭にダミー文字を追加した後に使ってしまいバグらせた。蟻本の「どれかであるので」という考え方が重要なのであった |
39 | 14:47 | https://atcoder.jp/contests/joi2011yo/submissions/15484514 | 手戻りなし、dp[i][j] := i 番目まで計算して、結果が j になる場合の数。先頭と末尾を特別扱いするのでインデックス注意 |
40 | 44:54 | https://atcoder.jp/contests/joi2012yo/submissions/15485657 | 配るDP にしたら i 日目 は パスタ k しか食べてはならぬ の条件を i + 1日目 に適用してしまいバグらせた。 前日と前々日の食事さえ分かっていればよいので、それらを添字に持つ |
41 | 18:48 | https://atcoder.jp/contests/joi2013yo/submissions/15496981 | 手戻りなし、dp[i][j] := i 日目 にフク j を着るときの最大スコア |
42 | 19:11 | https://atcoder.jp/contests/joi2015yo/submissions/15513581 | M 日目 にも移動できることを忘れて答えが合わなかった。 dp[i][j] := i 日目 に j に居る時の最小疲労度 |
43 | 21:17 | https://atcoder.jp/contests/pakencamp-2019-day3/submissions/15532988 | 手戻り無し。結局 i 列目 の塗り方は i-1 列目の塗り方にのみ依存するので、 dp[i][c] := i 列目 を色 c で塗る時の最小コスト。i 列目 を色 c で塗る場合を全てまとめて考えてよいことに対応する。 |
44 | (時間を計っていないけれど合計1hくらい?) | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4727213#1 | 個数制限なしナップサック問題なのだけど、普通にやるとMLEする。配列を使いまわすとOK |
45 | 20:33 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730700#2 | 素直に dp[i][j] := i番目のデータがjに復号される時の最小コスト |
46 | 33:58 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730839#2 | 素直な区間DP、[m, r) をマージした行列の行数を間違えて1回戻った |
47 | 40:01 | https://atcoder.jp/contests/joi2015ho/submissions/15655523 | 円形 -> 二周分配列(今回はDPテーブル)を持つ。手番の存在を忘れて1回戻り、メモ化を忘れて1TLE |
48 | - (自力できず) | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4736472#1 | dp[l][r] := [l, r) にできる操作の回数 なのだけど、2つの区間の和になる遷移 と 長さが2小さい区間の外側の差が1以下の遷移 を同時にやろうとして迷走してしまい解説AC |
49 | 38:20 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4738606#2 | 始点が定まっていない。と思ったら始点を0にする大嘘が通ってしまうので笑う。と思ったがそれはそうか*1蟻本を見ながら頑張って書いた。dp[S][v] := Sに含まれる頂点を訪問済みで、vにいるとき、そこから残りの頂点を訪問して start に帰ってくるときの最小コスト。初期値(再帰の停止条件)が全頂点を訪問し終わった時であることに注意する |
50 | 101:11 | https://atcoder.jp/contests/s8pc-1/submissions/15803043 | dp[S][v] := 訪問済み頂点集合がSでvにいる時の(最小コスト, 場合の数) のペア として下から配る DP をする、蟻本版でやろうとして無限に迷子になった |
51 | 29:40 | https://atcoder.jp/contests/joi2014yo/submissions/15815045 | 手戻りなし、 dp[i][S] := i日目に集合Sの人が参加する場合の数、SからS'に遷移するときに S & S'が0でないこと、各日の責任者を含むことを確認する |
52 | 33:43 | https://atcoder.jp/contests/joi2017yo/submissions/15818888 | 手戻りなし、 dp[S] := ぬいぐるみを左から詰めていくとしたとき、集合Sを置き終わった時の最小コスト。TSP 同様 n! を 2n に落とす系。 bitDP と言われてなければ解けなかった気がする…… |
53 | 31:43 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4754100#1 | 手戻りなし、セグ木の方しか知らないので貼ってしまった、dp[i] := ai を左端としたときの最長の LIS で更新はchmax(dp[i], [0, ai) の最大値 + 1)、aの範囲が広いので座圧がひつよう |
54 | 14:51(+ 1WA) | https://atcoder.jp/contests/abc006/submissions/15838521 | i 番目までソートする手順から i + 1 番目までソートする手順を構築しようとするも嘘なのでWA、よく考えると LIS の場所は変えずにそれ以外の場所だけ変えると最小コストになることがわかるので昨日書いた LIS のコードを貼ってAC |
55 | 15:23 | https://atcoder.jp/contests/abc134/submissions/15865751 | 手戻りなし(が、すでに解いたことがあったため……)、作られる増加列の先頭に注目すると、広義単調減少になっていることがわかるので、LISの要領で最長減少部分列の長さを求めるとGG |
56 | 10:45 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4760053#1 | 手戻りなし、素直なdijkstra |
57 | 17:07 | https://atcoder.jp/contests/joi2008yo/submissions/15881676 | ダイクストラをソラで書く縛りをしているのでキューに入れる不等号を逆にしてバグらせた |
58 | 48:13 | https://atcoder.jp/contests/joi2016yo/submissions/15882860 | 手戻りなし、普通に実装が重かった、bfs パートは素直に bfs をすると TLE するのでそのノードにより近いゾンビ町が存在するときは探索を打ち切る枝刈りをいれるとO(N)になる気がする。 |
59 | 83:39 | https://atcoder.jp/contests/joi2014yo/submissions/15984809 | グラフ構築パートで dfs を書いて1回戻り(dfs では最短経路は求まらないのであった)、bfs をなんとなく書いたらめちゃくちゃバグって苦しくなった。visited はキューに入れる時に true にしないとほかのノードからそのノードに到達したときに最適でない経路が記録されてしまうのでNG。幅優先探索なんもわかってなかった |
60 | 9:39 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4765542#1 | 負閉路検出は2回目で更新があったらでOKなのであった。(ベルマンフォードと同じ) 蟻本の実装だと負辺がある場合 INF から引かれてしまうので、 INF からは遷移しない、出力時に INF の範囲を広くする(あり得る最大パス長を超えたらINF)などの工夫が必要。 追記: WF の負閉路検出は dist[i][i] < 0 でもできるらしい。たしかに…… |
61 | 11:02 | https://atcoder.jp/contests/abc012/submissions/16014119 | 手戻りなし、問題文の読解が難しいけど WF して全始点について調べたらOK |
62 | 5:42 | https://atcoder.jp/contests/abc079/submissions/16021273 | 手戻りなし、グラフに見えるまでが大変な問題な気がするけど流石に最近は見えるようになった気もする |
63 | 64:11 | https://atcoder.jp/contests/abc074/submissions/16022335 | 与えられたAを完全グラフの隣接行列と見るまではよかったものの最小全域木を求めたり辺を小さい順に入れようとしたりして迷走した、迂回路がある辺は取り除いてよいので、A[i][j] == A[i][k] + A[k][j] なる k があったらその辺を除けばOK |
64 | 7:57 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772473#1 | 手戻りなし。今まで クラスカル の方が簡単なのでクラスカル を書いていたが、ここでは経験のため プリム を書いた。このプリム は ElogE な気がするけど、どうするとElogV になるんだろう(蟻本のダイクストラ同様の議論ができる?) |
64_2 | 4:19 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772504#1 | プリム法。こちらの方が実装が楽なので以降こちらを使う。(UnionFInd はまだ貼ってる) |
65 | 28:42 | https://atcoder.jp/contests/joisc2010/submissions/16039928 | 手戻りなし。K = 1 のときは普通に最小全域木を求めたらよくて、そうでないときは最小全域木から自由に辺をK-1本除ける(会場と会場の間の辺を自由に1本除去できるので、好きな辺を除去するための配置を構築できるはず) |
66 | 30:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4775067#1 | int と double を間違えて何度か戻った。 基本はセル?をノードとしたグラフを考えて MST するだけ |
67 | 11:07 | https://atcoder.jp/contests/abc065/submissions/16068331 | 手戻りなし。3回目なので流石にネタを知っている、この問題設定では MST に含まれうるのは x座標とy座標でソートした時に隣り合う点を含む辺のみ。 |
68 | 2:34 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783941#1 | + と * を typo して1回もどり(そんなことある?) |
69 | 10:59 | https://atcoder.jp/contests/abc084/submissions/16175469 | 1 を素数にしてしまい1回戻り、これ本質は 累積和 なのでは…… |
70 | 2:28 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4784031#1 | かけた時に mod 取り忘れて1回戻り、毎回蟻本版非再帰はかしこいなあとなる |
71 | 14:06 | https://atcoder.jp/contests/s8pc-1/submissions/16178360 | 今いる場所を更新するのを忘れて1回戻り、これも本質は累積和…… |
72 | 8:39 | https://atcoder.jp/contests/abc034/submissions/16178666 | H+W が 105 を超えうるのを忘れて1回戻り |
73 | 13:09 | https://atcoder.jp/contests/abc145/submissions/16179230 | 手戻りなし、基底ベクトルがちょっと変な座標平面で経路数える問題をやるだけ |
74 | 63:04 | https://atcoder.jp/contests/abc021/submissions/16182256 | O(nk) DP の計算量の見積もりを間違えて1TLE、その後DPテーブルを見るとパスカルの三角形になっていることに気づいてAC |
75 | 解説AC | https://atcoder.jp/contests/abc149/submissions/16202402 | むずい、期待値の線形性から各ノードの寄与度を個別に計算してよい、全方位木DP が必要そうな気持ちになって手が止まるんだけど、根つき木にした時に子側のノード数は木DP、親側のノード数は全体から引けば求まる(典型)(CF665 Div2 Dでも出た) |
76 | 8:18 | https://atcoder.jp/contests/nikkei2019-final/submissions/16214202 | 手戻りなし、累積和で区間和を高速化するとO(N2)で全探索できるようになる |
77 | 15:25 | https://atcoder.jp/contests/joi2010ho/submissions/16233240 | 区間和を累積和で高速化するだけ、あまりを取り損ねて1回戻り |
78 | 31:11 | https://atcoder.jp/contests/joi2011ho/submissions/16253199 | 実は2D累積和ははじめて、けんちょん氏の記事を見ながら頑張って書いたものの半開区間の感覚がバグってクエリ時の +1 を忘れてバグらせた(ちなみにけんちょん氏の記事の2D累積和はクエリ時のxとyが逆?) |
79 | 26:59 | https://atcoder.jp/contests/abc106/submissions/16272131 | 2D累積和を構築するときに0-indexedと1-indexedを間違えて1回戻り、1回解いてネタを知ってる + 累積和という情報あり、というかなりのズル、包含される区間の個数は2D平面にプロットすると累積和で高速に求められるのであった。 追記: 実装に若干嘘を埋めていて、入力が L <= R を期待しているコードになっている(L > R なる区間を足してしまっているが、そこが0であることを期待している)。今回の制約はそうなので、通る。 |
80 | 31:18 | https://atcoder.jp/contests/gigacode-2019/submissions/16463172 | 素直に2D累積和すると全探索できる。試しにライブラリ形式で実装してみた、べた書きだとインデックスを間違えがちなので相性はよさそう |
81 | 3:43 | https://atcoder.jp/contests/abc014/submissions/16475363 | 素直な imos 法するだけ |
82 | 23:15 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4813839#1 | 素直な imos 法するだけ、時刻のパースがヘタクソすぎる |
83 | 22分程度(CEDEC見ながら) | https://atcoder.jp/contests/joi2015ho/submissions/16478616 | imos をすると各路線を何回通るかわかるので、どちらがお得か計算可能 |
84 | たくさん | https://atcoder.jp/contests/joi2012ho/submissions/16489765 | 三角形のいもす法をいもす研ガン見しながらやった、変な座標系に対するいもす法の構築は目新しかった |
85 | 7:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4816695#1 | UF のライブラリを再実装してから解いた、 root の else 節で値を返し忘れておりデバッグした |
86 | 4:02 | https://atcoder.jp/contests/abc075/submissions/16500077 | 除く辺を全探索できる |
87 | 15:46 | https://atcoder.jp/contests/abc120/submissions/16521383 | UnionFind は分離できないので手順を逆回しして併合にする。最初の0が要らないのに気づかずちょっとデバッグした |
88 | 19:06 | https://atcoder.jp/contests/joi2008ho/submissions/16534292 | (色, 個数)のペアを保持する。置き換えが発生したとき、置き換えによって2つ手前の集合と同じ色になる場合マージする必要があることを忘れて1回戻った。毎回適切にマージすると保持される区間の色は交互になる(ex: 0, 1, 0, 1...)はずなので、計算量は悪化しない。 |
89 | 82:12 | https://atcoder.jp/contests/joi2013ho/submissions/16537069 | ランレングス圧縮した後同じ色が{2, 3, 4以上}連続する時について丁寧に場合分けする、2の場合が複雑でつらかった 解説を読むと交互列の長さでランレングス圧縮しており、かしこい |
90 | 24:00 | https://atcoder.jp/contests/s8pc-5/submissions/16550535 | 最小値の最大化なので二分探索(二分法)をする。最小半径 r を固定するとそれが可能かどうかはO((N+M)2) で判定できて十分高速。 |
91 | 27:49 | https://atcoder.jp/contests/abc144/submissions/16558668 | 平面図形の問題に落とせる、2回計算ミスした |
92 | 48:20 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4820842#1 | y座標ごとに始点をリセットするのを忘れて1バグ、デバッグに苦労した |
93 | 40:10 | https://atcoder.jp/contests/s8pc-3/submissions/16587818 | 落下処理とスコア計算処理を 92 から使いまわしたものの結局バグっていた、定数倍気にしなければ各行をランレングス圧縮してK以上だったら消える、とするのがいいのかも |
94 | 38:38 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4824261#1 | 計算量はたいしたことないので vector::erase を使ってサボれる。 |
95 | 6:33 | https://atcoder.jp/contests/abc149/submissions/16604842 | 貪欲 |
96 | 5:52 | https://atcoder.jp/contests/abc139/submissions/16604984 | i mod j (i < j) は i なので、1, 2, ..., N を1反時計回りにずらした Pi を考えると良い、適当にいじっていればすぐに思いつくけど、こういうのを直感以外で思いつくのはどうすればいいんだろうね |
97 | 43:33 | https://atcoder.jp/contests/abc150/submissions/16622766 | 式変形すると ak の奇数倍が 2X になればよいことがわかるので、全体の lcm の奇数倍が 2X 以下であるものを数えればよい。ただし、 ak の偶数倍が lcm になるときは解がなくなることに気を付ける。(lcm の奇数倍が ak の奇数倍ではないため) |
98 | 7分くらい | https://atcoder.jp/contests/sumitrust2019/submissions/16648910 | 各人を独立に考えてよくて、前から見て人iを見た時に A_i-1 の登場回数 - Ai の登場回数 通りの色があることがわかる。 |
99 | 155:24 | https://atcoder.jp/contests/ddcc2020-qual/submissions/16666763 | 操作の順番は回数に寄与しないという考察はそこそこ早く出たものの、へんなバグらせをして無限に時間をかけてしまった |
100 | 31:40 | https://atcoder.jp/contests/tenka1-2018-beginner/submissions/16749495 | 集合を頂点、共通の数を辺とみなすと完全グラフの辺にちょうど1-Nの数字を振れればいいことがわかるので、その通りに構築する、出力フォーマットを間違えて1WA |
メモ
19: こういう「二分探索して自分以下の数があれば返す」みたいなクエリはライブラリ化してもいいかもしれない(upper_bound -> begin じゃなければ一個もどす)
感想
- 1日1問やるにはちょうどいい難易度だった
- 簡単すぎ、と思うこともややあったけれど、全体的に見れば簡単すぎ、と言ってはいけないくらいの時間がかかっている問題が多いのでやっぱりちょうどいい難易度だった気がする
- 実装がやや複雑そうなときだけ疑似コードを書いたけれど、しょうもない添え字バグとかは減った……気がする
- それでも全体的にしょうもないバグ埋める率は高め……
- DP の部分がめちゃめちゃいい練習になった
- ライブラリ縛った意味はそこそこあった気がする、少なくともここに上がっているアルゴリズムとデータ構造で理解に不安が残るものはなくなったはず
*1:一筆書きの閉路なので、どこが始点になろうが解が存在するなら長さは同じはず
蟻本をする2(中級編)
ymduu.hatenablog.com
の続き、こんどは中級編だ
例題 3-1-1 lower_bound
自力: 〇
lower_bound やるだけ
類題
自力: 〇
https://atcoder.jp/contests/abc077/submissions/10357158
Bを決めた時に使えるCの場合の数を累積和しておけばA固定でも解ける、Bを固定するとそういう小細工をしなくても解ける
3つの変数がうごく -> 真ん中(のこり2つの両方に直接影響する) を固定すると嬉しいことが多い
例題 3-1-2 Cable Master (POJ No.1064)
自力: 〇
解を仮定して二分探索シリーズ
類題:
自力: 〇
https://atcoder.jp/contests/abc023/submissions/10373489
受けるペナルティを固定すると、各風船を何秒以内に破壊すべきかがわかるのでソートすれば可能かどうかをNlogNで判定可能
例題 3-1-3 Aggressive Cows (POJ No.2456)
自力: 〇
上と同様に最小値を決め打ちすればOK
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2015-quala/submissions/10421073
例題 3-1-4 平均最大化
自力: ×
解xを固定すると、その解が可能かどうかは式変形により貪欲に判定できるようになるパターン
類題:
自力: 〇
https://atcoder.jp/contests/abc034/submissions/10422151
例題 3-2-1 Subsequence (POJ No.3061)
自力: 〇
oldskool しゃくとり
類題:
自力: 〇
https://atcoder.jp/contests/abc032/submissions/10506572
例題 3-2-2 Jessica's Reading Problem (POJ No.3320)
自力: 〇
ある要素aの個数が0になった時は次のaが現れるまでrを進める、とすると実装が楽になる
類題:
自力:〇
https://atcoder.jp/contests/arc022/submissions/10524534
上に同じ
例題 3-2-3 Face The Right Way (POJ No.3276)
自力: ×
ライツアウトの結果は操作を行う場所の集合にのみ依存し、順番には依存しないことに気を付ける。
これさえ分かっていれば、左から順番に決めていくことで問題のサイズを1ずつ小さくすることができる。
ただし、この問題はそれだけではだめで、数列 f において、区間 [l, r] の和は、[l-1, r-1] + f[r] - f[l-1] で表せることを利用して差分だけ更新していく必要がある。
-> 長さNの数列において、固定長の区間を全走査したい場合は差分更新することでO(N)にできる
類題:
自力: 〇
https://atcoder.jp/contests/arc064/submissions/10538540
端から順番に決めていく系
例題 3-2-4 Fliptile (POJ No.3279)
自力: ×
今度は上1行を固定すると全体のひっくり返し方が決まるパターン
類題:
自力: 〇
https://atcoder.jp/contests/joi2008yo/submissions/10544690
例題 3-2-5 Physics Experiment (POJ No.3684)
自力: 〇
蟻と同じ考察をすればオッケー
類題:
自力: ×
https://atcoder.jp/contests/agc013/submissions/10667472
蟻の考察をすると蟻の順番は変わらないことがわかるけれど、その先で0番の蟻がどこにいくのか分からずgg
けんちょんさんのブログを見て、原点を左右に通過する蟻の数を数えると最初の位置からいくつズレたかが分かるのでOK
例題 3-2-6 4 Values whose Sum is 0 (POJ No.2785)
自力: 〇
くじびきと同じ
類題:
自力: 〇
https://atcoder.jp/contests/joi2008ho/submissions/10756669
例題 3-2-7 巨大ナップサック
自力: ×
類題: 〇
実装が重くてしんどい、DPの方のナップザック問題はソラで書けるようになっていたので成長をかんじる
https://atcoder.jp/contests/abc032/submissions/10771038
例題 3-2-8 領域の個数
自力: ×
線がある座標の±1の場所も含めて座圧するのがポイント
類題:
自力: 〇
AOJ で解いたんだけどURLがどっかいってしまった
例題 3-3-1 Crane (POJ No.2991)
自力: ×
つらい
類題:
自力: 〇
https://atcoder.jp/contests/arc008/submissions/10939720
手で試すとちゃんと結合則が成り立ってエモいです、ついでに座圧の復習もできてアド
例題 3-3-2 バブルソートの交換回数
自力: ×
類題:
自力: 〇
https://atcoder.jp/contests/chokudai_S001/submissions/10963786
転倒数、こわそう、と思っていたけど前から順番にセグ木で出てきた数を覚えておいて今見ている数より大きい数の個数を数えるだけだった、こわくない
例題 3-3-3 A Simple Problem with Integers (POJ No.3468)
自力: 〇
類題:
RSQRAQ
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4270233#1
例題 3-3-4 K-th Number (POJ No.2104)
自力: 〇
類題:
自力: 〇
https://atcoder.jp/contests/arc033/submissions/10982608
平方分割はセグ木の深さを1にして各ノードの区間長をsqrt(N) にした感じ、実装が軽いのに一点更新区間取得が超定数倍軽いsqrt(N)でできてえらい
例題 3-4-1 巡回セールスマン問題
自力: ×
類題:
自力: △(ソラで書けず)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4281785#1
例題 3-4-2 Traveling by Stagecoach (POJ No.2686)
自力: 〇
bitDPというよりも拡張ダイクストラのような?
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4282437#1
脳内でなく例題をAOJでACしたので類題は無し
例題 3-4-3 ドミノ敷き詰め
自力: ×
dp[i][j][S] := i行j列まで埋まっていて、下端の状態がSの時の場合の数 なるbitDPをする
類題:
自力: 〇
https://atcoder.jp/contests/code-festival-2014-quala/submissions/11078114
dp[i][j][S] := i(1-indexed) 桁目まで決めたとき、状態jであり使っている数の集合がSであるときの差の最小値というDPをした
— AIRをプレイする (@ymduu) 2020年3月22日
104 1 みたいな時は 111 でなく 99 が最適であることを見逃してWAしたもののストレステストで無事発見でき、かなりの良さ
— AIRをプレイする (@ymduu) 2020年3月22日
例題 3-4-4 フィボナッチ数列
自力: ×
漸化式のn番目は漸化式を一つすすめる行列を定義してその行列をかけることで求められる。
は、という感じだけど言われればまあそうだね、という感じだし行列積の手続きからも自明
類題
自力: 〇
https://atcoder.jp/contests/abc009/submissions/11369837
演算が特殊でも演算が半環をなしていれば行列積が計算できるのでgg
例題 3-4-5 Blocks (POJ No.3734)
自力: ×
http://poj.org/showsource?solution_id=21536909
DP 高速化 としての行列累乗、結局赤の偶奇と緑の偶奇で4通りしか状態がないので O(N) のDPは自然に思いつくはずで、それを行列累乗で高速化する。
最初 2 * 2 の 行列を考えてハマったけどこういうのは1列の行列で考えると見通しがよくなりがちっぽい
類題
POJ で実装までやったのでなし
例題 3-4-7 Matrix Power Series (POJ No.3233)
自力: ×
http://poj.org/showsource?solution_id=21552608
知ってるかゲーって気はするけど
類題
POJ で実装までやったのでなし
例題 3-4-8 Minimizing Maximizer (POJ No.1769)
自力: ×
POJ だと C++ の新しい機能バリバリの抽象化セグ木が使いづらいので、1点更新区間min のセグ木を写経した、よい復習になった
http://poj.org/showsource?solution_id=21553375
類題: POJ で実装までやったのでなし
てか類題が赤 diff ばっかりなんだが
ついにフローにたどりつきました
例題 3-5-1 最大通信量
例題はなし
類題:
自力: △(蟻本のF-Fを使ってるライブラリに合わせて改変しつつ写経した)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4329720
自力: 〇
マークしてる人から辺を張るノードを一つ用意してそこにたどり着けなくするための最小カットを求めればOK -> 最大流最小カット からフローを流せばOK
例題 3-5-2 仕事の割り当て
自力: 〇
二部グラフの最大マッチングは知っていたのでフローを持っていれば解けるね
類題:
自力: 〇
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4330160#2
自力: 〇
https://atcoder.jp/contests/abc091/submissions/11633199
例題 3-5-3 はたいへんなのでパス(は)
例題 3-5-4 最小費用流
自力: ×
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4336350#1
残余グラフにおいて、辺に流すときのコストを距離と見て最短経路問題を解き、その最短経路(つまり、最小コストで s-t に流せる経路)に流せるだけ流すことを繰り返す。
例題 3-5-5 Asteroids (POJ No.3041)
自力: ×
http://poj.org/showsource?solution_id=21562701
X 座標と Y 座標 をグラフのノードとみなし、隕石があるところに辺を張った二部グラフを構成する
そのようなグラフの最小点カバー問題を解けばよく(点 = ビームを撃つ X or Y座標)、これは二部グラフの最大マッチングに等しい
類題:
https://atcoder.jp/contests/soundhound2018/submissions/11692524
- グリッドグラフは市松模様に塗ると二部グラフ
- (x + y) もしくは (x - y) の偶奇でどちらに属するかを判定可能
- 二部グラフの最大マッチングをするときには、2つの集合をU, V として U -> V みたいに向きを付けておかないとフローを流すときに戻れてしまい終わる
- 最大安定集合(ノード同士が隣接しないようになるべく多くのノードを取る) -> 最大マッチングから計算できる、蟻本P199参照
例題 3-5-6 Evacuation (POJ No.3057)
自力: ×
この辺からくるしくなってきた
時間を固定すると(各時間,各ドア)から出られうる人間 という 二部グラフが作れるので、最大マッチングが人間の数だけあればOK
類題:
自力: ×
https://atcoder.jp/contests/arc013/submissions/11709738
作れうる各重さに関して高橋君のノード、青木君のノードを作成し、それらと鉄塊を表すノードを繋いだ二部グラフに始点終点を追加したもの に対してフローを流そうとしたが嘘なのでGG
正しい方法は、各重さについて2個以上作れればよいので、各重さを表すノードを2個ずつ作り、それらが同時に作れる場合(≒一つの鉄塊から切り出せる場合)に辺を張る。
そうして構成したグラフは二部グラフになり、「各重さが2つ以上作れる」 とは、このグラフの辺を適切に選んで、どの頂点も選んだ辺に接続している 状態にできればよい。
これは最小辺カバー問題であるので、最大マッチングから求めることができる。(蟻本P199参照)
なんだかお気持ちは Asteroids と同じ気もする
二部グラフに落としたいなあという気持ちがあって、{XY, 作れる重さ}を二部グラフの集合として、{隕石がある, 同時に作れる}を辺として、それの{最小点カバー, 最小辺カバー}を求める。
例題 3-5-7 Dining (POJ No.3281)
自力: ×
(食べ物, 牛), (飲み物, 牛) の同時割り当てを求める問題。
食べ物 -> 牛 -> 飲み物 のフローを流したくなるが、それはだめ。
なぜなら、一つの牛に対して複数のフローが流れてしまう可能性があるから(蟻本の例: s->食べ物1->牛1->飲み物1->t とs->食べ物2->牛1->飲み物3->t が同時に流れうるが、これを2頭の要求を満足すると数えてしまう。)
食べ物側と飲み物側のマッチンググラフを分け、同じ牛同士の間に容量1の辺を張ることで、一つの牛には一つの割り当てが行われるようになり(P192 頂点に容量がある場合 の考え方と同じ)、正解となる。
http://poj.org/showsource?solution_id=21566325
例題 3-5-8 Dual Core CPU (POJ No.3469)
自力: ×
燃やす埋める問題、診断人さんのスライドがマジでわかりやすい。
www.slideshare.net
小問題一つに対し、コストのかかる選択肢が2つあってそれを選ぶ、さらにその選択肢間に依存関係がある(グラフに見えてくる)場合は適切なグラフを作り最小カット(=最大流)を計算するとうまくいくことが多い。
気持ちとしては、始点sと終点tを用意して、s -> 選択肢1に対応する辺 -> 小問題に対応する頂点 -> 選択肢2に対応する辺 -> t なるグラフを作って、適切な方をカットする(≒選択肢を選ぶ)ことでs-tカットをつくるぞ、というもの。
蟻本の構築方法を後から見ても若干 ??? という感じだったので先に診断人さんのスライドを見てよかった
http://poj.org/showsource?solution_id=21566683
ところで、Dinic の計算量ってO(EV2)だけど、この問題はV = 2 * 104、E = 2 * 105 で、4 * 1013 で明らかに適用できないサイズに見えるんですけど……
Dinic は速い!とは聞くものの105倍速くなったりするものだろうか、それとも計算量の見積もりを間違えている?
例題 3-5-9 Farm Tour (POJ No.2135)
自力: 〇
http://poj.org/showsource?solution_id=21566867
容量2の最小費用流を流すだけ、逆向きの辺も追加する必要があることに注意(最大流と同じような議論で無向の時は逆辺を張ればいいことがわかる)
この辺全部 POJ で解いているけど、フロー系の問題は Dinic と Ford-Fulkerson と Primal-Dual さえあればあとは個別のアドホックなので、ライブラリを C++03 に対応させる手間が少なくてらくだった
例題 3-5-10 Evacuation Plan (POJ No.2175)
自力: ×
二部グラフの最小重みマッチングは最大マッチングの時みたいに最小費用流を流すことで解ける。
類題:
自力: ×
https://atcoder.jp/contests/abc004/submissions/11717678
例題 3-5-11 The Windy's (POJ No.3686)
自力: ×
http://poj.org/showsource?solution_id=21579994
非直感的な式変形をする問題、工場iでj個のおもちゃを作る時、k番目(0-indexed)に到着した依頼は終了時間の総和にj-k回効いてくることから、工場の頂点を倍加して工場iでk回目の依頼を処理する、というノードを作り、おもちゃlからコスト(j-k) * Z[l][i] とした辺を張る。
例題 3-5-12 Intervals (POJ No.3680)
自力: ×
http://poj.org/showsource?solution_id=21580272
言いたいことは分かるけど自力で思いつくのは無理だなあ、最後だし撤退するのも気持ち悪いので写経AC
蟻本P205のFが一定の時負辺を除去するテクを使っている
これは負辺を除去するために、負辺に目一杯流す≒負辺(u, v)のコストを最初から計上して、代わりにコスト0でu->t, s->v (sは新たに追加した始点、tは新たに追加した終点)に流せる辺を追加するというもの。(これを飲み込むのに2時間くらいかかったので元気が出たらまとめる)
蟻本をする
やりかた: 蟻本読解と類題解きを非同期でやっていく(読みたいときにさくさく先に進むため)
類題を前から1問ずつ解いていってダメだったら適宜戻る、コンテスト中に解いたことがある場合はサボります(最悪)
類題の出典: https://qiita.com/drken/items/e77685614f3c6bf86f44
特別に断りがない限り例題の自力 or notは脳内AC(POJはつらいので)、類題は該当submitを併記
2-1 全探索
グリッド -> グラフライブラリのverifyがてら暇なときに埋めていく予定
例題 2-1-1 部分和問題
自力: 〇
類題: https://atcoder.jp/contests/arc061/submissions/9672420
自力: 〇
bit全探索だね
例題 2-1-2 Lake Counting (POJ No.2386)
自力: 〇
類題: https://atcoder.jp/contests/atc001/submissions/9673321
自力: 〇
例題 2-1-3 迷路の最短路
自力: 〇
類題: https://atcoder.jp/contests/abc007/submissions/9676680
例題 2-1-4 特殊な状態の列挙
自力: 〇
類題: https://atcoder.jp/contests/abc150/submissions/me
自力: 〇
コメント: next_permutationを使う問題というだけ
2-2 貪欲
例題 2-2-1 硬貨の問題
自力: 〇
AtCoder上に類題なさそうだしパス
例題 2-2-2 区間スケジューリング問題
自力: ×
区間スケジューリング問題 -> 末尾でソートして貪欲
区間を見たら先頭 or 末尾 でソート
知らなかったら無から思いつくのはかなりつらくないですか
類題: https://atcoder.jp/contests/keyence2020/submissions/9565253
自力: 〇
コメント: 蟻本やるかーって言いだした直後のこれだったのでラッキー
例題 2-2-3 Best Cow Line (POJ No.3617)
自力: 〇
辞書順最小 -> 先頭から貪欲
先頭と末尾が同じ場合は reverse して比較することで同じ区間を無視して比較できる かしこい
類題: https://atcoder.jp/contests/abc076/submissions/8885620
自力: 〇
例題 2-2-4 Saruman's Army (POJ No.3069)
制約が厳しい順に貪欲(あるある)
類題: https://atcoder.jp/contests/abc083/submissions/9697785
自力: 〇
Fence Repair (POJ No.3253)
自力: ×
小さい順に合成していけばよいというのが非自明だった、言われてみればそれはそうなのだけど
類題: https://codeforces.com/contest/462/submission/69303070
自力: 〇
ほぼ例題そのまんまだった、手順逆回し、大きい集合がたくさん出てくると有利なのでその通りにする
2-3 DP
例題 2-3-1 01ナップサック問題
自力: 〇
知っていたので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4130992#1
自力: 〇
コラム:
貰うDPと配るDPの話、遷移元を意識するか遷移先を意識するか、という気持ちで理解している
個人的には"貰う" でメモ化再帰するのが一番らく(再帰関数が遅延評価っぽく解決してくれるため更新順序を考えなくて済むので)だと思うけど気がついたら配ってたりするのでわからんちん
例題 2-3-2 最長共通部分列問題
自力: ×
知っていたけど覚えていなかったので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131284#1
自力: △
解説見ながら写経しちゃった
例題 2-3-3 個数制限なしナップサック問題
自力: ×
ナップザック問題の、取得できる品物の個数が無限になったバージョン
dp[i+1][j] := i番目の品物から重さの総和がjイカになるように選んだ時の価値の最大値
とすると、 dp[i+1][j] を計算するとき、k(>=1)個品物iを取得する場合、dp[i+1][j-w[i]] を計算するときにk-1個選んだ場合と同様である と考えることができる。(<- 天才)
よって、dp[i+1][j-w[i]] (一つ以上の品物iを取得するかもしれない場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とできる。
ふつうの(01)ナップザック問題では dp[i][j-w[i]] (品物iを取得する場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とすることに注意する。(添え字が違う)
添え字の違いは遷移元の違いなのだなあ、という気持ち
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131387#1
自力: 〇
知ってればそれはできるね、という感じ
例題 2-3-4 01ナップサック問題その2
自力: ×
類題: https://atcoder.jp/contests/abc032/submissions/9813660
自力: △
半分全列挙のところだけ×
例題 2-3-5 個数制限付き部分和問題
自力: ×
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9830320
自力: 〇
DPの値にbool以上の意味を持たせる、って言われていれば素直に思いつく系
例題 2-3-6 最長増加部分列問題
自力: ×
類題: https://atcoder.jp/contests/chokudai_S001/submissions/9839984
まあ りす はDPでNlogNで求められるということを覚えていればよさそう
例題 2-3-7 分割数
自力: ×
解説が不親切シリーズ1
ここが詳しい
dp[i][j] := jのi分割(jのi分割、とはjをi個"イカ"の集合に分割する場合の数、であることに気を付ける、jをi個の集合に分割する場合の数、ではない) としたとき、分割した数の集合をa_k (0<=k<=i) とおくと、
1. a_k == 0 なるk が存在する場合
これはjのi-1分割に含まれるので、 dp[i-1][j]
2. そうでない場合
これは、jをi個の空でない集合に分割する必要があるので、集合が空集合にならないことを保証するためにi個の集合に先に1つだけ振り分けると(大学入試でよく見るヤツです)、dp[i][j-i]で表される
結局、 dp[i][j] = dp[i-1][j] + dp[i][j-i] で更新できる
類題: https://yukicoder.me/submissions/424992
自力: 〇
先に必要数だけ振り分けるという思考をついでに事前計算でもやる問題だった
例題 2-3-8 重複組合せ
自力: ×
解説が不親切シリーズ2
ここが詳しい
emtubasa.hateblo.jp 自分でもちょっと真面目に考えた
j-1に置き換える時のmの扱いに若干誤魔化しがあるけどこれでわかった感 pic.twitter.com/wGSNZduhd6
— AIRをプレイする (@ymduu) 2020年2月1日
類題: https://atcoder.jp/contests/abc021/tasks/abc021_dj-1に置換したときのmはmin(j, a[i])からmin(j-1, a[i]) になっているけど、mがjになるとj-m-1 が負になって、dpの定義からdp[i][-1] = 0 なので、mがjでもj-1でもdp[i+1][j-1] の値は変わらないといえる(ので、正当な式変形と言える)
— AIRをプレイする (@ymduu) 2020年2月1日
自力: 〇
素直な重複組み合わせなのでDPせずnCrのライブラリで殴っちゃった(演習の意味)
2-4 データ構造
例題 2-4-1 Expedition (POJ No.2431)
自力: 〇
類題: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/9867313
自力: 〇
例題 2-4-2 二分探索木 (set, map の練習) 流石に無 + 蟻本に対応する例題がないためパス
例題 2-4-3 食物連鎖 (POJ No.1182)
自力: ×
類題: https://atcoder.jp/contests/arc036/submissions/9868509
自力: 〇
グラフ上で「ある状態で」(今回の場合、移動距離が偶数の状態で)場所Nに到達できるか? -> 拡張ダイクストラ(頂点倍加)
今回は接続性さえわかればいいので、今までの移動距離が偶数であるノードと奇数であるノードを用意してUnionFindでOK
2-5 グラフ
例題 2-5-1 二部グラフ判定
自力: 〇
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9898898
例題 2-5-2 Roadblocks (POJ No.3255)
自力: ×
https://atcoder.jp/contests/abc035/submissions/9926603
複数の街に滞在する意味がないことはすぐにわかる。
帰り道の最短経路がわからないが、単一終点最短経路をしたいときは辺の向きを逆転させたグラフに対して単一始点最短経路をすればよい(賢すぎか?)
例題 2-5-3 Conscription (POJ No.3723)
自力: 〇
類題: https://atcoder.jp/contests/abc065/submissions/9954687
所見の時は思いつかなかった記憶があるけど今回は見た瞬間x軸y軸における両隣に辺を張ればよいことがすぐに思いつけたので、成長
例題 2-5-4 Layout (POJ No.3169)
自力: ×
牛ゲーム、不等式がたくさんあって、それを満たしながら最適化する問題は最短経路問題に落ちるかもということだけ覚えておく
類題: https://atcoder.jp/contests/utpc2013/submissions/9966659
自力: △
よくわかってないところがあり
牛ゲー(不等式 * 大量 の線形計画問題を最短経路に落とすやつ)、なんで負閉路が存在する場合(≒最短経路が存在しない場合)条件を満たす解が存在しないことになるんだろう
— AIRをプレイする (@ymduu) 2020年2月9日
このような不等式をすべて満たすようなdにおけるd(v) - d(s) の最大値がsからvへの最短距離となっています なので、負閉路が存在する場合最短距離が存在せず、不等式をすべて満たすd とやらも存在しなくなってしまうのだ、という話かなあ
— AIRをプレイする (@ymduu) 2020年2月9日
これ以上詳しい理解をしたければ蟻本でしれっと当たり前だが……みたいな顔で登場している"このような不等式をすべて満たすようなdにおけるd(v) - d(s) の最大値がsからvへの最短距離となっています" の理由を理解しないとダメそう
— AIRをプレイする (@ymduu) 2020年2月9日
例題 2-6-1 線分上の格子点の個数
自力: △
(すぐ下にある解説を見てしまった)
類題: https://atcoder.jp/contests/abc070/submissions/9970561
オーバーフローがめんどうでPythonしてしまった
例題 2-6-2 双六
自力: 〇
拡張ユークリッドの互除法やるだけ
類題: https://codeforces.com/contest/1244/submission/71210362
自力: 〇
拡張ユークリッドの互除法でごり押しできる(オーバーフローするので多倍長整数が必要だけど)
試合数に制限があるので、なるべくたくさん勝ったほうが有利であることを考える。
y の範囲は w 未満である(w 回 引き分けるなら d 回勝ったとするほうが試合回数的に有利であるため)ことを考えれば全探索できる
例題 2-6-3 素数判定
自力: 〇
類題: https://atcoder.jp/contests/arc017/submissions/10126400
はい
例題 2-6-4 素数の個数
自力: 〇
類題: https://atcoder.jp/contests/tenka1-2012-qualc/submissions/10127486
自力: 〇
例題 2-6-5 区間内の素数の個数
自力: 〇
類題: https://atcoder.jp/contests/jag2017autumn/submissions/10320359
自力: ×
言われてみれば区間篩なのだけど初見では全然わからんかった、区間[l, r] についてすべての素因数を処理したかったら sqrt(r) までの素数を列挙しておいてエラトステネスの篩っぽく飛び飛びに処理をする(語彙力)とよい区間[l, r]内の prime factor が素数である(a)数を列挙する問題で、sqrt(r)までの素数を列挙しておけば素因数分解がlogでできるので(ここまで自力)
— AIRをプレイする (@ymduu) 2020年2月24日
[l, r] の数を並べておいて、エラトステネスの篩っぽく素数pの倍数だけpで割れるだけ割っていく
sqrt(n) までの素因数を列挙しておけばlogで素因数分解ができるので、たくさん素因数分解をしなければならぬ ときには有効かも
例題 2-6-6 Carmichael Numbers (Uva No.10006)
自力: 〇
類題: https://atcoder.jp/contests/joisc2007/submissions/10322004
くりかえし二条城
類題はTL0.5sec で p = 104 なのに p2 が通るのでびっくりしてしまう(logがつくとダメ、というレベルでTLが厳しいので、すべての数についてn乗を計算しておく、とかvectorを使わない、とか涙ぐましい最適化が必要)
GCJの問題に挑戦
Minimum Scalar Product
自力: 〇
大きい奴には小さい奴をマッチングさせる貪欲なんだけど、どこかで全く同じ問題を見た気がする。
Crazy Rows
自力: ×
先に最右の1の位置(ダジャレ)を計算しておいて転倒数を計算したらいいじゃん、と思ったが嘘で死亡
制約がめちゃめちゃ小さいので1行目からシミュレートして確定させていってもよい
Bribe the Prisoners
自力: 〇
区間DP、これを自力できたのはかなりうれしいので記念に(?)コードを貼っておく
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <numeric> #include <queue> #include <stack> #include <map> #include <set> #include <string> #include <functional> #include <list> #include <random> #include <time.h> #include <iomanip> #include <assert.h> #include <numeric> #define BIT(nr) (1UL << (nr)) #define int long long #define ll long long #define double long double #define mod 1000000007 #define MAXN (int)1e+5 * 2+1 #define LL_MAX 9223372036854775807 //ない環境用 #define LL_HALFMAX 9223372036854775807 / 2 //ない環境用 #define MIN -(9223372036854775807 / 2) #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--) #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define mp make_pair template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; } template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; } using namespace std; int dp[10010][10010]; int A[101]; void solve() { int P, Q; cin >> P >> Q; rep(i, P + 5) { rep(j, P + 5) { dp[i][j] = LL_HALFMAX; } } vector<int> A(Q); rep(i, Q) { cin >> A[i]; } sort(ALLOF(A)); // [left, right) の解を返す function<int(int, int)> rec = [&](int left, int right) -> int { if (dp[left][right] != LL_HALFMAX) { return dp[left][right]; } int cost = LL_HALFMAX; auto lit = lower_bound(ALLOF(A), left); // もしも区間に開放すべき囚人がいなかったら、0 if (lit == A.end() || !(*lit < right)) { cost = 0; } while (lit < A.end() && *lit < right) { int n = *lit; chmin(cost, rec(left, n) + rec(n + 1, right) + (right - left - 1)); lit++; } return dp[left][right] = cost; }; cout << rec(1, P + 1) << "\n"; } signed main() { int T; cin >> T; rep(i, T) { cout << "Case #" << i + 1 << ": "; solve(); } return 0; }
Millinaire
自力: ×
解説が不親切シリーズ
解説を読んでもなにもわからないのでツイッターでググったりしながら頑張って読解した
蟻本のソースにガンバってコメントをつけてみたのでツッコミを募集します
int M, X; double P; double dp[2][(1 << 15) + 1]; void solve(){ cin >> M >> P >> X; int n = 1 << M; double *prv = dp[0], *nxt = dp[1]; memset(prv, 0, sizeof(double) * (n + 1)); // 尻からたどる想定、最後には $1000000 を持っているものとする prv[n] = 1.0; for (int r = 0; r < M; r++) { // 所持金がiから勝てる確率を求める、prv[i] := 今ラウンド後所持金iから勝てる確率、 nxt[i]:=今ラウンド前所持金がiから勝てる確率(尻から見て行ってるので実装上の prv nxt と時系列の前後が逆転することに注意) for (int i = 0; i <= n; i++) { // 所持金がnを超える必要はないので、最大掛け金はi(所持金全部)かn-i(nになるのに不足するぶんの掛け金) int jub = min(i, n - i); double t = 0.0; // jだけかける for (int j = 0; j <= jub; j++) { // 確率Pで勝ち、1-Pで負けるので、確率Pで勝った未来から、確率1-Pで負けた未来から遷移してくる(尻から見ていることに注意) t = max(t, P*prv[i + j] + (1 - P) * prv[i - j]); } nxt[i] = t; } swap(prv, nxt); } int i = (int)X*n / 1000000; printf("%.6f\n", prv[i]); } signed main() { int T; cin >> T; rep(i, T) { cout << "Case #" << i + 1 << ": "; solve(); } return 0; }
試行錯誤の記録
ググってもなにも出てこないし蟻本の解説から実装を理解できないので最後の望み†Twitter†をする
i:所持金
— hogeover40 (@hogeover30) 2016年4月12日
j:賭金
i + j:買った場合の所持金
i - j:負けた場合の所持金
所持金を超える額は賭けられない→ j <= i
所持金がnを超える必要は無い→ i + j <= n → j <= n - i
→ j <= min(i, n - i)#メモ
prv と nxt 、配列を使いまわすことで(2 ** 15) * 15 の配列を取らなくて済むようにしているのか(とっても10^5だしたいしたことはないと思うけど)
— AIRをプレイする (@ymduu) 2020年2月24日
いやでも t = max(t, P*prv[i + j] + (1 - P) * prv[i - j]); の max ってなんの max だ
— AIRをプレイする (@ymduu) 2020年2月24日
ゲームが終わった時点から見ていて、dpの各セルに入るのは ここから勝てる確率 であるので正当でした
— AIRをプレイする (@ymduu) 2020年2月24日
所持金iに対して可能なすべての掛け金jを試して、iになる確率がもっとも高いjを採用しているように見える(これ正当なのか?)
— AIRをプレイする (@ymduu) 2020年2月24日
大人しくdp[i][j] := i番目のゲームが終わった時所持金の区分がjである状態から勝てる確率 としたほうがわかりやすかったのでは……(メモリもおそらく間に合うし)
— AIRをプレイする (@ymduu) 2020年2月24日
確率で勝ったり負けたりするゲームで勝てる確率を計算するときは尻から各状態に遷移する確率を計算するDPをするといいかも、だけ覚えておけばいいかな
— AIRをプレイする (@ymduu) 2020年2月24日