問題文 : Vasily the Bear and Beautiful Strings問題概要 :つぎの性質を満たす文字列$s$ の総数をmod $10^9+7$ で求めよ.・$0$ が$n$ 個, $1$ が$m $ 個から成る文字列である. ・$s$ にmodification を0 回以上行うことで最終的に文字列$s$ が文字$g$ にな…

AOJ 0198ものすごくめんどくさそうだと思っていたが実装に気をつければそうでもなかった. おなじ色の面をみつけて, まわりの4 面を回転させて一致するかを見ればOK. #include <cstdio> #include <string> using namespace std; int rot[6][4] = {{2, 4, 3, 1}, {2, 0, 3, 5},</string></cstdio>…

問題文 : 宇宙人のきまぐれメッセージ解法 : 6 つの接続可能性をすべてのマスについて試すO(6^(W*H)) 通りの探索と, それが終わったあとに接続関係が適切であるかをWF で確かめるO((W*H)^3)を掛け合わせてO(6^(W*H)*(W*H)^3) という絶望的な最悪計算量だが,…

Unusual Round と謳っていたので怖かったですが, 参加してみると楽しかったです.Result : oox.. 240th 1753 -> 1804C が解けそうでC から考えているとB の得点がモリモリ減ってしまったので, 今はまだ低い得点の問題から素早く解いたほうがよさそうです.

問題文 : 図画工作解法 :$dp[i][j][k]$ : $i$ で表される道具の集合をを$j$ 日目に$k$ 個まで道具をかって実現することができるか, として事前にDP を行う.それで, 袋から完成状態へDP の結果をコストとする辺を貼り, 流量を$N$ とした最小費用流を行う.

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

試験期間は5 月30 日から6 月14 日でした(つらい)

大分達成できていない気がしてきたので進捗確認です.○競技プログラミング/コンテスト [必ず達成したいこと] ・JOI本選で銀メダル以上の成績を残す. ← × ・JOI春合宿に参加し, 1桁順位を目指す. ← △(合宿には参加できたけど下から数えたほうが早い順位な気が…

問題文 : Blur解法 : 基本的に枝刈り探索である. ・矛盾する状態(そこにインクを落とすと明らかに歪なインクの塊が残ってしまう)になったら探索をやめる ・インクの数を確定することが出来たら無闇にインクを落とすのをやめる ・探索に失敗したインクの集合…

問題文 : Bitwise Kingdom解法 : $n$ bit 中$k$ bit が$1$ の市民の人数は$_{n}\text{C}_{k}$ 人である. よって, $_{n}\text{C}_{k} \geqq m$ となるまで$m$ を減らす. あとは, 先頭に$1$ を入れたときに自分より速い組み合わせが幾つあるかをたどりながら$0…

問題 : AOJ のALDS のDivide and Conquer の中から見れます.解法 : 問題文で示されているように再帰を行う. 正三角形の頂点の座標$(mx, my)$ は, その左隣の点を$m1 = (lx, ly)$, 右隣を$m2 = (rx, ry)$ とし, $m2 - m1$ ベクトルを90 度回転させたものを $\…

問題文 : Stoning Fortune解法 : 線分の交差判定・交点判定がきちんとできていれば, 面積を求めて条件に合わせて出力を行う問題. ライブラリを頼りました.

問題文 : 最後の扉解法 : つながる三角形を列挙したら, 強連結成分分解を行うだけ. JOI のAdvertisement という問題と全く一緒になります. 問題のつながる三角形の列挙ですが, 長方形と辺が重なる or 三角形の頂点が長方形にはいる or 長方形の頂点が三角形…

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

Skew Heap は, meld (2 つのpriority queue をmerge する操作) ができるheapです. meld ができると, push は, 新しい要素をヒープとして親とmeld, pop は 親の子をmeldで実装できてしまいます. 計算量はならしO(log N) で便利です. (くわしくはhos さんのブ…

KOJ に載せている, (去年のAdvent Calendar に掲載していた)Big Range Query の問題文および解説です.

問題文 : 回転解法 :リストを使う. 右と下にいけるリストがあれば, 90 * n (0 ≦ n ローカルでは最大ケースに2.6sec かかり, AtCoder でも10 点分しか点数が得れないので, O(QN^2) 書いたのと同じ扱いで涙しかない...

むずかしかったです(感想) まわりの出来を聞いた感じ, うまくいけば銅メダルくらいはとれているかも...? あまり高望みはしないことにします.それぞれの問題の概要とか.5/16 追記 : 銅メダルGot でした. わーい!

こんばんは! kagamiz です.今回はオンラインジャッジを実装する話を少しします. (このスライドの補足説明みたいなものです.)

ずっと書こうと思っていたのですが, 中途半端にしかスライドが出来ていなかったので, ブログに解説を載せます. たぶん今年も模擬予選します. 誰か一緒にwriter しましょう～.問題はコチラ からみれます.[1] 漫画 (Comics) 毎年の1 問目と同じ傾向です. 直前…

問題文 : 濁流きつねの曲大好きな身としては, 解かなければと思い意を決して取り組みました. concon 好きです.解法 : 算数, しよう.(提案) 明らかに(x, y) と(y, x) を押す順番は一緒なので, x > y なら折り返してしまいましょう. その後, マスの斜め上半分…

問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.点のソートをするときに, x 座標…

今日はDay 2 の問題. Constructions の実装方針が迷走しているので, 明日以降じっくり詰めていきたい. 考える実装は本当に苦手なので, おいおいDragon もキレイに書こうと決意.Mascots (問題文はコチラ)dp[i][j] : i * j の長方形を埋める順序 としてDP. 初…

今日はJOI 春合宿2013 Day1 の問題を復習. APIO がんばるゾ.Bus Tour (問題文は コチラ)[どのバスか][バスの位置]を持ってdijkstra. もう訪れた地点を訪れないように枝刈りする. 実装が少し大変. /* TASK : Bus Tour LANG : C++ NAME : kagamiz JPN12 */ #in…

鬱度高いの書きます. それぞれの問題について, 解けたか解けなかったのか書いても結局本番で出来なかったので書くつもりありません. (どの日の問題もおもしろかったです.)↓↓↓↓ 1 日目であまり思うような点数がとれず, 翌日からは頑張ろう, と最初は思ってい…

問題文 : Josephus Permutation解法 :アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの. ヨセフスの芋の軌跡をたどったものを出力する問題. 愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこ…

問題文 : 山の遊園地問題概要 (問題文読みづらいので) : 長さ N の数列が与えられる. 次のクエリに答えよ. 区間 [l, r] の値を v に更新する. [I l r v] [1, x] の値がはじめてv を越えるようなx を求める. [Q v] 解法 :遅延評価をするセグメント木を用いる.…

問題文 : 色紙解法 :各矩形のとりうる領域の最大値を計算し, その上にある別の色紙から自分に向かった辺をはったグラフを考える. このトポロジカル順序が答えとなる. 計算量は, 矩形の操作にO(NWH) 時間, トポロジカルソートにO(N) 時間で, 全体としてO(NWH)…

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

kyuri さんや tozan さんに便乗です.○…ジャッジで満点を確認した. △(点数)… ジャッジで(点数)点を確認した. ×…ジャッジで0 点だった. ー…未着手. 思考中. 2007 問題名 解いたか 記事 Score ○ Factorial △(80) Mall ○ Building ○ Fermat △(40) Salt ○ Anagram…