AtCoder ABC277

当面の目標

1. 競技プログラミングに復帰する
2. AtCoder Beginner Contest を半年続ける
3. ブログに感想を書く

久々に競技プログラミングに復帰しようと思い、ABC 277に参加した。結果は2問。CのTLEがどうしても消えず、ABのみ。なかなかの惨敗である。

atcoder.jp

A問題、B問題

事前準備として、ABは何問か解いており、BはAより一段難易度が上がったように感じ最初中々解けずにいたが、実はそんなに難しくないということに気づいてから連続でぱぱっと解けるようになった。本番でも二つで10分はかかっていない。

C問題

梯子の数N=10^5と、階数A,B=10^9がある

1. 梯子は両方向に移動できる
2. 1階からどこにも行けないパターンもある

ぐらいの注意点でWAは消えた。

1. 最初は再帰で探索→TLE
2. メモ化（一度探索したところは探索しない）→TLE
3. 再帰を諦め、バブルソートのようにNの二重ループで、梯子の両側の階から行ける最大の階を更新していく方式に。（階、最大の階）にmapのfindを使っているので、N^2 log(N)ぐらい？→TLE
4. 階数は疎（スパース）なので、最大2Nの連続した整数に変換できる。（階、最大の階）の保持と検索にvectorとO(1)を使えるので、N^2→TLE

ここで心折れる。ABCへの参加は初めてだが、C問題からすでに計算量を考えてアルゴリズムを組まないと行けないのか？C++なのに。次回までにこれのC問題もやって感触をつかまなければ。

qiita.com