問題 解法 解答 問題 atcoder.jp 解法 dp(i) := マッチ棒を i 本ちょうど使って出来る最大の数 と DP を定義する．このとき，遷移時に A_i を全て試し，その中で最大の数を DP の答えにすればよい．答えとなる数は非常に大きくなるので，文字列として扱う．O…

問題 解法 解答 問題 atcoder.jp 解法 モンスター同士が攻撃しあう様子を見るとユークリッドの互除法の過程をしているだけなので，GCD(A_1, A_2, ..., A_N) を答えにすればよい．これは，ある２体のモンスターが攻撃しあって生き残ったほうの体力は２体のモ…

問題 解法 解答 問題 atcoder.jp 解法 K の i bit 目を K_i，K より小さい数 X の i bit 目を X_i とすると， K_40 = X_40 K_39 = X_39 ... K_i > X_i (0 <= i <= 40) となる．ここで，X_(i - 1), X_(i - 2), ... , X_0 は 0 でも 1 でもよい（K との大小に…

問題 解法 解答 問題 atcoder.jp 解法 まず，駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない．なので，駒を +1 の方向にだけ動かすことを考える．駒が通る距離を最小化したいので，駒が通らない距離を最大化すればよい．一番左・右の…

本選０日目 本選１日目 本選２日目 結果 2019/02/11 追伸 本選０日目 独房で朗読しようと思っていたライブラリ集をコンビニで印刷する． バチャコンを立てて直近の予選・本選の問題を解いておいた． 本選１日目 去年は朝学校に行くときに電車が人身事故で止…

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