kuretchi's blog

競技プログラミング初心者のブログです。

yukicoder contest 166

http://yukicoder.me/contests/168

  • Rank: 24th

テスターを担当したBを含めて3完。

No.525 二度寝の季節

解法

入力を $h$ : $ m $ で受け取って、$ m $ に $5$ を足す。

  • $m \ge 60$ なら $h$ をインクリメント
  • $h = 24$ なら $h$ を $0$ にする

以上を処理し $h$ : $ m $ を出力。

別解1

分に直して計算した後、元に戻す。

別解2

時間を扱う標準ライブラリを使う。

No.526 フィボナッチ数列の第N項をMで割った余りを求める

テスターを担当した。

解法

mod を取りながら計算する。典型。

No.527 ナップサック容量問題

解法

まず $sum(v_1, v_2, \dots , v_i) = V$ のときは、$min = sum(w_1, w_2, \dots , w_i)$、$max = inf$ で終了。

容量 $c$ のナップサックについて 0-1 ナップサック問題を解く関数 $knapsack(c)$ を考える。この関数は典型的な DP で実装できる。

$knapsack(c)$ は単調増加関数なので、$knapsack(c) = V$ となる $c$ を二分探索で求められる。後は $x = c$ と置き $x$ をインクリメントしていくと、$knapsack(x) > V$ となる最小の $x$ が得られる。ここで $max = x - 1$。$min$ も同様に求められる。

所感

明らかに適当解法。ABC063 の D 問題があったので二分探索がすぐに思いついたが、二分探索にしてももうちょっと賢く使えないものか。想定解は、価値に対して重みを最小化する DP (あとで考えて追記します)。

余談

いつも使っているマクロの欠陥に気づけた。