久々にCodeforcesに参加。 しばらくレーティングが水平線でしたが、今回は良い感じの順位を取ることができました。 - A. Ring road 問題：n個のノードが有方向の枝でリング状につながっている。各ノードに方向を反転させるコストが定められてて、ノードを全…

なぜかRound3を通過してしまったので、ｶﾞｸﾌﾞﾙしながら参加してきました。 - 250. BankLottery 問題：n人がaccountBalance[i]ドルずつ銀行にお金を預けてて、週に一度、誰か1人を(預金額/全員の総預金額)の確率で選んでjackpotドル振り込む。自分が0番の人だ…

AOJで通ってしまったので、その記録を晒してみます。F. 古い記憶基本的な方針は以下の通りです。 ピースをつなぎ合わせて(深さ優先で)文字列を生成していく 改ざん文書に対し編集距離d以下のものが出来たら答えに追加 さすがにナイーブに書いたら遅すぎたの…

数時間後に演奏会を控えていますが、Round3に出ればTシャツをくれるというので参加してきました。 - 250. SieveOfEratosthenes 問題：エラトステネスのふるいで2からmaxNumまでの数を処理したときに、最後にふるわれる数は？ maxNumは4以上20億以下。素直に…

E. 最強の呪文下に書いた話で、 倍くらい調べればループを使って辞書順を小さくする文字列が見つかる ゴール以外で6*(ノード数)くらいでループなしより辞書順で小さくなったら"NO" とか言ってるので，倍くらい調べなくて良い事に気付きました。 "NO"になる判…

G. レーザー光の反射解法 レーザーが当たる鏡の順番を全列挙する 反射回数は高々5で，鏡の枚数も高々5なのでそんなに多くない 各反射順ごとに，レーザーの照射角度を求める 反射順に鏡を選び，照射地点の鏡像を取っていく 最終的に得られる照射地点の像の方…

id:kusano_progさんに先に書かれてしまいましたが…。E. 最強の呪文解法 [現在の呪文の長さ][現在地] を使った拡張ダイクストラ 文字列A, B, Cに対して、一般にmin(A+C, B+C) = min(A, B) + Cは成り立たない が，AとBの長さが同じなら成り立つので文字列長ご…

D. ぐらぐら解法 仕様どおりに実装するだけの簡単なお仕事 以下の実装では、再帰を使った深さ優先探索を行っている isStable:(_y, _x)の位置にあるピースが安定ならtrueを返す Mは関係するピースの座標値(+0.5)の合計 cntは関係するピースの個数 重心のx座標…

C. ポロック予想解法 動的計画法 Nを何個の正四面体数で表せるかは，1〜N-1の答えを使って求められる ansA[i]を「iを表すために必要な最小の正四面体数の数」とする 正四面体数1, 4, 10, 20, …に対し， ansA[N] = min(ansA[N-1], ans[N-4], ans[N-10], …) + …

B. 迷図と命ず解法 入口から幅優先探索 データが綺麗に成形してあるので、文字列のまま持っておくと楽 座標を2倍すると文字列上での現在地に対応する #include <iostream> #include <queue> using namespace std; char dx[] = {1, 0, -1, 0}; char dy[] = {0, 1, 0, -1}; int </queue></iostream>…

こっそり国内予選の問題を解いたので、記録でも書いてみます。 ちなみに、Fは自分の実力では謎。 あと、問題の概要は問題文が日本語なので省略します。A. 角角画伯，かく悩みき解法 問題文通りに各タイルの位置を計算する i番目のタイルの位置(x, y)を配列で…