ARMERIA

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

競技プログラミング

AtCoder Regular Contest 052 D - 9

D - 9 公式Editorialと違う解法で解いたので記録。 計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした… 解法 まず桁DPを考えました。以下のように状態を考えることができます。 上から 桁目までの数字まで決めて、そこまで決めた値を で割った…

CPSCO2019 Session2 E - Mogu Mogu Gummi

お題箱より。 E - Mogu Mogu Gummi 解法 木DPを考えてみる 「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。 シンプルなグラフを例にして考えてみましょう…

天下一プログラマーコンテスト2016予選A B - PackDrop

お題箱より。 B - PackDrop 解法 まずは問題をシンプルに みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。 ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付…

Codeforces Round #573 (Div. 1) C. Tokitsukaze and Duel

Problem - C - Codeforces 問題概要 0または1からなる 文字の文字列 と整数 が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する 文字を選び、それらを全て0または全て1にする」という操作を行う。…

AtCoder Beginner Contest 133 F - Colorful Tree

F - Colorful Tree 解法 木の2点間距離たくさん→LCA 長さの変更についていったん無視すると、この問題は「木の2点間距離をたくさん求めてください」というものです。これはLCA(最小共通祖先)というものを用いると効率的に求めることができます。 根付き木…

AtCoder Regular Contest 085 E - MUL

お題箱より。 E - MUL 解法 私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。 先人の知恵 競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリ…

Codeforces Round #570 (Div. 3) F. Topforces Strikes Back

ちょっと変わった解き方をしたので記録。 Problem - F - Codeforces (追記)公式Editorial もこの解き方でした。 問題概要 以下の問題を ケース解け。 個の正整数 が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件…

yukicoder No.778 クリスマスツリー

お題箱より。 No.778 クリスマスツリー - yukicoder 解法 飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア の個数です。 頂点 が頂点 の先祖である。 頂点番号について、 である。 ここでの「先祖」は…

AtCoder Beginner Contest 130 E - Common Subsequence

E - Common Subsequence 公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。 解法 記法について 数列 を単に 、数列 を単に と書くことにします。 与えられた数列は1-indexedで扱い、「0要素目」として空の要素…

AtCoder Beginner Contest 130 F - Minimum Bounding Box

F - Minimum Bounding Box 解法 各座標軸ごとに、動きのイメージをつかむ 時刻を文字 で表し、 に依存する変数を のように表します。 まず、 座標を分けて考えてみます。 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。 グループ1…

AtCoder Regular Contest 098 F - Donation

お題箱より。 F - Donation 私も公式解説を見て通したので、公式解説の流れで書いていきます。 解法 時間を逆回しにしてみる 考察を進めていく順番ですが、まず「時間を逆回しにする」ことを考えてしまったほうが良いように思います。普通にゲームを進めると…

AtCoder Beginner Contest 129 E - Sum Equals Xor

E - Sum Equals Xor 解法 ※ と のXOR演算を、 という記号で表すことにします。 まず注目すべきは という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。 このことを確かめるために、 の…

Codeforces Round #564 C. Nauuo and Pictures

Problem - C1 - Codeforces Problem - C2 - Codeforces 問題概要 枚の画像がランダムに表示されるWebサイトがある。各画像には重み が設定されていて、画像 の表示確率は である。 画像を 回表示させる。このとき画像が1回表示されるごとにその画像の重みが…

AtCoder Regular Contest 094 E - Tozan and Gezan

お題箱より。 E - Tozan and Gezan 解法 プレイヤーを以下のように表記します。 Aさん: を操作する。先攻。ターン数を最大化したい。 Bさん: を操作する。後攻。ターン数を最小化したい。 また、 と表記することにします。 もしゲーム開始時点で全ての につ…

Chokudai SpeedRun 002 K - 種類数 β

お題箱より。 K - 種類数 β 解法 この問題はグラフとして捉えると見通しが良くなります。それぞれの整数を頂点とし、ペア を頂点 と頂点 を結ぶ辺として考えます。整数を選ぶとことを頂点に色を塗ることに喩えると、各辺ごとに「両端の頂点のうちどちらかを…

AtCoder Grand Contest 034 E - Complete Compress

E - Complete Compress 公式解説とちょっと違う方法で通したので書いておきます。 解法 木DPを考える コマを集める頂点を全て試すことにします。集める頂点を と表記し、 を根とする木DPを考えます。 それぞれの頂点 について、それ以下にある部分木に含まれ…

Codeforces Round #556 B. Three Religions

お題箱より。 Problem - B - Codeforces 問題概要 英小文字からなる長さ の文字列 が与えられる。また文字列 があり、これらは最初は空である。 以下のクエリが合計で 個与えられる。 1 i c 文字列 の末尾に文字 を足す。 2 i 文字列 の末尾の文字を取り去る…

AtCoder Beginner Contest 127 F - Absolute Minima

F - Absolute Minima 解法 最適な の条件 定数項 については単に答えに足すだけなので、 についてだけ考えます。 更新クエリをいくつか処理した後の式 を最小にするような の値は、 の中央値になります。これは以前の記事に説明を書いているのでそちらも参考…

AtCoder Beginner Contest 127 E - Cell Distance

E - Cell Distance 解法 この問題は結構考察ステップが多いです。順番に考えていきましょう。 数え上げの順番を変える まず考えることは「数え上げの順番を変える」ことです。抽象的な書き方ですが、これが具体的にどういうことか説明します。 問題文では以…

Codeforces Round #561 F. Vicky's Delivery Service

お題箱より。 Problem - F - Codeforces 問題概要 頂点 辺の無向グラフがあり、各辺は 色のうちどれかの色で塗られている。 以下のクエリを 個処理せよ。 + x y z 頂点 間に色 の辺を追加する。 ? x y 頂点 から頂点 までの、以下の条件を満たすパスが存在す…

AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行

お題箱より。 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip 解法 グラフの最短路問題として解けそうではありますが、異なる運営会社間での乗り換えを考慮する必要があります。つまり「どの駅にいるか」だけでなく、「その駅でどの会社の路線に乗っている…

いろはちゃんコンテスト Day2 H - 根室の巫女

お題箱より。 H - 根室の巫女 解法 Morris-Pratt法について まず、公式解説(?)にも書いてあるMorris-Pratt法(MP)について触れておきます。私も実戦で使ったことはないのですが…ある長さ の文字列 があったときに、全ての に対して以下の値を求めた数列 …

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

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

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の問題を使って説明していくので、ネタバレになる点はご了承ください。 「…