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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

お題箱より。 I - Number of Substrings 解法 ※この問題における文字列 の部分文字列とは、 の連続な部分を取り出した文字列であることに注意してください。慣習的に、「部分列」と書くと連続とは限らない取り出し方、「部分文字列」と書くと連続な取り出し…

お題箱より。 C - 2D Plane 2N Points 以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。 解法 考察 2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば 座標でソート…

Problem - F - Codeforces 自分の解法が非想定解っぽいので書き残しておきます。 問題概要 を正整数とする。 の数字からなる文字列が -primeであることを、以下の2つをともに満たすことと定義する。 全ての数字の和が である。 任意の連続部分列について、そ…

お題箱より。 C - 特別講演「括弧列と塗り分け」 解法 この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。 それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張…

お題箱より。 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder 解法 箱を並び替えても答えが変わることはないので、 の昇順に並べておきます。 各箱から玉を1個ずつ取り出し、ある1つの色 の玉がちょうど 個選ばれる場…

お題箱より。 Aizu Online Judge 解法 重み の負辺を足してできるだけ重み合計が大きい（ に近い）負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が 未満であるもののうち一番大きいものの重み」が分かれば良…

お題箱より。 Aizu Online Judge 解法 1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存…

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。 E - Smart Infants 解法 解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。 今回は以下のようなデ…