競技プログラミング

ECNA 2016 - D: Lost in Translation ★★☆☆☆

評価・感想 制約小さくて想定解とは異なる気もするけど、 DAGなら最小有向全域木の1ステップ目で終わるというのが面白かった。 問題 Englishで書かれた本があり、それをnヶ国語に翻訳したい。 m人の翻訳者の候補が居て、i番目の人は言語を言語(またはその逆)…

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - G: Maximum Islands ★★★☆☆

評価・感想 フローと塗りつぶしの2ステップがあるけどそこまで実装重くなく, 教育的良問だと思った. 二部グラフの最大安定集合は二部グラフの最小点カバーになって最小カットになって最大流になってすごく楽しい. 二部グラフの最大マッチング=最小頂点被覆 …

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - F: Illumination ★★★★☆

評価 2-SATに見えない良問. dfsしてしまいWA, 同値類で分解できるじゃーんと言ってUFしてWAした. 問題 n×nのグリッドのいくつかのマスに照明がある. 照明は全部でL個あり, 照明iは, に配置されている. 各照明は上下または左右に距離Rまで(合計2R+1マス)照ら…

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - B: Buggy Robot ★★★☆☆

評価 良問だが若干実装疲れた. 初め, dijkstraに見えなかった. 解くのにそんなに時間がかからなかったし若干実装重いB問題かーくらいの感覚だったけど, 解いてる人数少なくて驚いた. 問題 迷路と操作列が与えられる. 操作列はUDLR(上下左右)からなる文字列で…