■A - ○✕ゲーム
ジャッジが2^5ケースあってウケる
前から3文字セットで見てくだけ
■B - 上書き
それより後ろに同じ文字があれば採用しない
なければ採用するに読み替える。
■C - 三十六進法
N%36;
N/=36;で下から構築
0==inputがコーナーケース？
■D - リーディングゼロ
そのままだとstd::sortに打ち込んでも意味がないので
sort関数を自作する
文字列長が同じにしてなら比較するために
11と0012なら0011と0012にして比較
11と0011は0011と0011の比較になるが、その場合は0011が優先されるように
■E - ハンコ
90度回転させて4試す
SはsetでTはvectorで#の位置を保持しておく
90度回転後は-2 * max(H,W)から2 * max(H,W)までずらせばいいので
ずらした後のT＃がS＃と一致したらNG
ずらした後のT＃がH*Wの範囲外ならNG
としてO(max(H,W)^2 * H * W)で可能
■F - 一触即発
問題文がわかりにくない？
bit全探索でO(2^N * N * M)
解説を見たらO(2^N * M)に落ちると書いてた
■G - ヘビ
dfs
制約が小さいといっても16!は無理ですが
全探索しても16*3^16にもならないので終わります
■H - コンベア
bfs
pastはとりあえずbfsとdfsがかければ中級まではいけます
全頂点からやるのは無理なのでゴールからたどってそこに行けるかどうか
■I - 避難計画
Hに続いてbfs
避難所起点でbfs
■J - 長い長い文字列
指されている文字はどこから来たものなのかを考える
後ろから見ていって状態を戻していくといつか最初に足されたタイミングにぶつかるのでそこが答え
■K - 的あて
tdpcのjがほぼ同じ問題
■L - T消し
tdpcのiがほぼ同じ問題
■M - 棒の出荷
二分探索
■N - 旅行会社
セグ木上での二分探索
これはaclに備わっているので貼るだけ
■O - 通知
やるだけと思ってやるとTLEしてしまうので
O(QN)やO(QM)をO(Q*sqrt(N or M))程度に落としたい
なので友達の数が多い少ない(sqrt(M)以上or未満)で処理を変えると良い
■感想
M,Nがわりかし簡単な割にK,LのDPが初見だと少し厳しそうに見える。
傾向としてdfs,bfs,dpが適切にかければ上級(Lまで)
後ろ３つのどれか２つが解ければエキスパート。
