問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける． 左が欠けているやつを考えるときは末尾から比べたいので，各文字を反転した文字列集合も別に持っておく． 与えられた石版に ? がある場合は26文字全通り試す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽？ union find の各集合がどのクラブに属するかを別に vector で持っておく． a と b が同じ部活に所属している場合，マージするのだが違うクラブに属し…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2693 解法 いかにもな bitDP 感がある． しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える． うまくやれば状態に順列持てたりしないかな～と制約を読むと N -…

問題文 http://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか，という問題． まず，n * m （n, m はただの自然数）のような表現は完全に不利． 例えば 99 * 99 を考えてみるとわかりやすいが，そのまま出力したほうが短い…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390 解法 感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう． そして投げたら通った（終了）…だと困るので厳密じゃないけど一応それっぽいのだけ．木なので基地…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1342 解法 3次元幾何に見せかけた2次元幾何． 球の半径Rを決めた時，上から見て中心をどこにおけるかをイメージする． すると針と球の条件は，ある円があってその外側に中心を置く，という…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2558 解法 最小点被覆は多項式時間で解けない． この時点で，グラフにある良い性質を用いるか，頑張って枝刈りしかない． しかし与えられたグラフは単純グラフであるだけで他にいい感じの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2541 解法 特別な辺のコストを定めた時，それぞれの最短経路長がすぐに求まってくれないと困る． そこで特別な辺は100個しか無いことを利用し，とりあえず以下のダイクストラをやる．d[i][…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434 解法 他のそれぞれのアイドルの得点の期待値は，3種類の要素の得点の確率変数をX, Y, Z とすると E[X + Y + Z] だが，これは期待値の線形性から E[X] + E[Y] + E[Z] と等しい． した…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 解法 最短経路（それはそう）． 同じ高さの街が高々10しかないので，どの街に行ったか 2 ^ 10 で表現したい． どの街に行ったかを保存しつつ最短経路をやりたいね，となる． それには…

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

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

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

問題文 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) なので，まあ適当にや…

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

問題文 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>…

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

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

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

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

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

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

問題文 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| のコストがかかる．この操作は何回でも行える． こ…