■A - ケース・センシティブ
書いてるとおりにやる
■B - ダイナミック・スコアリング一
瞬ん?となるけど素直にシュミレーションするだけ
■C - 等比数列
1 == R は別処理して、とかしなくても通るオーバーフローだけ見ればいい
■D - 電光掲示板
char D[10][15] = { {'#','#','#','#','.','#','#','.','#','#','.','#','#','#','#'}, {'.','#','.','#','#','.','.','#','.','.','#','.','#','#','#'},
{'#','#','#','.','.','#','#','#','#','#','.','.','#','#','#'},
{'#','#','#','.','.','#','#','#','#','.','.','#','#','#','#'},
{'#','.','#','#','.','#','#','#','#','.','.','#','.','.','#'},
{'#','#','#','#','.','.','#','#','#','.','.','#','#','#','#'},
{'#','#','#','#','.','.','#','#','#','#','.','#','#','#','#'},
{'#','#','#','.','.','#','.','.','#','.','.','#','.','.','#'},
{'#','#','#','#','.','#','#','#','#','#','.','#','#','#','#'},
{'#','#','#','#','.','#','#','#','#','.','.','#','#','#','#'},};
みたいなのを作るの時間がかかった。
■E - スプリンクラー
QとNが小さいので一番最悪でもO(QN)
■F - 回文行列
やるだけ
■G - グリッド金移動
典型BFSと思いきや、無限に広がると書いている。
だが[-200,200]より上下に一つ広げた[-201,201]だけ見れば十分なので
座標を全て(+201,+201)して
start(201,201) end = (201+X,201+Y)としてBFS
■H - ハードル走
dp[i+1] dp[i+2] dp[i+4]に配るdp
ゴールを飛び越えるときのみ微調整
■I - 行列操作
毎回全部入れ替えるとTLEするので
転置しているかどうかと、x列の並び、y列の並びをそれぞれ保持しておく
答えがintで収まらないことに注意。
■J - 回転寿司
セグ木+二分探索
■K - コンテナの移動
プログラム入門書のポインタ編とかに載ってそう
文字列クラスの自作とかでnext繋いでとかありますよね
■L - スーパーマーケット
セグ木を二本持つ。
商品がないなら-1とか入れとけばOK
■M - 行商計画問題
巡回セールスマン。
N地点あるが、K地点+スタート地点間の距離だけわかればいいから
それぞれからbfsをする。
あとはdp[1<<(K+1)][K+1]で今まで行った場所と今いる場所。
■N - 入れ替えと並び替え
無理でした。
A[i] > A[i+1]な箇所だけ覚えておいて
lowerboundとか使ってうまいことすれば間に合うらしい
■O - 輪投げ
フロー。
最大と書いているけど最小費用流なやつ
ACLは負のコストに対応していないので微調整をする必要がある。