水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

JOI '18 予選:5 - 森林伐採

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, d) := マス (i, j) まで d 個のマス(マス (0, 0) と (H, W) を含む)を経由して行くときのコスト」と DP を立てる.マス (i, j) へはマス (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j) から行くこ…

JOI '18 予選:4 - 水ようかん

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j) := 左端から i 個までを切った後のピースの長さが j 以上になるようにうまく切った時の答え」で DP を立てる.DP の漸化式は, dp(i, j) = min( max( dp(k, j), (区間 (k + 1) ~ i の長さ) - j ) ) と…

Typical DP Contest:D - サイコロ

問題 解法 解答 問題 beta.atcoder.jp 解法 まず,D を素因数分解し,2, 3, 5 以外の素因数があった場合は,答えは 0 と決まる. そうでないとき,「dp(i, tw, th, fi) := i 回サイコロを振り,素因数 2 が tw 回,素因数 3 が th 回,素因数 5 が fi 回出た…

Typical DP Contest:C - トーナメント

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j) := 人 i が j 回戦目で勝つ確率」と DP を立てる.人 i と j 回戦目で当たる可能性がある人を人 l, l + 1, l + 2, ... , r とし,人 a が人 b に勝つ確率を p_(a, b) とすると, dp(i, j) = dp(i, j - …

Typical DP Contest:B - ゲーム

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, f) := 左の山から i 個,右の山から j 個取られていて今のターンが f の時のすぬけ君の取るものの価値の合計の最大値」と DP を立てる.DP 内で f に応じて処理を変える.具体的には,f がすぬけ君の場…

Typical DP Contest:A - コンテスト

問題 解法 解答 問題 beta.atcoder.jp 解法 N <= 100 なので,(i - 1) 番目までの要素でできた点数それぞれに対して i 番目の要素を足し合わせたものを新しく答えに追加すればよい.重複が生じるものがあるので,set を使って処理する.O(N^2 * logN). 解答…

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つか複数できることが分かる.ループ上では,自分のプレゼントと…

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

結果 A - Thumbnail B - Sum AND Subarrays 結果 2完(600 点,63:26),1391 位中 435 位,パフォーマンス 1587,レート 1547(+5, Highest).目標であった2完を達成出来たのでよかった.C 問題や D 問題の部分点を考えたが,歯が立たなかった.また,思…

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選:B - Sum AND Subarrays

問題 解法 解答 問題 beta.atcoder.jp 解法 2^31 の位から 2^0 の位の順に答えを決定していくことを考える.なぜならば,2^k の位が 1 にすることが可能であるならば,2^k の位をパスしより小さい位で 1 としたとしても答えを 2^k の位を 1 としたときよりも…

CODE FESTIVAL 2018 Final (Parallel):C - Telephone Charge

問題 解法 解答 問題 beta.atcoder.jp 解法 「全てのプラン ii に対して、通話時間が AiAi 分の場合には他のどのプランよりも通話料金が 11 円以上安くなることが保証され」ているので,A が T を超えるプランと超えないプランの2つについて料金を計算し,m…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選

結果 A - チップ・ストーリー ~無色編~ B - チップ・ストーリー ~漆黒編~ C - チップ・ストーリー ~白銀編~ 結果 3 完(700 点,58:53),1010 位中 396 位.目標であった3~4完を達成することが出来て一安心したが,各問題で実装でミスをしたり,…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選:C - チップ・ストーリー ~白銀編~

問題 解法 解答 問題 beta.atcoder.jp 解法 P_i の最大値を maxP,Q_i の最大値を maxQ とおく.この時,maxP を 1 ~ N で動かすとき,maxQ は [ N / maxP ] になる.P の通り数は maxP^10 - (maxP - 1)^10 になる(なぜならば,最終的な通り数を求める段階…

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

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

CODE FESTIVAL 2018 Final (Parallel):A - 2540

問題 解法 解答 問題 beta.atcoder.jp 解法 頂点ごとに各長さの辺が何本生えているかを数えておき,2つの辺の中間の頂点を全通り試し,それぞれ何通りのペアができるかを計算し,足していく.O(NlogN). 解答 beta.atcoder.jp 実装ミスで 8 WA した.

PCK 2016 本選:6 - 実数既約分数化

問題 解法 解答 問題 Aizu Online Judge 解法 循環小数を分数に変換する計算を実装するのみ.O(|str|). 解答 Aizu Online Judge 実装ミスにより 2 WA してしまった.

PCK 2016 本選:5 - 環状すごろく

問題 解法 解答 問題 Aizu Online Judge 解法 あるマスから飛ぶ先のマスに辺を張り,各マスから同じマスを2度まで通る DFS をする.一回一回の DFS ごとに,1回しか通らなかったマスを答えから除外していく.これを全てのマスについて計算すればよい.O(N)…

PCK 2016 本選:3 - 有理式最大化

問題 解法 解答 問題 Aizu Online Judge 解法 割られる数を出来るだけ大きく,割る数を出来るだけ小さくすることを考えればよい.割る数 C - D の C, D を全通り試し,余ったもののうち大きいもの2つを A, B に充てればよい.O(N^2). 解答 Aizu Online Jud…

PCK 2017 本選:5 - 朝昼晩ごはん

問題 解法 解答 問題 Aizu Online Judge 解法 朝・昼・晩の時間の決め方は,単純に考えると (24*60)^3 通り.これを全て計算していては間に合わない.時間の決め方は N 人の3つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる.…

PCK 2017 本選:4 - 電子メトロノーム

問題 解法 解答 問題 Aizu Online Judge 解法 t_i それぞれを t_i の最大値(M とおく)の約数にすることを考える.M の約数は O(MlogM) で列挙出来るので,各 t_i について t_i 以上で最も小さい約数にすることを考えればよい.O(MlogM). 解答 Aizu Online…

HACK TO THE FUTURE 2019 予選

結果 A - ばらばらロボット 結果 82829 点,440:23,519 位中 272 位.終わりの一時間だけの参加になった. A - ばらばらロボット 何も考えずに外周を R で囲っただけ. https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3579513

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…

AtCoder Beginner Contest 113

結果 A - Discount Fare B - Palace C - ID D - Number of Amidakuji 結果 3完(600 点,15:45),2359 位中 328 位.B 問題で痛恨の実装ミスをしてしまい 1 WA を出してしまったのが順位に響いてしまった.また,D 問題を解くことが出来なかったのがつらか…

AtCoder Beginner Contest 113:D - Number of Amidakuji

問題 解法 解答 問題 beta.atcoder.jp 解法 ぱっと見 DP をしたい気持ちになるので,以下のように DP を定義する: dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計 後は,DP の遷移を考える.この時,今いる行の次(すなわち h + …

AtCoder Beginner Contest 113:C - ID

問題 解法 解答 問題 beta.atcoder.jp 解法 (誕生した年,所属する県の番号,入力時の index) で二重 std::pair を作り,素直にソートし,県ごとに誕生した市ごとに番号を割り振っていけばよい.O(MlogM). 解答 beta.atcoder.jp C 問題にしては良心的な問題…

CODE FESTIVAL 2018 qual B:C - Special Cake for CODE FESTIVAL

問題 解法 解答 問題 beta.atcoder.jp 解法 以下のように X を配置するのがよい. 背景黒文字白の X 以外の X の配置場所には規則性があるので簡単における.背景黒文字白の X は規則性に基づいておいたけれども食べられるマスに配置する.O(N^2). 解答 bet…

Mujin Programming Challenge 2018:E - 迷路

問題 解法 解答 問題 beta.atcoder.jp 解法 ダイクストラ法を使う.この中で,あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので,時刻 0 ~ K - 1 のそれぞれの時,次に上下左右に動ける時刻を O(1) …