問題文 http://codeforces.com/gym/100453 解法 長さを最小化するので，N * (N - 1) / 2 >= K && (N - 1) * (N - 2) / 2 あとは，上から順に，その位置の値を変えなければならないところまで順番に 1 から埋めていく． その場所まで来たら，変えないと行けな…

問題文 http://codeforces.com/gym/100453 解法 ある数 a_i からスタートした時に，それ以上の値で余りをとっても変化はない． したがって，数列をまずソートし，最初にする数字を何にするか全部試すのが良さそうである． これは dp で計算できて， dp[i] :=…

問題文 http://codeforces.com/gym/100453 問題概要 n 個の鎖が与えられ，それぞれのサイズは c_i である． 鎖とは，連結グラフであり，かつ両端点以外の頂点の次数が2であるものである． これらの鎖を，鎖とは別に用意した1つの頂点 X に，その両端をつなげ…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の要素からなる数列 a が与えられる．あなたは以下の操作を k 回行える． ある要素の値を隣接する（どちらかの1方の）要素に加える． k 回の操作の後の，数列に含まれる値の最小値を最大化せよ． また…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の要素からなる数列 a が1つ与えられる． 以下を満たす集合 X のうち，最小の |X| をもとめよ． X = {b_1, ..., b_k} とすると，任意の a の要素は，Xの要素のうちからいくつか選んで足し合わせて作る…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の数列が与えられる． 各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる． 最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなる…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする． もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする． こうしてできる四角形のうち，凹四角形で…

問題文 http://codeforces.com/gym/100448 問題概要 n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える． こ…

はじめに 本記事は C++11で始めるマルチスレッドプログラミングその1 ～std::thread事始め～ - すいバカ日誌 の続きとなる記事です（何年越しだよ）． 今回は std:;mutex による基本的な排他制御について書きます． 本記事を書いた時点では C++17 がもう策定…

問題文 http://codeforces.com/problemset/problem/883/I 解法 求めたい値は二分探索で求めましょう． あとはある x にたいして題意を満たす分割が可能か調べます． 写真の値はソートしておくと，題意の分割は連続部分列の分割になります． その上で，以下の…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0597 解法 汁が飛び散る範囲が小さいので，それを利用します． ある連続する8個の区間を考えると，そのなかで各小籠包がどの順で食べられるかさえわかれば，答えを求めることができます． …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0624 解法 bitDP で解きます． あるマスにいるとき，それまでに買った屋台の情報を持つのですが，右か下にしかいけないことから，保存すべき場所が少なくなります． 具体的には，右，下，…

タイトルのまんま． 純粋関数型データ構造っぽさを意識して書いてみました． use std::rc::Rc; enum SkewHeap<T: Ord + Clone> { Empty, Node(T, Rc<SkewHeap<T>>, Rc<SkewHeap<T>>) } impl<T: Ord + Clone> Clone for SkewHeap<T> { fn clone(&self) -> SkewHeap<T> { match *self { SkewHeap::Empty => SkewHeap::Empty, S</t></t></t:></skewheap<t></skewheap<t></t:>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1386 解法 一方はいもす法やるだけなのはすぐわかると思います． もう一方が問題ですが，これも累積和で簡単に求まります． じつは，乗客 i のデータの区間 [a[i], b[i]] に対して，端点以…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1133&lang=jp 方針1 いわゆるやるだけ問題ですが，頑張って通して満足するだけで終わると得られるものがなさそうな問題． こういうので実装方針を詰める練習をしなければいけないと思う（…