読者です 読者をやめる 読者になる 読者になる

純ブログ

ちょっとプログラミングしてる人のブログです。

日本情報オリンピック 2014/2015 予選にオープン参加した

タイトルの通りです.

結果を受けて追記しました. (2014/12/18)

カテゴリ分けしてなかったのでしました. (2016/01/12)

問題 1

やるだけ.

問題 2

これもやるだけ.

落としました.

問題 3

ある区画 (i, j) のいくつ西の小区画に雲があるか数える. 雲が上空にあるなら 0. 雲が上空にも西にもなければ -1.

行末に空白を出力しないように注意.

これも落ちた.

問題 4

dp[i][j] := i 日目に都市 j にいるときの疲労度の最小値

とすると,

dp[i][0] = 0,
dp[i][j] = INF (j > i),
dp[i][j] = min( dp[i-1][j-1]+D[j-1]*C[i-1], dp[i-1][j] ) (else)

という漸化式が立てられる (グラフを書いてみればわかる). min{dp[i][N]} が解.

問題 5

崩壊した城の 8 近傍のみ更新すれば良い.

問題 6

解けなかった.

感想

思ったより簡単だった. 6 問中 5 問提出, 3 完でした...

問題 2, 3 について (2014/12/18 追記)

提出ファイルをダウンロードして確認したところ, なぜか入力ファイルを提出してしまっていました.

本来提出するはずだったファイルとの diff をとってみたところ, すべてのケースで正解のものと一致しました. つまり, 提出ファイルを間違わなければ 5 完できていたようです.

ファイルを提出するときはしっかり確認しましょう (自戒).