この記事は元々ある問題のお題箱リクエストのために書いていたのですが、一般的にテクニックを紹介する記事＋その問題を例題として解説、という流れにすることにしました。 まれによく出題される、「セグメント木に行列を乗せる」とはどういうことか。多くの…

お題箱より。 D - パスタ (Pasta) 解法 ※実装に合わせて、0-indexedでの記述とします。最初の日は 日目です。 日目から順番にパスタの種類を決めていくことにします。ルールは「事前に指定された日のパスタの種類は決まっている」ことと「3日連続で同じパス…

F - Distributing Integers 解法 「頂点に整数を書く」だと少し図示しづらいので、代わりに「頂点番号の書いたボールを処理する順番に並べる」として考えることにします。 最初にボールを置く頂点を根付き木の根とします。まずは根を頂点 に固定して問題を解…

お題箱より。 Problem - D - Codeforces 問題概要 人の子供がいて の番号を持っている。以下の 個の操作についてそれぞれ、実行するかしないかを選ぶことができる。 区間 に属する子供に1個ずつキャンディを与える。 ここで整数 が与えられ、 個を超える操作…

お題箱より。 E - Max GCD 解法の正当性について知りたいというリクエストだったので、そこをメインに解説します。 解法 操作によって全ての要素の合計は変わりません。そして操作後の の全要素が値 の倍数であるならば、 の合計値も の倍数であるはずです。…

お題箱より。 Aizu Online Judge Arena 解法 公式解説と逆になってしまいますが、与えられる を改めて と定義します。これが正である頂点は「過剰なので減らす必要がある」、負である頂点は「不足しているので増やす必要がある」ことになり、全ての を にす…

お題箱より。 E - Second Sum 解法 まずは「数え上げの順番をひっくり返す」という発想が大事です。 全ての区間 について、その区間内で2番目に大きい値 を求め、合計する をひっくり返して、 順列内の全ての要素 について、その要素が2番手になるような区間…

イマイチ良い言葉が見つからなかったのでタイトルが長くなりました。最近見る機会が多かったので記事を書いてみます。 以下のような形に帰着されるような区間の数え上げに使えるテクニックです。 例題 以下の2つの数列が与えられる。 左端から見た右端の条件…

Problem - F - Codeforces 問題概要 整数 と、整数の組 が 個与えられる。以下の条件を満たす長さ の整数列 の個数を で求めよ。 全ての要素は を満たす。 整数の組 で表現される以下の条件を 個全て満たす。 のビットANDを取った値がちょうど となる。 制約…

D - Merge Triplets 解法 操作の説明で登場する長さ の数列たちを「ミニ数列」と呼ぶことにします。 結果的にできる順列にどのような特徴があるかを考える上で、まず一番大きな値に注目すると良いと思います。 最大値 は、 が存在しているミニ数列以外の要素…

Problem - E - Codeforces 問題概要 から までの順列 が与えられる。 爆弾が仕掛けられているインデックスの集合 を考える。 に対して以下のように計算される値を と定義する。 を空集合とする。 の順に以下の操作を行う。 集合 に を追加する。その後 なら…

Problem - G - Codeforces 問題概要 個の相異なる英小文字列からなる集合 がある。この集合の要素 それぞれについて以下を求めよ。 文字列 を空文字列から始めて、以下の2つの操作を好きな順番で繰り返して と一致させるための最小コストを求めよ。 操作1： …

Problem - C - Codeforces 問題概要 左側、右側それぞれに 個の頂点があり、その間に合計 本の辺が存在する二部グラフが与えられる。右側の頂点にはそれぞれ正整数 が書かれている。 左側の頂点の部分集合 について、 を「右側の頂点のうち の要素のいずれか…

お題箱より。 B - 準急電車 (Semiexpress) 解法 後戻りできないこと、急行が停まる駅には必ず準急も停まることから、駅 からある目的駅までの最適な移動経路は「行けるところまで急行で行く→行けるところまで準急で行く→残りは普通で行く」となります。 その…

Problem - E - Codeforces 問題概要 整数 が与えられる。以下の条件を満たす長さ の数列 を1つ構築するか、そのようなものが存在しないことを判定せよ。 各要素は 以下の正整数である。 狭義単調増加である。 かつ を満たす3つ組 の個数はちょうど 個である…

お題箱より。 Programming Problems and Competitions :: HackerRank 公式解説はこちらで公開されています。 ゆるふわオンサイト#3 解説 - Google スライド 解法 2点をswapするクエリを処理するような問題は、swapであることを上手く活用するような解法も考…

お題箱より。 Problem - E - Codeforces 問題概要 頂点の木が与えられ、各頂点には a から t までのうち1文字のアルファベットが書かれている。 この木の2点間を結ぶパスであって、「通過する頂点のアルファベットを並び替えることで回文にすることができる…