JOI
kagamiz.hatenablog.comこの問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。
JOI 予選2013 - 2014 参加記 - Lilliput Steps JOI 予選2013 - 2014 参加記 - Lilliput Steps懲りずに今年も 6 色に挑戦しました. 結論から言うと 1 / 6 です Ω＼ζ°)ﾁｰﾝ. 俺が J 言語だ!! 答えとひとことコメンツも書いておきます. kagamiz 解が一応書かれて…
こんばんは, kagamiz です. この記事は JOI 模擬予選 2014-2015 の 解説pdf の補足(というかひとことコメント)を目的として書かれた記事です.それぞれの問題の kagamiz 解 / yosupot 解を載せます.あと, なるべく早くに KOJ に今日の模擬予選の問題はアップ…
問題文 : 小籠包
問題文 : 友だちをつくろう
問題文 : むこのどうぶつたち と しんりんのはかい
目標 : 後輩ズに勝つ /\_/\で参加する予定で, 2 まででいいだろ～と思っていたらハマって4 の考察までして, 試験前の貴重な4 時間を失いました(たのしかったです)
去年は旧ブログに書きましたが今年は新ブログに書かれることになりました.
JOI ボリュームの残っていた問題. せっかくなのでコンパイルせずに提出することにしたら悲惨なことになった.
問題文 : 回転解法 :リストを使う. 右と下にいけるリストがあれば, 90 * n (0 ≦ n ローカルでは最大ケースに2.6sec かかり, AtCoder でも10 点分しか点数が得れないので, O(QN^2) 書いたのと同じ扱いで涙しかない...
ずっと書こうと思っていたのですが, 中途半端にしかスライドが出来ていなかったので, ブログに解説を載せます. たぶん今年も模擬予選します. 誰か一緒にwriter しましょう～.問題はコチラ からみれます.[1] 漫画 (Comics) 毎年の1 問目と同じ傾向です. 直前…
問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(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 日目であまり思うような点数がとれず, 翌日からは頑張ろう, と最初は思ってい…
問題文 : 色紙解法 :各矩形のとりうる領域の最大値を計算し, その上にある別の色紙から自分に向かった辺をはったグラフを考える. このトポロジカル順序が答えとなる. 計算量は, 矩形の操作に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…
問題文 : バブルソート解法 :与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする. すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.愚直に数え上げを行えばこれはO(N^2) 時間で最…
問題文 : コンテスト解法 : まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位…
問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…
問題文 : しょうじききつね と うそつきにんげん解法 : はじめに"正直者の人数" をもととしたグループを作ると, それが正しい可能性のあるグループは高々O(√N) 個しかできない. 明らかに嘘を付いている人物がいれば, その人を使って正直者かどうかの判定を行…
問題文 : 中華料理解法 : 委員 a が 料理 b を食べるとき, 理事長の前にある料理はb - a となる. このような料理たちを通る最小手順を, すべてのありうる開始地点について考える問題である. これを考えるにあたって, 折り返しはたかだか1 回で良いことに注意…
問題文 : SALT TREE XV解法 : (qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する. また, 辺の数が0 の状態への遷移は, 頂点が1 個の時…
問題文 : しりとり解法 : 各辺を1 度だけ通るような探索をしてしまうと, 辺の数が多すぎるためうまく探索ができない. そこで, 00 ~ 99を頂点としたグラフを考え, その間に辺を貼ることを考える.このグラフがオイラーグラフであればしりとりをすることが可能…
問題文 : リンゴの出荷解法 : 濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,・ある区間に値x を足す ・ある区間の和を求めることが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.た…
問題文 : 魚解法 : 初めに, 尺取り法で, 起こりうる魚の組み合わせ(赤a 匹, 緑b 匹, 青c 匹 以下の組み合わせなら全て作成可能である) というものを列挙する. これをa * b * c の直方体として扱う. その後に, セグメント木で体積を, 以下の要領で求めていく.…
問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…
問題文 : 最悪の記者解法 : トポロジカルソートをすればよい. トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い. (隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が…
問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…
