チラシの裏.htm

メモとか記録とか雑記とか

ABC 001

A

Submission #2098051 - AtCoder Beginner Contest 001

入出力の練習

B

Submission #2098047 - AtCoder Beginner Contest 001

if祭り

C

Submission #2098026 - AtCoder Beginner Contest 001

風力は2分探索で、風向きは剰余を使って求める。

↑の実装では風程を60で割って風速を比較しているが、誤差を考慮するなら風速を60で掛けて比較した方が良さそう。今回は偶々問題は無かったけど。

D

Submission #2097697 - AtCoder Beginner Contest 001

雨が降っているかどうかを配列で管理する。各要素は 0:00~0:05, 0:05~0:10, ... のそれぞれの時間帯の状態に対応する。最初に配列を0で初期化し、与えられた時間帯と対応する要素に1を加算するという風に累積和を取ることで、値が正なら雨が降っている状態、値が0なら降っていない状態をそれぞれ表現できる。正の値が連続する時間帯が答えになる。

実装は単純だが入出力や配列の添字で結構手こずった。猛省。

ABC 087

A

Submission #2090176 - AtCoder Beginner Contest 087

特筆事項無し

B

Submission #2090240 - AtCoder Beginner Contest 087

可能な硬貨の支払い方を全て試せばおk

 {10a + 2b + c = x\,(0 \leq a \leq A, 0 \leq b \leq B, 0 \leq c \leq C, x = \frac{X}{50})} を満たす  (a, b, c) の組を求める問題なので  O(1) で解ける気がしなくも無い。一応  {2(5a + b) = x - c = 2k\,(k: \text{整数})} とすることで不等式制約を満たす格子点 {(x, k)}を求める問題に帰着されるけど、制約に対応する領域の形に応じて場合分けするのが割りと面倒くさそう。

C

Submission #2090297 - AtCoder Beginner Contest 087

 深さ優先探索

D

Submission #2095728 - AtCoder Beginner Contest 087

頂点数  {N} で辺  {(L_i, R_i),(R_i, L_i)} のコストがそれぞれ  D_i, -D_i となる有向グラフを構成する。頂点は  x 軸上の人に、辺は2頂点間の距離の制約にそれぞれ対応する。グラフの各連結成分内で1点の座標を適当に固定すると他の成分内の座標も自動的に決まることを利用し、幅優先探索で隣接する頂点の座標を計算して既に求められた座標の値と合っているかどうかをチェックする。これを全ての点の座標が計算済みになるまで繰り返せば良い。

ある連結成分内の幅優先探索を終える度に座標を毎回リセットするというミスに気づかずTLEを起こしまくった。恥ずかしい。