上級者が解くべき過去問精選 100 50 問 - noko206/AtCoder GitHub Wiki
上級者が解くべき過去問精選 100 + 50 問
これは何？
上級者が解くべき過去問精選 100 + 50 問 の要点や感想をまとめたページです。
座標圧縮
101. DSL_4_A - Union of Rectangles
二次元いもすと座圧。
座圧後の座標なら二次元いもす法で解くことができる。 各座標を $1×1$ の正方形とみなして、それらが元々いくらの面積を持った長方形だったのかを復元する。 あとは、復元した面積を足し合わせれば答え。
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8902163#1
102. ABC 036 C - 座圧
座圧するだけ。
https://atcoder.jp/contests/abc036/submissions/50289673
103. JOI 2013 予選 5 - 魚の生息範囲
三次元いもすと座圧……と思ったけど、計算量的にいもすを使わなくても愚直で間に合う。
そのほうが実装も楽になる。
やってることはほとんど問題101と同じ。
二次元か三次元かの違い。
https://atcoder.jp/contests/joi2013yo/submissions/50289919
104. JOI 2008 本選 5 - ペンキの色
なぜメモリ制限が64MBなのか。
再帰だとメモリが足りなくてスタックオーバーフローしてしまう。
そのため、BFSなど再帰を必要としない実装を採用しなければいけない。
普段は富豪プログラミングしかしていないのでなかなか気づけなかった。
https://atcoder.jp/contests/joi2008ho/submissions/50400137
半分全列挙
105. DPL_4_B - Coin Combination Problem II
半分全列挙をする。
全列挙した配列は何個のコインを使用したかを添え字として管理する。
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8945352#1
106. AtCoder Beginner Contest 032 D - ナップザック問題 の 34 点の部分点
半分全列挙をする。
価値と重みみたいに2つの値があると実装が面倒。
https://atcoder.jp/contests/abc032/submissions/50645005
107. CODE THANKS FESTIVAL 2017 G - Mixture Drug
半分全列挙 + bitDP。
まずは n=20 の解法から考えた。
$O(2^nn^2)$ は 4*10^8 くらいで間に合わないので、 $n^2$ の部分を高速化していく。
各薬品に対して、毒が発生する薬品をビットで管理すると、
「使用した薬品のビット」と「毒が発生する薬品のビットの総OR」のANDが0であればOK。
これで n=20 は解けるので、拡張して n=40 の場合を半分全列挙で考える。
薬品を半分に分割して、それぞれに対して先ほどの操作を行い、グループ内の最適解を出しておく。
それぞれ、グループA、グループBと呼ぶことにする。
グループB ⇒ グループA に対する毒が発生する薬品のビットも管理しておくと、
グループB ⇒ グループA の最適解の候補が求まる。
しかし、最適解の候補は、グループA内で毒が発生する薬品の組み合わせが存在する可能性があるため、
bitDPで部分集合の最適解をchmaxで伝播させておく。
これで、グループBに対する最適なグループAの薬品の個数が求まるため、
問題を解くことができる。
https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/66407097
108. JOI 2015 予選 6 - 財宝
半分全列挙 + 二分探索 + セグ木
$3^{n/2}$ の半分全列挙を行う。
パターンは、
- Annaが財宝を取る
- Brunoが財宝を取る
- どちらも財宝を取らない
市場価値と貴重度に対して、
Brunoが取った財宝の合計 - Annaが取った財宝の合計を計算しておく。
一方を市場価値の合計でソートしておき、
対応する貴重度の合計をセグ木で管理する。
ソートしてない方の市場価値の合計を $x_i$ 、
ソートしている方の市場価値の合計を $x$ とすると、
$|x+x_i| \le D$
$-D \le x+x_i \le D$
$-D-x \le x_i, x_i \le D-x$
となるため、
該当する $x_i$ の範囲を二分探索で求めて、
その範囲の貴重度の合計の最大値をセグ木から求めることで問題に解くことができる。
計算量は $O(3^{N/2}N)$ 。
https://atcoder.jp/contests/joi2015yo/submissions/67027522
行列累乗
109. yukicoder No.526 - フィボナッチ数列の第N項をMで割った余りを求める
3項間漸化式なので、2×2の行列を用いて遷移式が書けないか考える。
$(f_{n+1}, f_n)=(f_n+f_{n-1}, f_n)$
を用いて、
$[f_{n+1};f_n]=A[f_n;f_{n-1}]$
となる行列 $A$ をパズルしていく。
すると、
$A=[1,1;1,0]$
だとわかるので、
$[f_{n+1};f_n]=[1,1;1,0][f_n;f_{n-1}]$
$[f_{n+1};f_n]=[1,1;1,0]^{n-1}[f_2;f_1]$
となる。
あとは行列 $A$ の $n-1$ 乗をダブリングで計算することで、
この問題に解くことができる。
https://yukicoder.me/submissions/1101105
110. AtCoder Beginner Contest 009 D - 漸化式
★解説AC★
ANDとXORは半環になるため行列累乗に乗る。
また、ANDの元は $2^{32}-1$ であることに注意する。（1敗）
線形漸化式は次のような形になることがわかった。
$a_n = c_1 * a_{n-1} + c_2 * a_{n-2} + ... + c_k * a_{n-k}$
$[a_n;a_{n-1};a_{n-2};...;a_{n-k}]=[c_1,c_2,c_3,...,c_{k-1},c_k;1,0,0,...,0,0;0,1,0,...,0,0;...;0,0,0,...,1,0]^{n-k}[a_k;a_{k-1};a_{k-2};...;a_1]$
参考：https://zenn.dev/shibak3n/articles/f08a8ad67a7d14#%E7%B7%9A%E5%BD%A2%E6%BC%B8%E5%8C%96%E5%BC%8F
あとはダブリングするだけ。
https://atcoder.jp/contests/abc009/submissions/67047313
ダブリング（最長共通祖先 [LCA] を含む）
111. GRL_5_C - LCA: Lowest Common Ancestor
オイラーツアー×セグ木で解いた。
AOJ、ACL使えなくて不便すぎて泣いた。
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=10643467#1