■A - チェックディジット
前から順番に処理する。
■B - 蒸気圧
問題の設定がよくわからんけど
min(a,b*c)/b;
要するにmin(a/b,c);
■C - 入力チェック
9桁よりデカければoutなので、
stringで受け取って、文字列長を見てintに
0がコーナーケースだが、サンプルにある。
■D - 書き換え
左から貪欲。
■E - 青木君のいたずら
何も考えずに全パターン試す
■F - ダブルブッキング
mapで日付ごとに管理
日付ごとにimos法
// 6/15 46点 ここまでで初級 25分
■G - べき表現
下から順々に決める
■H - 折れ線グラフ
dp[i][j][k]:=i番目まで、合計がj、直前がk
■I - ほくろ
ABC207-Dの悪夢を思い出す。
c++なら回転はcomplexを使えば容易。
// 9/15 64点 ここまでで中級 65分
// ここからが本番
■J - 終わりなき旅
閉路がないつまりdagかどうかを判定すれば良い
トポロジカルソートのライブラリを貼り付ける。
■K - 急ぎ旅
ダイクストラ
一部long longにし忘れてWA
■L - たくさんの最小値
seg木とsetで状態を管理する
setに対してlower_boundを使うと実行時間も余裕
// 12/15 82点 ここまでで上級 120分
■M - 分割
割と素直な最小費用流
■N - モノクロデザイン
boolの配列を区間でひっくり返るといい。
これは、区間サイズと区間和(trueの数)を持っていれば
区間和をサイズ-和に変更すれば良い。
なので、座圧して遅延セグ木に載せる。
■O - コンピュータ
これただのdpじゃ?
biは単調増加だと思っていい。
単調増加でない部分は、無視してお金をもらうタイミングをずらす。
dp[i]:=i日目に必要なコンピュータを条件を満たすような買い方したときの最小コスト
としたら只の尺取になった。
// 15/15 100点 ここまででエキスパート 240分