人権なし

競プロで解いた問題や開発の進捗などの記録です

JOI 難易度8問題

JOI '08 春合宿1:3- Flu インフルエンザ

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 解法 k 日目までに感染の広がる様子をシミュレーションする.流行している都市から感染が拡大する範囲が d <= 25 と狭いので,現在流行している都市それぞれを…

JOI '09 予選:5- シャッフル

問題 解法 解答 問題 www.ioi-jp.org 解法 カードの枚数に対してシャッフルの回数がとても少ないので,ほとんどバラバラにならない.なので,連続する数字が書かれるカードを1つの区間としてもっておき,その区間をシャッフルによって切ったり,並び替えた…

JOI '09 本選:3- あみだくじ

問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 ある横の辺を消すということは,その辺を通る2つのパスの中のその辺の高さ以降のパスが逆になることを意味する.ゆえに,任意の横の辺を消したとき,ある2つ…

JOI '09 本選:4- 散歩

問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 1 ~ (N - 1) 回目にたどり着いた場所を知る必要はない.また,詳しいルートを1回ずつ区別して計算する必要はない.なぜならば,N 回目のルートやたどり着く場…

JOI '09 本選:5- 認証レベル

問題 解法 解答 問題 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf 解法 各事務所についてどれぐらいの数の部屋をどれぐらいの認証レベルで入ることが出来るのかが知りたい.ここで,各事務所のマス上で BFS をする.具体的には,(今…

JOI '09 春合宿1:1- Sequence 数列

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf 解法 数列 A を書き出して実験してみると,1 ~ (m * 2^m) 項目の偶奇が周期的に繰り返していることが分かる.1つの周期の中にいくつ奇数の項があるかを数え,(…

JOI '09 春合宿1:3- Pyramid 貫きピラミッド

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf 解法 ピラミッドの頂点を通るような斜め状の (2 * h_i - 1) マスにピラミッドの各段の数を書き込む.このとき,マスに既に数が書かれている場合は,max を取る…

JOI '09 春合宿2:2- Advertisement 宣伝

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day2_21.pdf 解法 人を頂点として (a, b) に辺を張る.このとき,グラフ全体には木があったり,閉路があったり,閉路といくつかの辺・頂点が合体したものがあったりする.こ…

JOI '09 春合宿4:1- Distribution 冊子の配布

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day4_23.pdf 解法 根から頂点 i までのやる気度の合計を costSum_i とする.min(n, m) 回ある頂点を選び,その頂点の costSum を足したものが答えとなる. ここで,頂点 k …

JOI '10 予選:6- 方向音痴のトナカイ

問題 解法 解答 問題 www.ioi-jp.org 解法 プレゼントを配っていく動作を逆にして考える(すなわち,各家からプレゼントを回収する感じ).すると,次に行く家はプレゼントを回収していない家を通過することは出来ないので各方向一か所に定まる.なので,探…

JOI '10 春合宿1:2- 戦国時代 (Sengoku)

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf 解法 各見張りの監視する範囲はその見張りの位置を中心とする × の形になる.ここで,領地を 45 度回転させてひし形にして考えると,各見張りの監視する範囲は x, …

JOI '10 春合宿2:1- 足し算 (a+b problem)

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf 解法 小さい位から順に考えていく.桁を1つ1つ見ていては TLE になってしまうので,1つ目か2つ目の整数の桁の数が変わる桁の位置で区切って考える.1つの区間…

JOI '10 春合宿2:2 - DNA の合成 (DNA synthesizer)

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf 解法 dp(i) := S の i 文字目までを構成するのに素 DNA 鎖が最小で何本必要か と DP を定義する.このとき,S の i 文字目から文字列が一致する素 DNA 鎖の最大の…

JOI '11 春合宿3:1 - 解読

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day3.pdf 解法 「dp(i) := i 文字目から L 文字目までで考えられる原文の数の総和」と DP を立てる.このとき,S[i] と同じ文字が出てくる位置を p とすると, dp(i) = dp(i + …

JOI '12 春合宿1:3 - 日本情報オリンピック旗

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day1.pdf 解法 旗は再帰的に決まっていくので, dp(x1, y1, x2, y2) := マス (x1, y1), (x2, y2) の正方形を旗にするときの最小コスト と DP の漸化式を立てる.DP 内では「ど…

JOI '13 春合宿2:2 - マスコットの片付け

問題 解法 解答 問題 http://imoz.jp/data/joi/2013-sp-d2-mascots.pdf 解法 まず,長方形になる回数を最大化する方法を考えると,最初に与えられた状態をまず出来るだけ小さい長方形にし,4辺それぞれを拡大していくのが最適になる. 最初に与えられた状態…

JOI '13 春合宿4:2 - プレゼント

問題 解法 解答 問題 http://imoz.jp/data/joi/2013-sp-d4-presents.pdf 解法 学生を頂点,プレゼントをあげる関係を有向辺で表すと,ループ状の頂点の集合とループにつながる一本道の構造が1つか複数できることが分かる.ループ上では,自分のプレゼントと…

JOI '15 春合宿1日目:1 - コピー&ペースト2

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf 解法 K <= 200 という制約から考えると「全ての操作後の文字列の 1 ~ K 文字目は元の文字列の何文字目か?」という問題を解けばいい.これは,操作を逆から見ていくこと…

JOI '15 春合宿 4:1 - 遺産相続

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d4.pdf 解法 K 人それぞれに Union Find 木を構成し,辺のコストが高い順に辺を見ていく.辺ごとにどの人に辺を割り振るかを考える.この時,ある人を境に辺を含めることが可能…

JOI '15 春合宿 2:1 - ビルの飾りつけ 3

問題 解法 解答 問題 https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d2.pdf 解法 元の数列である A を構成する条件は, 1 <= A_i <= max(A_0, A_1, A_2, ... , A_(i - 1) ) + 1 であるので,B_i も同様に 1 <= B_i <= max(B_0, B_1, B_2, ... , B…