ARMERIA

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

プログラミング

Ritsumeikan University Programming Contest 2013 (AOJ 2507) Computer Onesan

お題箱より。 Aizu Online Judge 解法 実は過去の解説記事に類題があります。 Educational Codeforces Round 17 D. Maximum path - ARMERIA Codeforcesの問題は最大化でAOJの問題は数え上げという違いはありますが、解法はほぼ同じです。 左上から右下に向か…

yukicoder No.1460 Max of Min

お題箱より。 No.1460 Max of Min - yukicoder 解法 この問題の解法はいくつかのステップで構成されていて、その1つ1つが覚えておくと有用なテクニックだと思います。順に追っていきましょう。 ステップ1 求めたい値 は、与えられた数列の要素に対して と を…

AtCoder Beginner Contest 195 F - Coprime Present

お題箱より。 F - Coprime Present 解法 互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。 集合 とします。求…

AtCoder Heuristic Contest 001 参加記

A - AtCoder Ad 得点率97.4%で130位でした。 seed値0の入力に対する解のビジュアライザ出力です。 考察 スコアの計算式を見ます。各企業が指定する1マス(以下、指定マスと呼びます)を含めないとその企業からの点は貰えないので、まずこれは含める必要があ…

AtCoder Regular Contest 047 C - N!÷K番目の単語

お題箱より。 C - N!÷K番目の単語 解法 ※この解説の「何番目」という表記は全て1-indexedです。 一般に を 以上 以下の整数として、 個の順列のうち辞書順で 番目にあるものを、前の要素から順番に求めていく方法を考えます。 最初の要素は、 個の順列を辞書…

PAST公式テキストを書きました

このたび、マイナビ出版から発行される「アルゴリズム実技検定 公式テキスト(エントリー~中級編)」の執筆をさせていただきました。kenkooooさんとの共著です。 アルゴリズム実技検定 公式テキスト[エントリー~中級編] (Compass Booksシリーズ)作者:岩下 …

AtCoder Regular Contest 112 B - -- - B

B - -- - B 解法 ある整数 を作ることが可能か判定するときには、 を最小のコストで作る操作列だけを考えれば十分です。作りたい整数を最小のコストで作る操作列が、何らかの限定的な特徴を持つことを見つけられると非常に見通しが良くなります。 その特徴を…

AtCoder Regular Contest 099 E - Independence

お題箱より。 E - Independence 解説 問題文をグラフ理論の言葉で解釈します。 個の頂点を2つの集合 に分け、それぞれの集合内では任意の2頂点間に辺が存在している(すなわち、クリークになっている)必要があります。 の頂点数をそれぞれ とすると、最小化…

AtCoder Grand Contest 047 D - Twin Binary Trees

お題箱より。 D - Twin Binary Trees 解法 ちょうど2本の特殊辺を持つ単純サイクルは、第1の木の異なる2つの葉の組み合わせと同じ個数だけ存在します。このサイクルは、その2つの葉の第1の木におけるLCAと、それらと接続されている第2の木の2つの葉のLCAとを…

AtCoder Grand Contest 046 D - Secret Passage

お題箱より。 D - Secret Passage 解法 操作の特徴をつかむ 与えられる文字列 の長さを とします。また の 文字目を と表記します( 先頭は です)。 操作列によって文字列がどのようになるかを、まずは大雑把に理解しましょう。前から順に操作されるため、…

CodinGame Fall Challenge 2020 参加記

ゲームAIコンテスト「CodinGame Fall Challenge 2020」に参加して、Legendリーグ63位でした! どんなゲーム? アニメーション:Game Replay - CodinGame 素材からポーションを作ってお金を稼ぐゲームです。各プレイヤーはターンごとに「注文リスト内のポーシ…

Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155)

お題箱より。 Aizu Online Judge 解法 最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。 の最小公倍数(LCM)は、全ての素数 について各要素における の重複度の最大値 を求め、 …

第11回日本情報オリンピック 予選 E - イルミネーション

お題箱より。 E - イルミネーション (Illumination) 解法 座標の表記について、(縦の座標, 横の座標)という順番で表記することにします。こちらのほうが配列の添字順と合うので都合が良いです。 公式解説と同じく、与えられる領域の外周にもう1つ分の六角…

AtCoder Regular Contest 106 D - Powers

D - Powers 解法 である全てのペア について、【 と について対称な式】の値を合計せよ。 という問題設定はよく登場します。このような問題では、 という条件を外して かつ である全てのペア について、【 と について対称な式】の値を合計せよ。 と考えると…

AtCoder Grand Contest 048 B - Bracket Score

B - Bracket Score 解法 正しい括弧列の必要十分条件 いわゆる「正しい括弧列」の問題です。よく使われるアプローチとして累積和がありますが、今回は括弧が2種類あるので2つの累積和を管理する必要があり厳しそうです。 今回は別の性質を使うことにします。…

AtCoder Grand Contest 048 D - Pocky Game

D - Pocky Game 解法 各山の石の個数について、その初期値を と表し、ゲームの途中経過における値を と表すことにします。 まずは全ての状態を網羅するDPを もし石の総数が十分少なければ、以下のDPで全ての局面の勝敗状態を求めることができます。 :「先手…

個数制限付き部分和問題+条件を満たす選び方の数え上げ

先日のコンテストの問題における、最後の高速化について知りたいというリクエストがあったため、解説を書きます。より一般的な「個数制限付き部分和問題+条件を満たす選び方の数え上げ」という枠組みで説明します。 扱う問題 正整数 と、正整数からなる長さ …

AtCoder Regular Contest 104 E - Random LIS

E - Random LIS 公式解説とは違う解法です(たぶん)。 解法 あり得る全ての場合に対するLISの長さを合計して、全事象数 で割ることにします。 取っ掛かりが非常に掴みにくい問題ですが、 という制約から何らかの全探索をやることを目指してみます。 座標圧…

Codeforces Round #673 (Div. 1) D. Graph and Queries

Problem - D - Codeforces コンテスト中に自分が通した解法を書きます。 問題概要 頂点 辺の無向グラフが与えられ、頂点 には相異なる整数 が書かれている。 以下のクエリを合計 個処理せよ。 1 v:頂点 と連結な頂点の中で最も大きい整数が書かれている頂点…

第三回 アルゴリズム実技検定 C - 等比数列

お題箱より。 C - Geometric Progression 解法というよりは「こういう問題を解くための思考プロセスが知りたい」というリクエストだったので、その方向で書きます。 解法 この問題は結局、等比数列の性質を知識として知っている、または実験によって理解する…

ACL Beginner Contest F - Heights and Pairs

F - Heights and Pairs 解法 まずは入力を各身長ごとの人数として集計します。 を身長が である人の人数とします。 であり、 人であるような身長を無視すれば身長の種類数は 以下です。 条件を満たす組み方をDPなどで直接数えようとすると、 から落ちず厳し…

ACL Beginner Contest E - Replace Digits

E - Replace Digits 先日、AtCoder Libraryの遅延伝播セグメント木の使い方について記事を書きました。 AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA 今回の問題はセグ木にちょっと変なものを乗せる問題なので、上記の記事で解説していることの実践編と…

AtCoder LibraryのLazy Segtreeのチートシート

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA こちらの記事でAtCoder LibraryのLazy Segtreeの使い方を説明しましたが、コンテスト中に読んでられっか!みたいな時のためにコピペで使えるチートシートをまとめます。整数列に対する、以下の組み合わせ6…

AtCoder LibraryのLazy Segtreeの使い方

AtCoder Libraryが遅延伝播機能を持つセグメント木 atcoder::lazy_segtree を提供しているものの、何か渡すものいっぱいあるしドキュメントは数学用語だらけだしよく分からん!みたいな人向けの記事です。 問題を解いていて、セグメント木に必要な機能(区間…

Educational Codeforces Round 11 E. Different Subsets For All Tuples

お題箱より。 Problem - E - Codeforces 公式解説より楽な解法があるのでそっちを紹介します。記事最後に、リクエストにあった公式解説の補足についても説明します。 問題概要 整数列 に対して、 を「 の部分列(連続でなくても良い)として登場する長さ 以…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip

お題箱より。 D - Swap and Flip 解法 この問題のように「操作する場所を選んで、決められたルールに従って操作する」ということを繰り返す問題では、1回目の操作の選択、2回目の操作の選択…といった分岐パターンを直接探索していくのは非常に大変です。操作…

AtCoder Beginner Contest 178 F - Contrast

F - Contrast 解法が色々ある問題。シンプルで実装も楽な解法1と、私が本番で解いた解法2を証明付きで紹介します。前者のほうが断然オススメ。 解法1 まず 合計で 個を超える値が存在する場合、どのように並べても となる箇所が存在してしまいます。この場合…

Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces 問題概要 インタラクティブ問題である。 まず正整数 が与えられる。ジャッジは 以上 以下の整数 を持っている。また集合 があり、初期状態では である。 以下のクエリを合計 回まで投げることができる。 の値を特定し、Cクエリで解…

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

お題箱より。 Problem - D - Codeforces 問題概要 本のビルがあり、 番目のビルの高さは である。 ビル からビル へは、 かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。 :ビル は隣り合っている。 :間にあるビルが全て、…

POJ NO.3686 The Windy's

お題箱より。蟻本に載っている問題です。 3686 -- The Windy's ※ライブラリをC++98に対応させる気になれなかったのでACコードはありません。蟻本に載っているのでそちらを… 問題概要 個のおもちゃ工場があり、 個のおもちゃの注文を受けた。おもちゃ を工場 …