ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder

AtCoder Beginner Contest 138 D - Ki

お題箱より。 D - Ki 様々な木の問題を解く上で基本となるような実装なので、実装も含めて解説します。 解法 1回の操作のイメージを図にすると以下のようになります。 実際には大量の操作があるので、これを1つ1つ処理していくことはできません。ではどうす…

AtCoder Beginner Contest 155 E - Payment

E - Payment 上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。 解法 上の桁から見ていって、その桁までで支払う&お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。 例えば 円だったとして、 の位の桁まで…

AtCoder Beginner Contest 155 D - Pairs

D - Pairs ※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。 解法 二分探索に落とし込む 与えられた数列などに対して大量の数を計算し、その 番目…

AtCoder Regular Contest 059 E - キャンディーとN人の子供

お題箱より。 E - Children and Candies 部分点解法から満点解法へのステップアップについて重点的に書きます。 解法 部分点解法 部分点解法は公式解説にもしっかり書かれているので軽く。各 について なので、ある1つの組 に対してだけ を求めてください、…

AtCoder Grand Contest 011 E - Increasing Numbers

E - Increasing Numbers 公式解説と少し違う方法で解いたので記録しておきます。 解法 十進法の桁を、一番下の桁を 桁目とするように表記します。 桁目は に対応する桁です。 「各桁から を引く回数」の条件への言い換え 非負整数が増加的であることは、「1…

キーエンス プログラミング コンテスト 2020 F - Monochromization

F - Monochromization 解説放送を観て解いたので、その方針をベースに書きます。 解法 まずは判定問題 まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。 ある最終状態の盤面から操作を逆回しして考えま…

第6回 ドワンゴからの挑戦状 予選 E - Span Covering

E - Span Covering 本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。 解法 包除原理の適用 土地を 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 について、 に含まれるマスだけに全てのシートを置く(…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution

C - Cookie Distribution 解法 式変形と言い換え 全てのクッキーの配り方の集合を 、答えを とします。答えは の期待値に全ての配り方の通り数を掛けたものなので、 を全ての配り方について合計したもの、つまり以下のように表現できます。 実際には各 は配…

第6回 ドワンゴからの挑戦状 予選 D - Arrangement

D - Arrangement 公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず… 解法 まずは貪欲に作ってみる 「カード の右隣のカードがカード であってはならない」という条件は、そんなに厳しい条件ではないように思います。なので…

第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

お題箱より。 F - Count Permutations Many Times 難しめの(とはいえ上級者には比較的知名度が高い)テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。 解法 …

CODE FESTIVAL 2016 Grand Final A - 1D Matching

お題箱より。 A - 1D Matching 解法 まずはケーブルの長さの合計が最小になる条件を考えましょう。 座標点を数直線上に並べて、小さい方(左)から見ていくことを考えましょう。このとき各点について「保留して、それより右側の座標点と繋ぐことにする」か「…

HACK TO THE FUTURE 2020 本戦 参加記録

オンサイト本戦に参加し、その1で8位、その2で10位のダブル入賞でした! ネタになるエピソードとか写真とかは特にないので、マジメにコンテストについて書こうと思います。 本戦1 A - 千の木 問題を理解し、正の得点を得る提出をするまで49分。ここまでのハ…

AtCoder Regular Contest 067 E - Grouping

お題箱より。 E - Grouping 解法 グループを作れる条件がなかなか扱いづらいことや制約の小ささからDPの線を考えます。 上手くDPを組むコツは「覚えておくべき情報を減らす」、逆に言うと「状態を忘れられるようにする」ことです。例えばこの問題において、…

AtCoder Beginner Contest 145 F - Laminate

お題箱より。 F - Laminate 解法 問題で最小化すべき値である「塗る操作の回数」を「コスト」と呼ぶことにします。また各 の値を「高さ」と呼ぶことにします。 説明をやりやすくするため、0列目に である列が存在すると考えます。 の値が確定した後、コスト…

DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 E - Majority of Balls

E - Majority of Balls 解法 キーとなるのは以下の2つの気付きです。 に対する質問の答えと に対する質問の答えは必ず異なる。片方が Red であればもう片方は Blue である。 もし「赤青が半々ずつ」ということが分かっている 個のボールの集合が得られたとす…

AtCoder Beginner Contest 146 F - Sugoroku

F - Sugoroku 解法 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。 ゴールするための最小ターン数はDP等で求めることができます(後で具体的に説明…

AtCoder Beginner Contest 141 F - Xor Sum 3

お題箱より。 F - Xor Sum 3 線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。 前段の考察 を表すビット桁を 桁目と表記することにします。一番下が0桁目です。 各ビット桁ごとに、 のうち 桁目が立っ…

HACK TO THE FUTURE 2020予選 参加記録

HACK TO THE FUTURE 2020予選 - AtCoder なんと全体10位で本戦に進むことができました! やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが… ビジュアライザのスクリーンショット等はexample_…

AtCoder Grand Contest 040 B - Two Contests

B - Two Contests 本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。 解法 公式解説にならい、それぞれのコンテストを「集合」、問題 を解ける人の範囲を「区間 」、コンテストの楽しさを「含まれる区間の共通部分の長さ…

CPSCO2019 Session1 F - Fruits in Season

お題箱より。 F - Fruits in Season 解法 最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。 判定問題として、ある に対して「果物の美味しさの最小値を 以上にできるか?」という問題を考えます。最小値の最大化問題に…

AtCoder Beginner Contest 144 E - Gluttony

E - Gluttony 解法 この問題はいくつか考察ステップが必要なので、順に見ていきましょう。 記法などについて 簡単のため、入力として与えられる値の集合 を単に 、 を単に と書くことにします。 また、最小化すべき値である「メンバーと食べ物の組み方を決め…

Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

お題箱より。 E - 根付き森二人用ゲーム 解法 それぞれの木を小規模なゲームとして解く スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手…

AtCoder Beginner Contest 143 F - Distinct Numbers

F - Distinct Numbers 解法 色々な解法があるみたいですが…この記事ではそれぞれの について独立に解きます。ある について解くときには、可能な操作回数には単調性があるので二分探索できます。 ある と操作回数 を固定したときに、操作を 回行えるかどうか…

AtCoder Regular Contest 077 E - guruguru

お題箱より。 E - guruguru 後半は公式解説と少し違う方法になっています。 解法 お気に入りで節約できる回数を定式化する ある1つの に対する から への移動を考えます。まず簡単のため、 と仮定しておきます。移動元と移動先をそれぞれ と書くことにします…

第一回日本最強プログラマー学生選手権決勝 C - Maximize Minimum

お題箱より。同じ問題に2件リクエストがありました。 C - Maximize Minimum 簡潔に飛ばし気味ではあるものの公式解説の説明が分かりやすいと思うので、流れは公式解説に沿いつつ図や行間を補って書いていきます。 解法 イチゴの最適な折り返し方 まずクエリ…

AtCoder Beginner Contest 054 D - Mixing Experiment

お題箱より。 D - Mixing Experiment 半分全列挙解法を…とのリクエストだったので、そちらを書きます。 解法 個の薬品をグループ0・グループ1に分け、それぞれについて薬品の選び方を決めたとします。これらを混ぜてちょうど混合比 になっているかどうかを判…

AtCoder Grand Contest 038 B - Sorting a Segment

B - Sorting a Segment 公式解説と少し違う方法で解いたので記録。 解法 ある長さ の区間を昇順に並び替えた時に、値が変更される最左のインデックスを 、最右のインデックスを とします。この時操作の結果は、閉区間 内の要素を昇順に並び替えたものとなり…

AtCoder Beginner Contest 141 E - Who Says a Pun?

E - Who Says a Pun? 解説で別解として紹介されている二分探索+ローリングハッシュで通したので書いておきます。 解法 条件を満たす長さで二分探索 「文字列 の連続部分文字列として位置が重ならずに2回以上出現する、長さ の文字列が存在する」ということ…

AtCoder Grand Contest 024 E - Sequence Growing Hard

E - Sequence Growing Hard 公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。 解法 要素を挿入して、辞書順でより大きくなる条件は 長さ の数列に1つ要素を挿入して、辞書順でより大きい長さ の数列を作る方法…

TTPC2019 オンライン参加記

てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。 はじまり アルメリアさんへTTPCチーム組みませんかてんぷら— てんぷら (@tempura_cpp) August 1, 2019 ご指名いただきました…