ダブリング
opt さんの得意系って感じだった！ 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
木上のパスに関する問題！！ LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…
「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…
異様に難しかった！！ 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…
回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…
頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …
ツリー上のパスクエリについての教育的典型題だった 問題へのリンク 問題概要 (意訳) 頂点の重み付きツリーが与えられる。以下の 個のクエリに答えよ。 各クエリは 2 頂点 , と値 が指定され、ツリー上の と とを結ぶパス上の辺の重みの積を求め、それと を…
操作を 回行った結果を求める系、苦手意識あるけど克服したい！ 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…
これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…
重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…
居酒屋からのエクストリーム参加。D 問題が面白そうだったので突っ込んだ。解けてよかった！！！ 問題へのリンク 問題概要 から までの整数からなる 2 つの順列 に対して、新たな順列 を以下のように定める: := 項目の値は である 今、順列の列を で定める。…
NTT と聞いて 問題へのリンク 問題概要 偶数 が与えられる。 十進法表記で () しか登場しない 桁の整数のうち、 前半 桁の各位の和 後半 桁の各位の和 が等しいものが何通りあるか、998244353 で割ったあまりで答えよ。leading zero は OK。 制約 考えたこと…
好きだけど細かいところで時間とられるやつなん 問題へのリンク 問題概要 整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって N <= 20 M <= 60 任意の辺 (u, v) について u < v でなければならない 頂点 1 から頂点 …
きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …
