単純な全探索で解ける！ 累積和で高速化したり DP したりしても OK 問題へのリンク 問題概要 のマス目があり、上から 行目、左から 列目のマスをマス と表すことにする。マス には ​ 個のアメが置かれている。 あなたははじめ、左上のマス にいる。 右方向ま…

EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それぞれの日において責任者が誰なのかが…

いくらなんでも 2 分で解ける問題とは思えないのですが... 問題へのリンク 問題概要 2 × N のグリッドが与えられる。最初はグリッドのマスはすべて「通路」の状態であって、マス (1, 1) からマス (2, N) に到達することができる。以下の q 個のクエリに答え…

枝刈り探索が根本的に計算量改善することを示せることがある！！！ 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

なんとか解けてよかった 問題へのリンク 問題概要 × の二次元グリッド盤面が与えられる。 空いているマスを 2 つ選んで、その 2 つに駒を置く。ただしその 2 マス間のマンハッタン距離が 3 でなければならない という操作を繰り返し行う。こうして出来上がる…