ARMERIA

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

競技プログラミング

解説記事リクエストの募集をはじめました

アルメリアです。いつも記事を読んでいただきありがとうございます。 このたび、競プロ解説記事のリクエスト募集を始めます。過去の問題の記事も少しずつ増やしていきたいのと、せっかく書くなら困っている人の助けになれればいいかなと思ったので。 受付に…

AtCoder Beginner Contest 126 F - XOR Matching

F - XOR Matching 解法 結論を書いてしまうと、以下のような数列がもし作れれば答えになります。 アイデアとしては、まず を挟んで 以外の数字を鏡写しに並べます。こうすることで 以外のどの数字を選んでも、2つの位置の間(両端を含む)にあるものは「 1個…

Codeforces Round #561 D. Cute Sequences

Problem - D - Codeforces 問題概要 以下の問題を 個解け。 正整数 が与えられる。以下の条件を満たす整数列 を1つ構成するか、そのような数列が存在しないことを判定せよ。 初項が で末項が である。 項数を として、全ての について とすると が成立する。…

Educational Codeforces Round 65 E. Range Deleting

Problem - E - Codeforces 問題概要 長さ の数列 と整数 が与えられ、 である。 以下の条件を満たす整数の組 の個数を求めよ。 である。 数列 から を満たす要素をすべて取り除くと、残った数列は広義単調増加になる。(空数列でも可) 制約 解説 削除する値…

Codeforces Round #560 F2. Microtransactions (hard version)

Problem - F2 - Codeforces 問題概要 ※microtransactionは、オンラインゲームなどでのアイテム課金を指す言葉だそうです。文中では「アイテム」と訳します。 イヴァンはゲームのアイテムを買おうとしている。アイテムは 種類あり、種類 のアイテムは 個必要…

AGC033 B - LRUD Game

B - LRUD Game 解法 まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが 盤外に落ちる条件が「縦座標が の範囲から外れること」または「横座標が の範囲から外れること」であること 縦座標と横座標が互いに影響し合わない…

diverta 2019 Programming Contest D - DivRem Number

D - DivRem Number 解法 この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。 具体的に数式で表すと、 を で割った余りを とすると が成立…

「答えを決め打つ」タイプの二分探索を使いこなそう

ゴールデンウィークの有志コンテストなどで多く出題され、話題になったので記事を書こうと思います。 対象レートはだいたい緑~水色(最後のほうは青くらいまで)です。実際のAtCoderの問題を使って説明していくので、ネタバレになる点はご了承ください。 「…

AtCoder橙になりました

5月4日のAGCで、ついに橙になることができました!!! 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書き…

いろはちゃんコンテスト Day1 L - をあ ぷろぶれむ

L - をあ ぷろぶれむ 解法 初手は二分探索 この問題のように、 与えられた数列などから、列挙しきれない個数の要素(入力 個に対して 個など)を計算する。それらをソートしたときの 番目の値を求めよ。 という形式の問題では、二分探索が有効なことが多いで…

Codeforces Round #554 F. Neko Rules the Catniverse

Problem - F1 - Codeforces Problem - F2 - Codeforces 問題概要 整数 が与えられる。以下の条件を満たす要素数 の数列 は何通りあるか、 で求めよ。 は相異なる 制約 F1とF2で の範囲が異なる。 F1: F2: 解法 何となく数列の頭から順に決めていくDPを考えた…

Tenka1 Programmer Contest 2019 F - Banned X

F - Banned X 気合いで数える問題。ARC-FやAGC-Dあたりの数え上げをやりまくったおかげで解けたかな…と思います。 解法 まず、全要素の合計が 未満かどうかで場合分けをします。 合計が 未満である場合 要素の合計が 未満である場合はどのように数を並べても…

Tenka1 Programmer Contest 2019 D - Three Colors

D - Three Colors 解法 三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。 逆に三角形が成立しない…

yukicoder No.819 Enjapma game

No.819 Enjapma game - yukicoder writerさんの解法が天才なので、地道に実験して解いた私の解法もまとめてみたいと思います。 解法 「その盤面状態で自分のターンが回ってきた時に勝つ/負ける」という状態をそれぞれ勝ち状態/負け状態と呼ぶことにします。 …

CSA FII Code Final Round Online Mirror F - Flawed Olympiad

https://csacademy.com/contest/fii-code-2019-final-round-online-mirror/task/flawed-olympiad/statement/ 問題概要 要素数 の非負整数列 と非負整数 が与えられる。数列 の要素間に | (ビットOR)または & (ビットAND)を入れて出来る式であって、計算…

Codeforces Round #551 E. Serval and Snake

Problem - E - Codeforces これ結構好き。 問題概要 インタラクティブ問題である。 のグリッドがあり、グリッド内に蛇がいる。蛇の両端は異なるマスにあり、胴体は隣り合うマスを渡って両端を繋ぐパスとして表現される。 以下のクエリを2019回投げることが出…

AGC022 D - Shopping

D - Shopping この記事を書いている時点で、AGC-Dの中で配点が最も高い問題。私自身AGC-Dを全問通しましたが、ダントツで一番難しい問題だと感じました。解説ACをするのにも非常に苦労しました… この回は解説放送のアーカイブがなくて、解説記事も全然書かれ…

エクサウィザーズ 2019 E - Black or White

E - Black or White 解法 答えを定式化する 番目のチョコレートを食べ終わった直後に、 黒が残っている確率: 黒白どちらも残っている確率: とします。このとき黒だけが残っている確率は です。 番目に食べるチョコレートが黒であるパターンは、 番目のチョ…

エクサウィザーズ 2019 D - Modulo Operations

D - Modulo Operations 解法 単調減少列を考える まず気付くべき点は、「ある値 で余りを取ったあと、それより大きい値 で余りを取っても値は変化しない」ということです。 で余りを取った時点で黒板に書かれた値 は 以下になっていて、その より大きい値で…

ABC122 D - We Like AGC

D - We Like AGC 解法 問題文の条件を満たすためには、具体的にどのような部分文字列が含まれていてはダメでしょうか。NGパターンを列挙してみましょう。 3文字のNGパターン もちろん AGC はNGです。また、隣り合う2文字を入れ替えて AGC となる GAC と ACG …

yukicoder No.803 Very Limited Xor Subset

No.803 Very Limited Xor Subset - yukicoder 解法 AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番は…

AGC031 C - Differ by 1 Bit

C - Differ by 1 Bit 解法 コンテスト本番で私が考察・実装した方針を書いていきます。公式解説とは実装の方針が異なっていて、公式解説のほうが恐らく楽な実装だとは思いますが、ACを得るまでの1つの過程として参考になればと思います。 YES/NO判定 まずは…

AGC031 B - Reversi

B - Reversi 解法 まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側…

早稲田大学プログラミングコンテスト2019 I - Ramen

I - Ramen 解説を見て通したけど、実装にけっこう手こずったので記録。 解法 距離の2乗をコストに持つDP、といえばCHTです(?)。CHT(Convex-Hull Trick)が使えるように、価格 の計算式を と変形します。 が についての一次式群から最小値を求める形式に…

早稲田大学プログラミングコンテスト2019 F - RPG

F - RPG 解法 「全ての頂点に対し、頂点 からのパスと、頂点 へ向かうパスが存在する」「閉路がない」という制約から、無駄な辺/頂点はないということが分かります。具体的には全ての パスを考えた時、全ての辺/頂点についてそれを通る パスが存在し、さらに…

早稲田大学プログラミングコンテスト2019 E - Artist

早稲田大学プログラミングコンテスト2019 - AtCoder 解法 まず気付くべき点は、行の区切り位置と列の区切り位置を独立に考えられることです。行・列ともに、それぞれの区切り位置を境として黒いマスの個数が反転します。 そのためまずは行(列も同様)ごとの…

早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

D - Choose Your Characters 解法 条件を満たしている区間はさらに伸ばしても必ず条件を満たすので、しゃくとり法が使えます。上手くしゃくとり法ができるように工夫をしましょう。 しゃくとり法では自キャラのほうを区間に入れたり出したりするので、それに…

早稲田大学プログラミングコンテスト2019 C - Permutation City

C - Permutation City 解法 木にする まずはグラフの形を簡単にします。距離に関する条件が「1または2である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、 連結性を保ったままいくつかの辺を削除しても、変化後のグラフ…

ABC121 D - XOR World

D - XOR World 解法 「 について○○を計算した合計を求めよ」という問題で使える実装テクニックとして、代わりに「 について○○を計算した合計」から「 のうち○○を計算した合計」を引いたものを求めると考えると、変数が減る上に同じ処理を2回すれば良いだけに…

Educational Codeforces Round 61 D. Stressful Training

Problem - D - Codeforces 問題概要 コンテスト参加者が使う 台のPCがある。 番目のPCの初期電池残量は で、消費速度は毎ステップ である。 初めに充電器の充電速度として非負整数 を決め、以下の処理を ステップ行う。 各ステップごとに、どのPCを充電する…