問題文 http://joisc2015.contest.atcoder.jp/tasks/joisc2015_a 問題概要 文字列 S が与えられる． S に対して，クエリが N 個投げられる． 各クエリは A, B, C を持ち，これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する． 最…

問題文 https://csacademy.com/contest/archive/task/xor-closure/ 問題概要 N 項からなる数列 {a_n} が与えられる．この数列にいくつか数を追加して，以下の性質を満たすようにする． 相異なる任意の i, j に対して，a_i XOR a_j もまた数列 {a_n} に含まれ…

問題文 http://arc025.contest.atcoder.jp/tasks/arc025_3 解法 制約をみて，なんとなく全頂点を始点としてダイクストラできるなーと検討はつく． とりあえず，目的地を決め打ちしてしまって，目的地を始点にダイクストラする． その後，得られた距離 d[i] …

問題文 http://arc035.contest.atcoder.jp/tasks/arc035_c 解法 頂点数が小さいので，ワーシャルフロイドでよい． ただし，建設するたびにワーシャルフロイドすると間に合わない．よく考えると，x-y 間に橋を作ったときに最短経路が変わるのは，x-yを経由す…

問題文 http://arc023.contest.atcoder.jp/tasks/arc023_3 解法 典型 of 典型みたいな問題．L -1 -1 ... -1 R みたいな区間に分けて考えて，R - L を -1 にうまく分配するという問題になる． これはいわゆる重複組合せというやつ．高校数学でも頻出． という…