問題文 : Network Reliability | Aizu Online Judge 概要 無向グラフと整数 が与えられる．の各枝が独立にパーセントの確率で消失するとき，グラフが連結である確率を求めよ． 制約

問題文 : Let's Play Osu!概要$n$ 個のマスがある. マス $i$ は確率 $p_i$ で "○" になり, 確率 $1 - p_i$ で"×"になる. $n$ 個のマスのうち, "○"で繋がったそれぞれの連結成分の大きさを$S_i$ とすると, スコア $\displaystyle\sum_{i = 1}^{連結成分数}S_i…

問題文 : 小籠包

問題文 : 猫

問題文 : 表現の自由

問題文 : 双子の読書感想文

問題文 : Twenty Questions概要 :長さ$m $ のビット列が$n$ 個ある. これらを一意に識別するために必要なビット数はいくらか？ ただし, あるビットの情報を得た後に次の戦略を考えても良い.$1 \leqq m \leqq 11,\ 1 \leqq n \leqq 128$

問題文 : 鉄道路線

問題文 : Sereja and Subsequences概要 :数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.$n \leqq 10^5$

問題 : Ben Toh

問題 : -平-均-ものすごくJOI 本選に出そうな問題だった.部分点1 が$n \leqq 20$ 部分点2 が$n \leqq 50,\ a_i \leqq 100,\ T \leqq 100$ 満点が問題文の通り, みたいな感じ.

問題文 : 奇襲部隊

問題文 : ボール

問題文 : イウィ

問題文 : ナップザック

問題文 : 辞書順

問題文 : 準急

問題文 : 数

問題文 : サイコロ

問題文 : トーナメント

問題文 : ゲーム

問題文 : コンテスト

問題文 : 直線状の庭園 (pdf 注意)

問題文 : 輪番停電計画解法 :$dp[sy][sx][gy][gx] := sy \leqq y \leqq gy,\ sx \leqq x \leqq gx$ を満たす区間でのグループの数の最大値と, 供給力の最大値として, メモ化再帰を行うと楽. 列 or 行を降りていき, 分割が不可能な域に達したらimpossible を…

問題文 : Adhoc Translation解法 : これがA 問題ってやべえなあ... 辞書に登録されている単語とネットで見た単語の間に, それぞれ編集距離をコストとした辺を張る. ネットで見た単語の数 ≦ 辞書に登録されている単語の数で, かならずネットで見た単語の数の…

問題文 : ウォッチング解法 (ただし人と違う解き方をしているらしい) : 50 点分の解法は, dp[i][j][k] : 位置i までを小カメラj 個, 大カメラk 個で覆うときの距離の最小値, として, O(N^4) で計算できる. (二分探索とは概念)これを高速化するために, dp[i][…

問題文 : 最古の遺跡2解法 :dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺…

問題文 : Little Elephants and Broken Sorting解法 :dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,この配列の初期値はA[i] > A[j] なら 1, A[i] k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換され…

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

問題文 : Stack Maze解法 :dp[y1][x1][y2][x2] : 区間D : x ∈ [x1, x2], y ∈ [y1, y2] で宝石を置ける個数の最大値とすると, マス(y1, x1) から(y2, x2)に到達可能であれば, D' : x ∈ (x1, x2], y ∈ [y1, y2] などの, Dより小さい区間の最大値からこの値を計…