問題 Rabbit Party | Aizu Online Judgen 匹のウサギがパーティーをする。各ウサギには友達度が定義されている(これが正の値を取るのは高々 m 個)。 ウサギ i がパーティーに参加した際の満足度は, パーティーに参加したウサギのうち, 友達度が最も低いもの…

問題 Road Construction | Aizu Online Judge連結な無向グラフが与えられる。各辺には長さとコストが定義されている。このグラフを次の条件を満たすように変更したい。 各点 v の 0 からの距離(距離は辺の長さで定義される)が元のグラフと変わらない。 任意…

問題 Never Wait for Weights | Aizu Online JudgeN 個の頂点があり, 各頂点には W[i] という特徴量がある。次の二つのクエリが与えられるので適切に処理せよ。 W[b] - W[a] = w という情報が与えられる。 a, b を与えるので, 今までの情報で W[b]-W[a] が求…

問題 Traveling by Stagecoach | Aizu Online Judge 解法 bitDP 的なダイクストラやるだけ。 const int MAXN = 8; const int MAXP = 1000; const int MAXM = 33; const double INF = 1e18; int T[MAXN]; int dist[MAXM][MAXM]; double dp[MAXM][1<<MAXN]; int main() { int n, m, p, a, b; while (cin >> n >> m ></maxn];>…

個人的にはいろんな知識満載で良問だと思ったので記事書いておきます。まず, プログラムは「次に呼び出すべき命令は何か」というのを覚えておくプログラムカウンタというのがあります。これは %eip というのが管理しているらしいので, 方針としては なんとか…

問題 Dashboard - Round 2 2016 - Google Code JamN 人の人がいる。それぞれの人は, YES という確率が P[i] で, NO という確率が 1-P[i] である。N 人の中から K 人の人を選んで YES という人と NO という人の確率が K/2 人ずつになる確率を最大化したい(K …

問題 Dashboard - Round 2 2016 - Google Code Jamじゃんけんトーナメントをする。各参加者はあまり戦略的でないので, 常に同じ手を出す(例えばグーしか出さない人とかがいる)。なので, もし同じ手を出す人同士が対戦すると, トーナメントが永遠に終わらなく…

問題 abc038.contest.atcoder.jp 解法 これ想定解かな…セグメント木を適当に使ったら解けました。まず (h, w) のペアの順番にソートします。基本的にはこれで dp[i] = (i までの箱を使って最高いくつの入れ子を作れるか) というのを求めていきます。これで (…

今回の ABC は久しぶりにちょっと難しかったです。 問題 abc038.contest.atcoder.jp 解法 [l, r) の区間が単調増加の場合, その間にある条件を満たすペアの数は (r-l)*(r-l+1)/2 で求められます。各単調増加列ごとにこれを求めれば答えが得られます。 int ma…

問題 TopCoder Statistics - Problem Statement 解法 素直に実装するだけです。あんまりおもしろくない… const int SIZE = 1000; bool done[SIZE][SIZE]; class RotatingBot { public: int minArea(vector <int> moves) { int n = moves.size(); if (n == 1) retu</int>…

問題 Save your cats | Aizu Online JudgeN 頂点, M 辺の平面グラフが与えられる。平面グラフの面の数が 1 になるように辺を破壊したい。これを達成する最小コストを求めよ。 解法 下のスライドの前半を読めばすべてを察することができます。 平面グラフと交…

はぁ… 問題 TopCoder Statistics - Problem StatementA, B, C が与えられる。1 解法 三角形の辺の組としてあり得ないものを数え, それを A*B*C から引く, というように考えます。あり得ない辺の組としては, a が最大のもの(a >= b+c を満たす) b が最大のも…

問題 codeforces.comA さんと B さんが N 次の多項式の係数を埋めるゲームをする(係数は実数ならなんでも良い)。A さんの目的はこの多項式が x-k で割り切れるようにすることで, B さんはそれを阻止することが目的である。B さんが先行ですでにいくつかの係…

Div2 だけど久しぶりにこどふぉやった気がする・・・ 問題 codeforces.com迷路が与えられる。迷路はセルが H*W 個あるような形をしており, 各セルにはいくつかの方向にドアがついている(上, 右, 下, 左 からいくつか)。 あるセルからは, 隣接するセルに移動…

問題 TopCoder Statistics - Problem Statement魔法使いとあなたがゲームで勝負をする。ゲームでは, 二次元座標上にいくつかの帽子を置き, そのいくつかの帽子の中にはコインを隠しておく。 あなたは, numGuess 回だけ, 好きな帽子の中身を見ることができる…

picoctf で相変わらず遊んでいます。今回のテーマは「ググれカス」です。 picoCTF Substitution この問題, 「英語の歌詞なんて知らんわ～」で無視しようと思ったんですが, 暗号解析サービスみたいのがあるらしく, それにかけるとあっという間に解くことがで…

問題 TopCoder Statistics - Problem Statement円錐のセットを 2 つ用意する。2 つのセット Top, Bottom は次のように使う。 Top の円錐を Bottom の円錐の上にかぶせるように乗せる。 ここで, Top の円錐の半径は Bottom の円錐の半径より小さくなければな…

最近のんびり過ごしています。 問題 CatChecker | Aizu Online Judge 解法 区間 dp をします。dp[l][r] = (区間 [l, r) が猫の鳴き声文字列になっているか？)というのを判定します。これは, s[l] = 'm', s[r-1] = 'w' s[m] = 'e' の時, dp[l+1][m-1], dp[m+1…

問題 tdpc.contest.atcoder.jp 解法 sugim さんの解法を参考にしました。O(NCW) から計算量を落とせなくてずっと悩んでたんですが多分 O(NCW)…？(間違ってたらすみません)ちなみに僕が考えていた解法より 2 倍くらい定数倍早くて実装も楽でした。各色ごとに …

問題 tdpc.contest.atcoder.jp 解法 mat[i][j] = (同じ部屋に訪れることなく部屋 i から部屋 j に行く方法) とします。これが求まったとすると, dp[h][i] = (h 階において 部屋 i にいる場合の数) というのは, dp[h+1][i] = dp[h][k] * mat[k][i] となります…

ほとんどの人にとって知識ゲー or ググりゲーだったんですが, 日本語でしかググらなかったのはミスでした。 問題 arc054.contest.atcoder.jp 解法 結論から言いますと, 行列 S の行列式の偶奇を見れば終わりです。理由を考えていきます。この問題では要する…

問題 arc054.contest.atcoder.jp 解法 凸関数 + 凸関数 という形になっているので, 全体としても凸関数です。ということで三分探索をしましょう。 int main() { double P; cin >> P; double l = 0, r = 1e18; auto f = [&](double x) { return x+P/pow(2, x/…

問題 tdpc.contest.atcoder.jp 解法 dp[i][j] = (猫 i までの幸福度の最大値。ただし, 猫 i は 猫 j, j+1, ..., i の猫と距離 1 以内の場所にいる) という dp を考えます。すると, dp の遷移はdp[i+1][j] = max(0 sum の部分については事前に累積和を計算し…

問題 Immortal Jewels | Aizu Online Judge 解法 ある最適な直線があったとします。この直線を少し動かしても結果は変わりません。結果が変わる直線の動かし方は, その直線が ある円の内部を貫くか, ある円の中心からの距離が Ri + Mi となるときです。なの…

ksnctf で解いたのはさっきの記事で終わりで, 次からは picoCTF です。10 問くらい解いたんですが, 全部書くのは面倒なので書きたい奴だけ書きます。 picoCTF Internet Inspection 要素の検証をして script の部分を開きます。そうすると, ready ってところ…

唐突に ksnctf というので遊んでいたところ, picoCTF のほうが初心者向けでオススメと言われたので, そっちもやってみました。今までに解いたのをバーッと書いていきます。 ksnctf.sweetduet.info picoctf.com ksnctf Easy Cipher ksnctf.sweetduet.infoまず…

問題 tdpc.contest.atcoder.jp 解法 円の右端が小さい順に円を並べます。円iがほかの円jを内包している条件は, (円iの左端の座標) であるので, 上記のような並べ方をすると, すでに 右側の条件は満たしていることになります。なので, あと考えるべきなのは …

問題 tdpc.contest.atcoder.jp 解法 dp[state] = (state で表されるものはすでに倒されている場合の, あと必要な投球数) とします。ある state においては, どこか 1 つの座標に向かってボールを投げ続けるのが最適です(外れたからやっぱこっち, とかやるよ…

オーダー落とせずに死んでました。 問題 TopCoder Statistics - Problem Statement1 ～ X の目が書いてあり, 面が N 個あるさいころを二つ用意する。この二つのさいころの目はすべてバラバラである(よって 2*N このさいころを使って簡単なゲームをする。さい…

問題 TopCoder Statistics - Problem Statementn 本の木が与えられ, それぞれは高さ h[i] である。レベル X の魔法を使うと, それぞれの木の高さを, [max(1, h[i]-X), h[i]+X] の範囲に変化させることが出来る(ただし高さは整数にしなければならない)。この…