hotpepsiの練習帳

Codeforces Round #192

00:52

Div1 A. Purification

問題

• グリッド状の床がある
• 座標を指定すると、列と行が掃除される
• 呪われている座標は指定できない
• 全て掃除するのに必要な最小の手を求める

方針

• 全ての行または全ての列のどちらかが必要
• 両方とも満たせない場合は無理
• ある行全てが埋まっているかどうかを調べる
• ある列全てが埋まっているかどうかを調べる
• 埋まってない方で手を作る
• Passed System Test

Div1 B. Biridian Forest

問題

• 君は○ケモンマスターだ
• 現在地とゴール地点が与えられる
• グリッドで表される地図上に君と他のトレーナーがいる
• 全員1ターンに一歩ずつ進む
• 君と出会うと戦闘が生じる
• ゴール地点までの戦闘回数の最小値を求める

方針

• 通り方によって結果が変わるかどうか考えてみた
• ゴール地点への距離が自分と同じか短いトレーナーとは必ず戦闘になるので、遠回りするメリットはない
• それぞれのトレーナーのゴールまでの距離がわかればよい
• ゴールからの距離をBFSで求めればOK
• Passed System Test

結果

oo--- 462 + 682(+1) = 1144pt 294th/528 rating 1755 -> 1771 (+16)

距離の初期値を0にしていたため、ゴールに到達できないトレーナーの処理が間違っていて+1。