前書き なるべく愚直な操作でなんとかする解法です。（実質的には同じかもしれませんが、）mod での累積和を使っていません。 コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。 公式解説を読むほうが…

問題 atcoder.jp 思考過程 長ければ長いほど、とりあえず条件は満たせるので、どこまで「短くできるか」ということを考える。となると、おそらく各区間の端っこの部分で、ここでどうなるかを考える。 最初に、区間の「の最大値」と「の最小値」を考えてみる…

問題 atcoder.jp 思考過程 パッと見てどう構築するか思いつかず、色々と手で書いて考えてみる。 後ろに継ぎ足して生やしていこうとすると、場合の数を数えるのが色々とややこしくなりそう。 簡単に数えられるのは、ひたすら "7" を続ける場合で、k個続けるな…

問題 atcoder.jp 思考過程 コンテスト中にTLE解法を投げていた。 成約が小さいので全探索できそうな雰囲気を感じる。が、本当に全探索してしまうと、通り、なら 約 通りあるため、間に合わない。 そこで、スタートとゴール*1から半分ずつに分けて、真ん中ま…

問題 atcoder.jp 思考過程 最大ペアをどうにか構築できないかを考えてみようとする。 貪欲に多い部署からK人のペアを作るようにすると、最大ペアは作れなさそう（雑感）。他にうまく構築する方法が思いつかない。 なんとなくこういう、うまく組み合わせられ…

問題 atcoder.jp 思考過程 最初の方針（遅延セグ木解法） 対応するカッコがちゃんと閉じているか判定する問題。この手の問題ですぐに思いつくのは、"(" なら +1して ")" なら-1していく数列を作り、「範囲の両端で同じ値」かつ「間の数字が両端の数字を下回…

問題 atcoder.jp 思考過程 2人のスタートする位置と向きさえ決めれば、あとの動きは決まりそう。ただ、このままだと初期状態が 通りあるので、間に合わない。 図を書いてみると、交差点は2つになっていそうなので、この交差する場所をうまく選んであげれば行…