AtCoder Beginner Contest 080
Updated:
Source codes
Solutions
A - Parking
$\min(AN, B)$ を出力する。
B - Harshad Number
まず $X$ を文字列で受け取り、普通に $f(X)$ を求め、 $X$ を割り切れるか判定する。
C - Shopping Street
ビット演算を使う。 $i = 1, \dots, 2^{10} - 1$ を試せばよろしい。
ポイント
問題文が読みづらかった。
D - Recording
まず最初は、連続した番組を連結させる。今回は bool broad[30][100010]; で $s[i] - 1, \dots, t[i] - 1$ を塗りつぶせば十分である。あとは各時間での同時放送数を求めればよろしい。その最大値が答えであるが、論証は以下の通りになる。
区間 $\{ [x _i, y _i) \} _{i \in N}$ を録画するのだが、まず tuple<int, int> X; を定義し、組 $(x _i, 1)$ と $(y _i, 0)$ を vector<X> V; に入れる。これをソートして、順に 2 要素目を見る。 $1$ だったらカウンタを足す、 $0$ だったらカウンタを引く。こうすると、カウンタの数は、そのときに使っている録画機器の数に一致する。録画機器にあらかじめ番号を付けるのではなく、スタックに入れておくと考えておく。録画開始時刻には録画機器をスタックから出して対応するしかない。録画終わったら、その録画機器を解放して良いからスタックの中に入れて良い。最終的にスタックから取り出したことのある最大録画機器数が答えである。
ポイント
頭の回転が遅くてうまく時間内に解けなかった。
あと $i, j$ を間違え、さらに c[i]--; を忘れていた。
Others
A - sample: 3, tle: 2.000, time: 01:42, from_submit: 38:58
B - sample: 3, tle: 2.000, time: 01:21, from_submit: 37:37
C - sample: 3, tle: 2.000, time: 11:20, from_submit: 26:17
D - sample: 3, tle: 2.000, time: 26:17, from_submit: 00:00