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

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

問題文 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をやります．作れる文字列の数…

問題文 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 度とすると，長針，短針，秒針…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2436 解法 カードの数字同士を足すわけではなくそのまま並べるので，桁に注目したいなーという気持ちになります． しかも $a[i]$ は高々4桁なので嬉しいです．こういう問題は，すべての数…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725 問題概要 催し物を時間 $T$ だけ開催することになった． そこで歌う歌の候補が $N$ 個あり，それぞれの歌はパラメーター $t[i], p[i], f[i]$ を持つ．$t[i]$ は歌の長さ，$p[i]$ は歌…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2606 解法 まず，制約を読むと，ある項についてたかだか40回の遷移で元に戻ることがわかるので，愚直にこれを求めます． このとき，それぞれの項が c[i] 回 で元に戻るとします． すると，…