ARMERIA

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

競技プログラミング

Codeforces Round #587 (Div. 3) E2. Numerical Sequence (hard version)

Problem - E2 - Codeforces 問題概要 正整数 に対して、 を十進表記で書いたものをこの順に連結した文字列を とする。そして、 をこの順に連結した無限の長さの文字列を考える。与えられる 個の整数 に対して、この文字列の 番目の文字を答えよ。 制約 解法 …

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つ要素を挿入して、辞書順でより大きい長さ の数列を作る…

競プロでWAが出たときのランダム入力データ生成入門

概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力デ…

TTPC2019 オンライン参加記

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

Codeforces Round #577 (Div. 2) B. Zero Array

お題箱より。 Problem - 1201B - Codeforces 問題概要 個の正整数 が与えられる。これに 異なる2つの要素を選び、それぞれの要素を1減らす。 という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。 制約 解法 この判定は競技プログラミングで…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion

C - Cell Inversion 解法 各マスの操作のされ方は、 自分より左のマスとペアになって、1つの反転操作区間の終点になる 自分より右のマスとペアになって、1つの反転操作区間の始点になる のどちらかです。そして各マスがそのどちらになるかは、実は端から順番…

「みんなのプロコン」本選 A - YahooYahooYahoo

お題箱より。 A - YahooYahooYahoo 解法 「編集距離DP」を知ろう まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。 置換: の任意の1文…

AtCoder Beginner Contest 135 D - Digits Parade

お題箱より。 D - Digits Parade 「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたい…

AtCoder Beginner Contest 138 F - Coincidence

F - Coincidence 解法 考察も実装もそこそこ重い問題です。順に考えていきましょう。 記法について 剰余演算を記号 、XOR演算を記号 で表すことにします。 またこの記事では数え上げの対象である2数のペアを ではなく の順番で記載しています。 ビットだけの…

CODE THANKS FESTIVAL 2017 H - Union Sets (並列二分探索解法)

お題箱より。 H - Union Sets 「公式解説で省略されている並列二分探索について知りたい」というリクエストだったのですが、私も実装したことがなかったので調べて書いてみました。私にとっても勉強になりました。 参考資料 参考にしました。 Parallel Binar…

AtCoder Beginner Contest 136 D - Gathering Children

D - Gathering Children 私の解法をTwitterに流したらわりと好評だったので記事にまとめておきます。 解法 ある程度動きをシミュレーションしてみると、十分に時間が経った後は全ての子供が RL の2マスで振動するということが分かります。最終状態を求めるた…

AtCoder Beginner Contest 136 F - Enclosed Points

F - Enclosed Points 解説 数え上げの軸を変える 個の部分集合それぞれについて、その集合に対応する長方形に 個の点のうちいくつ含まれるかを考え、それを全て合計したものを求めよ。 という問題です。部分集合の数が多すぎますね。まともに列挙するのは到…

AtCoder Beginner Contest 051 B - Sum of Three Integers

お題箱より。 B - Sum of Three Integers 計算量の考え方に入門するのにとてもいい問題です。 解法について知りたい…というリクエストだったので、色々な計算量で解く方法を解説してみました。 解法 全ての基本、全探索です。 を満たす を全て試します。和が…

HUPC2019 Day1 D: 貪欲が最適?

お題箱より。 Aizu Online Judge Arena 解法 答えとなる金額の払い方の必要条件を考える ある金額 について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額 は条件を満たす」と書くことにします。そして条件を満たす最小の金額(答え…

AtCoder Beginner Contest 135 E - Golf

E - Golf 解法 コの字の作り方を考えてみる まずは考えやすい&実装しやすいように座標変換をします。 に負の値がある場合、符号反転させて両方とも非負としておきます。 始点 から終点 までボールが移動する軌道は、長さの総和が の倍数になっている必要が…

AtCoder Beginner Contest 134 F - Permutation Oddness

F - Permutation Oddness ※問題文で与えられている は小文字ですが、 を添え字として使いたいので本記事では と表記します。 解法 順列のDP 順列の場合の数を求める問題です。何か条件を満たす数列の個数を求める問題として「左からDP」というのはメジャーな…

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演算は繰り上がりのない足し算と思うことができます。 このことを確かめるために、 の…