Open11
競プロ典型90問☆4
ほき001
問題リンク
考え方
最大値を最小化（逆も然り）する問題は答え二分探索で解けることが多い．
切断されてできる羊羹のサイズをl以上にできるかどうかで二分探索する．
端から見ていけばいいので1回にかかる計算量はO(N)で全体の二分探索はO(logL)なので間に合う．
ACコード
ほき003
問題リンク
考え方
木の直径を求めろという問題．遠い2頂点のパスの長さを求めれば良い．
任意の点からDFSで最も深い頂点を見つけて，その頂点からもっとも深い位置にある頂点を探す．
ACコード
ほき008
問題リンク
考え方
dp[i][j] := Sの最初のi文字目から抜き出して"atcoder"のj文字目まで一致するような方法の個数
として解ける．
ACコード
ほき012
問題リンク
考え方
連結成分はUnionFindで解ける．
ACコード
ほき026
問題リンク
考え方
隣り合わない＝2色で交互に塗ったときの同じ色
木は必ず二部グラフなので，辺で結ばれた頂点を必ず違う色で塗ることができる．
木を2色で塗った時に，必ず片方の色は頂点数/2以上なので，多い方の頂点グループを出力する．
ACコード
ほき028
問題リンク
考え方
複数の領域を重ね合わせるので，二次元いもす法を使う．
ACコード
ほき034
問題リンク
考え方
端から範囲を伸ばしていくと，範囲内に含まれる数字の種類は単調増加する．
単調増加するので，限界まで範囲を伸ばして，超えたら端を動かすように尺取をすれば良い．
ACコード
ほき042
問題リンク
考え方
9の倍数は各位の和（桁和）が9の倍数かどうかで判別ができる．
Kが9の倍数のとき，桁和がKの整数が全部で何個あるか数えれば良い．
これは動的計画法で表すことができて，桁和がKの整数は先頭の桁がNで桁和がK-Nの整数の組をあわせたものになる．
ACコード
ほき043
問題リンク
考え方
方向転換をしたらコストを1追加するようにして最短経路問題を解く．
ACコード
ほき058
問題リンク
考え方
周期性があるので，それに着目する．
ACコード
ほき063
問題リンク
考え方
Hの制約が小さいので，Hに着目した全探索をする．
ACコード