はじめに 本記事は 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 いわゆるやるだけ問題ですが，頑張って通して満足するだけで終わると得られるものがなさそうな問題． こういうので実装方針を詰める練習をしなければいけないと思う（…

はじめに 2017年の振り返りをします．去年の振り返り記事は自分でも読みづらかったので，今年はできるだけ簡潔に書こうと思います． 基本的に競プロ関係に絞って書くことにします． 1月，2月，3月 記憶がない．多分競プロをほとんどやっていない時期． 2月頭…

目次 目次 はじめに プラクティス 本番 本番の問題概要 結果 旅程まとめ 7日（前々日） 8日（前日） 9日（Practice当日） 10日（コンテスト本番） 11日 12日 感想 はじめに kazuma, nakano, 僕の3人でチーム KazumaDragon としてミャンマーの Regional に参…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537 解説 言い換えると $1 \leq a_1 $a_1 + a_2 + \ldots + a_n = S$ をみたす $a_n$ の作り方を求める問題で，O(NMS) の解法はすぐわかると思いますが，実は O(NS) で解けます． 分割数…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1281 解法 この問題はやるだけなんですが，TLEとMLEをうまく回避するのが大切な問題です．定数倍遅くなりそうな部分はできるだけ排除していく必要があります． 基本BFSをやっていくだけな…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1238 解法 人をノードと見て，x y a を辺と考えると良い．ある人を仮に divine あるいは delivish と定めると，その人と関係のある人間の性質が一意に定まる． よって，関係のあるグループ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2731 解説 シフト操作 F について，F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば，あとはこれらを結合するだけです．操作 F, G に対し，これらをこの順に結合した操作 H は…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1361 解法 求めるものは unavoidable になる境界なので二分探索できそうです． ある時刻からデットロックを避ける最良の方法は，当然 terminate できるプロセスを順に殺していくことです．…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362 問題概要 文字列 S を部分列（部分文字列ではない）に持つような最小の長さの回文の集合の中で，辞書順 k 番目のものを求めよ． ・制約 1 1 解法 区間DPをやります．作れる文字列の数…

問題文 https://agc001.contest.atcoder.jp/tasks/agc001_c 解法 解説と（ちょっとだけ）違ったので一応書いておきます． まずBFSで全点対最短路を求めておいて，頂点 v から K より離れた頂点の数を sz[v] とします． あとは sz[v] の大きい方から貪欲に削…

問題文 http://codeforces.com/contest/789/problem/D 解法 まず，同じ辺を2回通るパスという時点でオイラーツアーが思い浮かびます． 自己辺を考えるのはめんどうなので，とりあえずない場合を考えると，条件を満たすパスがあるかどうかは，「一度のDFSによ…

問題文 http://codeforces.com/contest/785/problem/E 解法 平方分割 + 2次元BITで解いた．[0...m] x [0...n] で二次元．m は n / sqrt(n)． l[i] から r[i] の間に完全に含まれているブロックは BIT 上で計算し，端っこの部分は生で持っている配列を使って…

問題文 http://codeforces.com/contest/785/problem/D 解法 条件に合う部分列の，一番右端の "(" の位置を総当りして計算します． その位置から左に（その位置自体も含めて）"(" が $x$ 個あり，右に ")" が $y$ 個ある時，求める答えは $\displaystyle \sum…

問題文 http://codeforces.com/contest/884/problem/F 解法 最小費用流で解ける． まず，各アルファベットに対応する26個の頂点と，N / 2 個からなる文字列の前半（ないし後半）に対応する頂点をもつグラフをつくる． それぞれのアルファベットから，文字列…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294 解法 ゴールから見るDPでやります．dp[i][j][k] := 高さ (H から) i まで見た時に，位置 j にいて，それまでに猫が k 本引いているような確率とします． 高さ 1 から i までに，うさ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2556 解法 やり方は色々あると思うんですが，僕は桁DPっぽくやりました（正直実装方針かなりミスっていると思う．）まず，[0..N] までの答え f(N) を求めることができれば，f(B) - f(A - 1…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2614 解法 ローリングハッシュでやります．同じ長さの文字列 S, T に対して，「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます． も…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2605 解法 制約をよく読むと，（使えない辺を含める）与えられたグラフにおける各連結成分は，1つのパスまたは閉路になっていることがわかります． 各連結成分において計算して，最後にま…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449 解法 これは典型問題です． $i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは，$i$ 行目の $1$ から $j - 1$ 列目と，$i - 1$ 行目の $j$ から $C$ 列目だけです…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 解法 石取りゲームだからいい感じにわかるんでは？と思ったけどよくわかんなかったのでメモ化再帰で解きます．勝ちが決まるタイミングはは，連結成分の数が2であり，かつ自分の手番で…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 解法 ちゃんとフローがわかってるなら解ける問題． まず辺の追加クエリは簡単で，単純に辺を増やすだけ． 問題は辺の削除クエリです．与えられた辺を $\{a, b\}$ とします． 今流れて…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2344 解法 木DPで解きます． まず部分木に注目しましょう． 冷静に考えると，この部分木のすべての葉を回収するのには，以下の3通りだけしかありません．この部分木の根を $v$，左右の子を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2598 解法 移動に時間がかからないので，各強連結成分においては，好きな広告を（制限以内なら）好きな回数だけ見ることが出来ます．これは典型的な個数制限付きナップザック問題です．あ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1338 解法 まず，それぞれの針がなす角を求めましょう．短針が1周するのに$H$時間かかるとします． 今時刻が $h:m:s$ である時，針が上を向いている状態を 0 度とすると，長針，短針，秒針…