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次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば 座標でソート…