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

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

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

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

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

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

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

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

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

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

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

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

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

問題 解法 解答 問題 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 + …

問題 解法 解答 問題 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 内では「ど…

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

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

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

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

問題 解法 解答 問題 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…