【問題】 arc058.contest.atcoder.jp【考察】 典型数え上げ問題の変形タイプ。この問題では少し特殊な制約がついていて、二項係数ライブラリで一発 AC というわけにはいきません。まず数え上げ問題の常套手段として、いくつかの排反な事象への場合分けをしま…

【問題】 arc024.contest.atcoder.jp【考察】 そこまで難しくないんですが、結構一般的な知見を得た問題。 以下簡単のため、互いに共通部分をもっていてもアナグラムダジャレになれる、と考えます。まず、2 つの部分文字列がアナグラムの関係にあるとき、そ…

【問題】 arc014.contest.atcoder.jp【考察】 N がそれなりに小さいのですが、ギリギリ半分全列挙はできないくらいの大きさ (そもそも効率的にマージする方法もなさそうですが)。そこで O(N^4) くらいの DP かなと思ってあれこれ考えてみるものの、箱に入っ…

【問題】 arc038.contest.atcoder.jp【考察】 Grundy 数を使いそうなのはすぐに分かるのですが、普通に山ごとに Grundy 数を設定しようとすると、ある山の遷移が他の山に影響を与える設定のせいでうまくいきません。そこで視点を変えて、茶碗に入っている豆…

【問題】 arc037.contest.atcoder.jp 【方針】 K 番目に小さい値を求める問題 (CodeForces 191E) を最近やっていて、それと同じく二分探索でやるのかなと最初に思う。ちょっと考えたら、ある値 S より小さいようなマス目の値は std::set で簡単に求まりそう…