競プロ

Codeforces Round #176 (Div.1) E. Ladies' Shop

問題文 http://codeforces.com/problemset/problem/286/E 解法 FFT. まず,答えの集合から生成できる任意の重さは,ある2個以下のカバンを使って(同じカバンを2つでもいい)作ることができる. なぜなら,もしある重さを p1 + p2 + p3 で生成したとする.…

AOJ 2703 Dice Stamp

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703 解法 明らかに全てのサイコロを使うのが最適. あとは,後ろから見るbitDPで解く. これは,最後に使うサイコロから決めていくと,その直前に使うサイコロによる得点が,今まで使った…

AOJ 2572 Venn Diagram

問題文 Venn Diagram | Aizu Online Judge 解法 頑張って実装するだけ. 円の半径は入力からすぐわかる. 2つの円の距離を二分探索で求めたら,でかい方を左下隅に配置. 小さいほうは [0, pi/2] でどの角度に置くとよいかを判定.計算したくないので二分探…

AOJ 1252 Confusing Login Names

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1252 解法 以下の4パターン全部試すだけ. swap しない(単に編集距離の問題) 1回swapしたあと編集距離 2回swap 消した後 swap 最悪 200(200-1)/2 * 16 * (16 * 16) なので,まあ適当にや…

Helvetic Coding Contest 2018 E2. Guard Duty (medium)

問題文 http://codeforces.com/contest/958/problem/E2 解説 わからなかったので上位陣のコードから解法を得た. とりあえずソートして隣接項の差を作ると,以下の問題になる.n - 1 要素からなる数列から,k 個えらんでその和を最小化せよ.ただし,隣接2要…

AOJ 1371 Infallibly Crack Perplexing Cryptarithm

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1371 解法 現れうる文字は高々8種類しかない. なので各文字に対して何を割り当てるか全探索して構文解析するだけ. ソースコード #include <bits/stdc++.h> using namespace std; using ret_type = doubl</bits/stdc++.h>…

AOJ 1351 Flipping Parentheses

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351 解法 StarrySkyTree + 二分探索で通した.( を +1, ) を -1 として累積和をStarrySkyTree上で管理する. 文字列が balanced であることと,累積和上の最小値が 0 以上であり,かつ末…

AOJ 1333 Beautiful Spacing

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 解法 二分探索+しゃくとり法. 二分探索は,普通に「スペースの隙間を X にして条件をクリアできるか」でやる.次にしゃくとり部分.二分探索の過程で与えられた,空けていい間隔を …

2014 Yandex.Algorithm Elimination Stage, Round 3 E - Tetrahedron

問題文 http://codeforces.com/gym/100459 解法 Standing -> 重心をおろした位置が底面の内部 Unstable -> 重心をおろした位置が底面の周上にある Falling -> 重心をおろした位置が底面の外部重心の座標は (a + b + c + d) / 4 なので,あとは底面の三角形と…

2014 Yandex.Algorithm Elimination Stage, Round 3 C - Intervals

問題文 http://codeforces.com/gym/100459 解法 しゃくとり法で解いた. 条件を満たさないようなペアの数を数えて,全体から引くことで求める. しゃくとりの過程で,今現在の区間が overlap しうるので,その分は足すことで重複して引かないようにしている…

2014 Yandex.Algorithm Elimination Stage, Round 3 B - Science

問題文 http://codeforces.com/gym/100459 解法1 行列累乗で解く. 左から順番に見ていった時,状態としては k + 3 種類ある. 最初の second type が来た状態,途中の first type (k個の状態がある),最後の second type が来た状態(受理状態),それ以…

2014 Yandex.Algorithm Elimination Stage, Round 2 F - Permutation Cube

問題文 http://codeforces.com/gym/100453 解法 X, Y, Z のそれぞれについて,巡回するいくつかのグループに分けることができる. 周期 a で巡回する列と,周期 b で巡回する列と,周期 c で巡回する列を考える.これらはそれぞれ X, Y, Z から持ってくると…

2014 Yandex.Algorithm Elimination Stage, Round 2 D - Inversions

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

2014 Yandex.Algorithm Elimination Stage, Round 2 B - Remainders

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

2014 Yandex.Algorithm Elimination Stage, Round 2 A - Cycles with Common Vertex

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

2014 Yandex.Algorithm Elimination Stage, Round1 F - Data Mining

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

2014 Yandex.Algorithm Elimination Stage, Round1 E - Burger Bar

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

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

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 できるプロセスを順に殺していくことです.…