Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI

JOI Open Contest 2015 - Sterilizing Spray ふたたび

kagamiz.hatenablog.comこの問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

JOI 予選 2014-2015

JOI 予選2013 - 2014 参加記 - Lilliput Steps JOI 予選2013 - 2014 参加記 - Lilliput Steps懲りずに今年も 6 色に挑戦しました. 結論から言うと 1 / 6 です Ω\ζ°)チーン. 俺が J 言語だ!! 答えとひとことコメンツも書いておきます. kagamiz 解が一応書かれて…

JOI 模擬予選 2014-2015 解説++

JOI

こんばんは, kagamiz です. この記事は JOI 模擬予選 2014-2015 の 解説pdf の補足(というかひとことコメント)を目的として書かれた記事です.それぞれの問題の kagamiz 解 / yosupot 解を載せます.あと, なるべく早くに KOJ に今日の模擬予選の問題はアップ…

AOJ 0597 - Xiao Long Bao

問題文 : 小籠包

JOI 春合宿 2014 Day2 - Making Friends is Fun

問題文 : 友だちをつくろう

IJPC #1 A - Innocent Animals and Destruction of Forests

問題文 : むこのどうぶつたち と しんりんのはかい

JOI 本選 2013 - 2014 オンライン参加記

JOI

目標 : 後輩ズに勝つ /\_/\で参加する予定で, 2 まででいいだろ~と思っていたらハマって4 の考察までして, 試験前の貴重な4 時間を失いました(たのしかったです)

JOIss 2013 参加記

JOI

去年は旧ブログに書きましたが今年は新ブログに書かれることになりました.

AOJ 0586, 0587, 0588, 0589

JOI

JOI ボリュームの残っていた問題. せっかくなのでコンパイルせずに提出することにしたら悲惨なことになった.

JOI 春合宿 2012-day2 Rotate

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

JOI 予選模擬(2012-2013) 解説

JOI

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

JOI 春合宿 2013-day2 Construction

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

JOI 春合宿 2013 Day2 (mascots, spy)

JOI

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

JOI 春合宿 2013 Day1 (bustour, collecting, communication, joi_poster)

JOI

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

JOI 春合宿 2013 Day1 - Day4

JOI

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

JOI 春合宿 2008-day1 Sheet

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

JOI 春合宿 2008-day4 Ruins

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

合宿問題

JOI

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

JOI 本選 2013-5 Bubble Sort

問題文 : バブルソート解法 :与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする. すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.愚直に数え上げを行えばこれはO(N^2) 時間で最…

JOI春合宿 2009-day2 Contest

問題文 : コンテスト解法 : まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位…

JOI 春合宿 2012-day3 Sokoban

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…

IJPC # 3 C - Honest Fox and Dishonest Man

問題文 : しょうじききつね と うそつきにんげん解法 : はじめに"正直者の人数" をもととしたグループを作ると, それが正しい可能性のあるグループは高々O(√N) 個しかできない. 明らかに嘘を付いている人物がいれば, その人を使って正直者かどうかの判定を行…

JOI 春合宿 2012-day4 Chinese

問題文 : 中華料理解法 : 委員 a が 料理 b を食べるとき, 理事長の前にある料理はb - a となる. このような料理たちを通る最小手順を, すべてのありうる開始地点について考える問題である. これを考えるにあたって, 折り返しはたかだか1 回で良いことに注意…

JOI春合宿 2007-day2 SALT TREE XV

問題文 : SALT TREE XV解法 : (qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する. また, 辺の数が0 の状態への遷移は, 頂点が1 個の時…

JOI春合宿 2011-day2 shiritori

問題文 : しりとり解法 : 各辺を1 度だけ通るような探索をしてしまうと, 辺の数が多すぎるためうまく探索ができない. そこで, 00 ~ 99を頂点としたグラフを考え, その間に辺を貼ることを考える.このグラフがオイラーグラフであればしりとりをすることが可能…

JOI春合宿 2011-day4 apples

問題文 : リンゴの出荷解法 : 濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,・ある区間に値x を足す ・ある区間の和を求めることが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.た…

JOI春合宿 2012-day1 fish

問題文 : 魚解法 : 初めに, 尺取り法で, 起こりうる魚の組み合わせ(赤a 匹, 緑b 匹, 青c 匹 以下の組み合わせなら全て作成可能である) というものを列挙する. これをa * b * c の直方体として扱う. その後に, セグメント木で体積を, 以下の要領で求めていく.…

JOI春合宿 2007-day4 lines

問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…

AOJ 0519 - Worst Sportswriter

問題文 : 最悪の記者解法 : トポロジカルソートをすればよい. トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い. (隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が…

JOI春合宿 2011-day3 report

問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…

JOI 本選 2012 - 2013 参加記

2 / 9 (Sat.) から 2 / 10 (Sun.) にわたって開催されたJOI (日本情報オリンピック) の参加記を書きます. 2 / 8 (Fri.), Okinawa ・本選開催前日だというのに25 時まで起床する. ・8 時30 分からある生物の試験に恐れ慄きながら就寝する.・生物の試験で(たぶ…

APIO 2012-1 - Dispatching

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

JOI春合宿 2008-day3 Nightman

問題文 : 夜警解法 :登場する点のうち,・警備員のいる点 ・建物の点を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.これが出来れば, あとはダイクストラ法を各点に行うだけである.コード : #include <cstdio> #</cstdio>…

JOI春合宿 2011-day4 orienteering

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

JOI2007 本選

友達に勉強を教えながら, ゆったり2007を解いてみました. 4 -> 3 -> 2 -> 1 -> 5 の順で解きました. 4 が一番簡単なんだよなあ... 1時間半くらい余らせて終了.1. 碁石並べシミュレーションを行う. オセロっぽい操作を行う. #include <cstdio> #include <cstring> #include <algorithm> #i</algorithm></cstring></cstdio>…

JOI春合宿 2011-day1 joitter

問題文 : ジョイッター解法 : (1) 1の人がいる場合 (2) 1の人がいなくて, 2, 3の人がいる場合 (3) 3の人だけの場合で場合分けをする.(1) 1の人がいる時は, その人と他の人を全員友達にしてあげれば, 最小の辺数を達成できる.(2) N人の人がいれば, ある人と皆…

JOI春合宿 2009-day4 Chopsticks

問題文 : 塗り箸解法 : dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とするとdp[i][i] = 1, dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])となる. これは, 区間の幅を小さいものから計算すれば実現できる.コード : #…

JOI春合宿 2009-day3 Ski

問題文 : スキー解法 : 全体の平均速度について2 分探索を行う. ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる. 通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜け…

JOI春合宿 2009-day1 Stamps

JOI

問題文 : 判子解法 : まず, この作業でスタンプを作ることは, スタンプからIOIOI...OIの形を復元することを考える. このとき, 境界条件を考えないために, IO と OI を文字列に連結する. このとき, "OOO"や"III"の形で連結されている箇所があれば, 真ん中を変…

JOI春合宿 2011-day2 guess

問題文 : 数当て解法 : 最初に, 1の数をO(N)時間で当てる. あとは, 1の情報を元に二分探索を行う. Σ[i = 2, 99] ceil(log_{2}i) = 580 くらいなので, 最悪でも580 + 100 コード : #include <cstdio> #include <cstring> using namespace std; void print(int *p, int n) { fo</cstring></cstdio>…

JOI春合宿 2010-day2 aplusb

JOI

問題文 : 足し算解法 : vectorを使って実際に足し算を行う. 繰り上がり/桁数が変わる位置のみに微妙な変化があり, 間の数の計算は省くことができる.コード : #include <cstdio> #include <climits> #include <vector> #include <algorithm> using namespace std; typedef long long lint; typedef</algorithm></vector></climits></cstdio>…

JOI春合宿 2010-day1 sengoku

問題文 : 戦国時代解法 :見張り達の見張るエリアを, 左上と右上の線で分ける.まずは左上側の線の処理を以下のように行う.点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.右…

JOI春合宿 2010-day4 lake

問題文 : 湖解法 :まず,dp[l][r] = 区間[l, r]での運行数の最大値, とすると dp[l][r] = max(dp[l][r], dp[l][s[i] - 1] + dp[s[i] + 1][t[i] - 1] + dp[t[i] + 1][r]);となる. ただし, s[i], t[i]はそれぞれ船の来航する地点の座標で, s[i] これは, t[i]に…

JOI春合宿 2008-day1 committee

問題文 : 委員会(pdf注意, 1-2ページ目)解法 : 各頂点ごとに, やる気の最大値をメモする. 答えは, やる気の最大値が最も大きい頂点となる. ある頂点のやる気の最大値は, 自分自身のやる気+自分の子までのやる気の最大値のうち, 負で無いものの和, として求…

JOI春合宿 2009-day1 pyramid

問題文 : 貫きピラミッド解法 : 自分の地点での大きさを, 次のように, 2方向から伝搬しながら更新してやれば良い.どちらから先に行なっても良い. この更新が終われば, あとは各マスの和を取るだけである.O(WH)回の上書きで答えが求まるので, 計算量はO(WH)時…

JOI春合宿 2011-day4 IOI

問題文 : 国際情報オリンピック解法 :まず,"G を,N 問の合計点が G 点以上の選手の人数が全体の 1 / 12 以上となるような最大の値とする.このとき,金メダルが与えられる条件は,N 問の合計点が G 点以上であることである."ということを, 問題を解きやす…

JOI春合宿 2009-day4 Starry Sky

問題文 : 星空解法 : N個ある各星のLについて, そのLで囲める星の最大値を求める.ここで, 走査をする際に, x軸のみを走査し, y軸はセグメント木で, "ある点に於いて観測できる星の最大値"を管理すると, x軸の走査がO(N), その過程でのセグメント木の走査がO(…

JOI春合宿 2011-day3 deciphering

問題文 : 解読解法 : dp[i][j], i番目の文字まで, jで終わる暗号の総数, とするとdp[i][i番目の文字] = Σ[j = 'A'...'Z' + ' ', j + i番目の文字は禁止されていない] dp[i - 1][j]となります. 答えは Σ[i = 'A'...'Z'] dp[L][i] です. dp[0][' '] = 1として…

JOI春合宿 2010-day4 highway

問題文 : 高速道路解法 : 次のように, 2つの木を考える. 辺の更新のクエリが来た時は, euler-tourを行った時に、それぞれの辺が上りだったか、下りだったかを覚えておき処理する.頂点uからvへ行くクエリが来た際は, u->lca(u, v)に行くときは逆辺の木, lca(u…

JOI予選 2012-2013

JOI

順当にいけば104点だと思います. (2以外の)解答も載せるので良ければ参考にしてください. 一応ソースや解答, validationのために作ったプログラムは http://www1.axfc.net/uploader/so/2717504に置いています.1.解法 : 答えは L - max(国語を終わる日数, 算…