2018-11-01から1ヶ月間の記事一覧
問題 解法 解答 問題 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 解法 学生を頂点，プレゼントをあげる関係を有向辺で表すと，ループ状の頂点の集合とループにつながる一本道の構造が１つか複数できることが分かる．ループ上では，自分のプレゼントと…
結果 A - Thumbnail B - Sum AND Subarrays 結果 ２完（600 点，63:26），1391 位中 435 位，パフォーマンス 1587，レート 1547（+5, Highest）．目標であった２完を達成出来たのでよかった．C 問題や D 問題の部分点を考えたが，歯が立たなかった．また，思…
問題 解法 解答 問題 beta.atcoder.jp 解法 2^31 の位から 2^0 の位の順に答えを決定していくことを考える．なぜならば，2^k の位が 1 にすることが可能であるならば，2^k の位をパスしより小さい位で 1 としたとしても答えを 2^k の位を 1 としたときよりも…
問題 解法 解答 問題 beta.atcoder.jp 解法 「全てのプラン ii に対して、通話時間が AiAi 分の場合には他のどのプランよりも通話料金が 11 円以上安くなることが保証され」ているので，A が T を超えるプランと超えないプランの２つについて料金を計算し，m…
結果 A - チップ・ストーリー ～無色編～ B - チップ・ストーリー ～漆黒編～ C - チップ・ストーリー ～白銀編～ 結果 ３ 完（700 点，58:53），1010 位中 396 位．目標であった３～４完を達成することが出来て一安心したが，各問題で実装でミスをしたり，…
問題 解法 解答 問題 beta.atcoder.jp 解法 P_i の最大値を maxP，Q_i の最大値を maxQ とおく．この時，maxP を 1 ~ N で動かすとき，maxQ は [ N / maxP ] になる．P の通り数は maxP^10 - (maxP - 1)^10 になる（なぜならば，最終的な通り数を求める段階…
問題 解法 解答 問題 https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf 解法 K <= 200 という制約から考えると「全ての操作後の文字列の 1 ~ K 文字目は元の文字列の何文字目か？」という問題を解けばいい．これは，操作を逆から見ていくこと…
問題 解法 解答 問題 beta.atcoder.jp 解法 頂点ごとに各長さの辺が何本生えているかを数えておき，２つの辺の中間の頂点を全通り試し，それぞれ何通りのペアができるかを計算し，足していく．O(NlogN)． 解答 beta.atcoder.jp 実装ミスで 8 WA した．
問題 解法 解答 問題 Aizu Online Judge 解法 循環小数を分数に変換する計算を実装するのみ．O(|str|)． 解答 Aizu Online Judge 実装ミスにより 2 WA してしまった．
問題 解法 解答 問題 Aizu Online Judge 解法 あるマスから飛ぶ先のマスに辺を張り，各マスから同じマスを２度まで通る DFS をする．一回一回の DFS ごとに，１回しか通らなかったマスを答えから除外していく．これを全てのマスについて計算すればよい．O(N)…
問題 解法 解答 問題 Aizu Online Judge 解法 割られる数を出来るだけ大きく，割る数を出来るだけ小さくすることを考えればよい．割る数 C - D の C, D を全通り試し，余ったもののうち大きいもの２つを A, B に充てればよい．O(N^2)． 解答 Aizu Online Jud…
問題 解法 解答 問題 Aizu Online Judge 解法 朝・昼・晩の時間の決め方は，単純に考えると (24*60)^3 通り．これを全て計算していては間に合わない．時間の決め方は N 人の３つの時間の区間の始点と終点の数だけに抑えることが出来るので N^3 通りになる．…
問題 解法 解答 問題 Aizu Online Judge 解法 t_i それぞれを t_i の最大値（M とおく）の約数にすることを考える．M の約数は O(MlogM) で列挙出来るので，各 t_i について t_i 以上で最も小さい約数にすることを考えればよい．O(MlogM)． 解答 Aizu Online…
結果 A - ばらばらロボット 結果 82829 点，440:23，519 位中 272 位．終わりの一時間だけの参加になった． A - ばらばらロボット 何も考えずに外周を R で囲っただけ． https://beta.atcoder.jp/contests/future-contest-2019-qual/submissions/3579513
問題 解法 解答 問題 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…
結果 A - Discount Fare B - Palace C - ID D - Number of Amidakuji 結果 ３完（600 点，15:45），2359 位中 328 位．B 問題で痛恨の実装ミスをしてしまい 1 WA を出してしまったのが順位に響いてしまった．また，D 問題を解くことが出来なかったのがつらか…
問題 解法 解答 問題 beta.atcoder.jp 解法 ぱっと見 DP をしたい気持ちになるので，以下のように DP を定義する： dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計 後は，DP の遷移を考える．この時，今いる行の次（すなわち h + …
問題 解法 解答 問題 beta.atcoder.jp 解法 (誕生した年，所属する県の番号，入力時の index) で二重 std::pair を作り，素直にソートし，県ごとに誕生した市ごとに番号を割り振っていけばよい．O(MlogM)． 解答 beta.atcoder.jp C 問題にしては良心的な問題…
問題 解法 解答 問題 beta.atcoder.jp 解法 以下のように X を配置するのがよい． 背景黒文字白の X 以外の X の配置場所には規則性があるので簡単における．背景黒文字白の X は規則性に基づいておいたけれども食べられるマスに配置する．O(N^2)． 解答 bet…
問題 解法 解答 問題 beta.atcoder.jp 解法 ダイクストラ法を使う．この中で，あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので，時刻 0 ~ K - 1 のそれぞれの時，次に上下左右に動ける時刻を O(1) …
問題 解法 解答 問題 beta.atcoder.jp 解法 図を書いてみると，1 ~ N の数字を三角形状に並べられるものがよいと気づくので，N が三角数であれば Yes，そうでなければ No となる． どのように部分列を構成するかというと， N = 15 の場合では，三角形の三辺…
問題 解法 解答 問題 beta.atcoder.jp 解法 lcm(7, m) のマスは 0 のマスと塗られているかどうかは同じになるので，lcm(7, m) - 1 のマスまでマス目を塗るシミュレーションをすれば十分．縦 lcm(7, m) / 7 マス，横 7 マスの表を S と置く．S の下に新しく S…
問題 解法 解答 問題 beta.atcoder.jp 解法 A, B の "(" , ")" の数がそれぞれ |S| / 4 になっていればよい．S を先頭から見ていくとき，S を真ん中で半分にして考える． 前半分のとき， S_i == "(" で A の "(" が不足しているとき：A += "(" S_i == "(" で…
問題 解法 解答 問題 beta.atcoder.jp 解法 ある要素を inf にした場合，答えは２つに分けられた数列のそれぞれの中で完結する要素の総和が０である部分列の数の和になる．そこで，２つに分ける箇所を全探索し，それぞれについて前後の数列に当てはまる部分…
問題 解法 解答 問題 beta.atcoder.jp 解法 王都から各都市に行ったならばすぐに王都に戻るのが最適であるので，M 個の依頼からすぐにまた王都に戻ってくる時刻を１つに定められる．なので，２種類の依頼を１つにまとめてしまうことで，最大スケジューリング…
