競プロ

2014 Yandex.Algorithm Elimination Stage, Round1 D - Splitting Money

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

2014 Yandex.Algorithm Elimination Stage, Round1 C - Non-Convex Quadrilaterals

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

2014 Yandex.Algorithm Elimination Stage, Round1 B - Adjusting Ducks

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

Codeforces I. Photo Processing (2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest)

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

AOJ 0597 Xiao Long Bao

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

AOJ 0624 Food stalls

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

AOJ 1386 Starting a Scenic Railroad Service

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

AOJ1133 Water Tank

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

The 2017 ACM-ICPC Asia Yangon Regional Programming Contest 参加記

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

AOJ 0537 Bingo

問題文 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) で解けます. 分割数…

AOJ 1281 The Morning after Halloween

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

AOJ 1238 True Liars

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

AOJ 2731 Shifting a Matrix

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

AOJ 1361 Deadlock Detection

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

AOJ 1362 Do Geese See God?

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

AGC001 C - Shorten Diameter

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

Codeforces Round #407 (Div. 2) D. Weird journey

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

Codeforces Round #404 (Div.2) E. Anton and Permutation

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

Codeforces Round #404 (Div.2) D. Anton and School - 2

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

Codeforces ECR #31 F. Anti-Palindromize

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

AOJ 2294 Entangled with Lottery

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

AOJ 2556 Integer in Integer

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

AOJ 2614 Almost Same Substring

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

AOJ 2605 Social Monsters

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

AOJ 2449 Connect

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

AOJ 2376 Disconnected Game

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

AOJ 2313 Box Witch

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

AOJ 2344 Multi Ending Story

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

AOJ 2598 Website Tour

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

AOJ 1338 Clock Hands

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