人権なし

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

AtCoder Beginner Contest 118:D - Match Matching

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

AtCoder Beginner Contest 118:C - Monsters Battle Royale

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

AtCoder Beginner Contest 117:D - XXOR

問題 解法 解答 問題 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 Beginner Contest 117:C - Streamline

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

第18回日本情報オリンピック(JOI 2018/2019)本選

本選0日目 本選1日目 本選2日目 結果 2019/02/11 追伸 本選0日目 独房で朗読しようと思っていたライブラリ集をコンビニで印刷する. バチャコンを立てて直近の予選・本選の問題を解いておいた. 本選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 鎖の最大の…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:D - Restore the Tree

問題 解法 解答 問題 atcoder.jp 解法 問題文中に 書き足された各辺 u→vu→v は、ある頂点 uu からその子孫であるような頂点 vv に向かって伸びています とあるので答えは一意に定まる(これを見落としていて複数答えがあるのでないかとちょっと悩んでいた)…

全国統一プログラミング王決定戦予選 / NIKKEI Programming Contest 2019

結果 A - Subscribers B - Touitsu C - Different Strokes 結果 6問中3問正解(700 / 3200 点, 63:43),2443 位中 993位,パフォーマンス 1398,新レート 1629 (-23).最近にないレートの下げ幅を記録してしまった.A, B 問題を早く通せたのはよかったが…

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:C - Different Strokes

問題 解法 解答 問題 atcoder.jp 解法 自分と相手にとって幸福度の高いものを食べたいと考えると,(a_i + b_i) が大きいものから食べていけば最適だと気付く.言い方を変えると,最初に求める答えが -(b_1 + b_2 + ... + b_N) だった場合,ここに最大の (a_i…

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019:D - Nearest Card Game

問題 解法 解答 問題 atcoder.jp 解法 2人の操作後の各カードの所属は,N が偶数のとき「TATA...TAAA...ATT...T」のように高橋君と青木君が交互になっている区間(区間1)・青木君の区間(区間2)・高橋君の区間(区間3)となっている.また.区間2と区…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:A - レース (Race)

問題 解法 解答 問題 atcoder.jp 解法 雪マスは必ず2つ以上連続するので,1つの雪マスを氷マスに変化させても氷マスの連続する区間が1つの区間になることはない.また,氷マスの区間が最も長い区間の前後どちらかの雪マスを氷マスに変化させるのが最適で…

AtCoder Beginner Contest 116:D - Various Sushi

問題 解法 解答 問題 atcoder.jp 解法 まず,N 個の寿司を「おいしさ」が大きい順にソートし,大きいものから K 個選び答えの候補にする.このとき選んだ寿司のネタの種類数が k だとしたとき,1 ~ (k - 1) 種類のネタだけで K 個選ぶことは不可能 or 最適で…

AtCoder Beginner Contest 116:C - Grand Garden

問題 解法 解答 問題 atcoder.jp 解法 「水やり」の回数を最小化したいので,1回の「水やり」で出来るだけ多くの花の高さを伸ばしたい.なので,あと 1 以上伸ばさなければいけない花の連続する区間は1回の「水やり」で 1 ずつ伸ばす.h_i に達した花がそ…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

結果 A - Beginning B - KEYENCE String C - Exam and Wizard D - Double Landscape 結果 6問中4問正解(1200 / 2700 点, 115:24),1986 位中 405位,パフォーマンス 1750,新レート 1652 (+11, Highest).目標であった4問正解を達成できたのでよかった…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題 解法 解答 問題 atcoder.jp 解法 各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする.また,数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし,数字 i を書く時点で書くことが出来るマスの総数を avail_i …

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:C - Exam and Wizard

問題 解法 解答 問題 atcoder.jp 解法 まず,A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる. 上げる必要がある準備度の総和を sum とし,準備度が十分であるものの余剰分(B_i - A_i)を降順ソートした…

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

結果 A - Bulletin Board B - Contests C - Alternating Path 結果 5問中3問正解(600 / 1700 点, 39:10),1970 位中 420 位,パフォーマンス 1696,新レート 1641 (+6, Highest).何とかレート Highest 更新出来たが,D 問題を WA が多発し,通せなかっ…

CODE THANKS FESTIVAL 2018:F - Coins on the tree

問題 解法 解答 問題 atcoder.jp 解法 問題文の条件より,i 枚目のコインをある頂点 v に置くと決めた場合,(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる.よって,1 枚目のコインから順に置く場所を決めていく. (i - 1) 枚…

Educational DP Contest / DP まとめコンテスト

結果 A - Frog 1 B - Frog 2 C - Vacation D - Knapsack 1 E - Knapsack 2 G - Longest Path H - Grid 1 I - Coins K - Stones L - Deque M - Candies P - Independent Set 結果 26 問中 12 問正解(1200 / 2600 点, 216:15),1124 位中 252 位.AC した問…

Educational DP Contest:P - Independent Set

問題 解法 解答 問題 atcoder.jp 解法 dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき,頂点 i から到達できる頂点を塗り分ける通り数 と定義する.このとき, dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき) dp(i, f) = dp(v_1…

Educational DP Contest:M - Candies

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 人目までで j 個分けるときの通り数 と定義する.このとき, dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) + ... + dp(i - 1, j - a_(i - 1)) dp(i, j) = 1 (j == 0 のとき) dp(i, j) = 0 (j < 0, i == 0…

Educational DP Contest:L - Deque

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := 数列 a_i ~ a_j の中で k が操作するときの (X, Y) の値 と定義する.このとき, dp(i, j, k) = ( dp(i + 1, j, (k + 1) % 2).X + a_i, dp(i + 1, j, (k + 1) % 2).Y ) か ( dp(i, j - 1, (k + 1) % 2).…

Educational DP Contest:K - Stones

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 石が i 個あり操作するのが j のとき,j が勝てるかどうか と定義する.このとき,残りの石の状態のうちどれかが相手を負けにすることが出来るならば,自分を勝ちにできることを踏まえると, dp(i, j) = !d…

Educational DP Contest:I - Coins

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 枚目まで操作し j 枚表のときの,表が裏より多くなる確率 と定義する.このとき, dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1)) と漸化式が立つ.状態数 O(N^2),遷移 O(1…