問題 解法1 クエリ平方分割 もしクエリが1つしかない場合、以下の方法で求められる。 森の連結成分ごとに適当に根を取り、DFSで各頂点の親を求めると、各クエリについて、 と の親のいずれかが候補になるため、親を とすると、辺 と辺 が存在するかを、辺集…

問題 解法 適当に の領域を3つの長方形に区切り、さらにそれぞれの長方形から の正方形を取り出すと考えて良い。 その場合、3つの長方形の区切り方は以下の6つのいずれかになる。 |--------| |--------| | | | | | | |--------| | | | | | | | | | | |------…

問題 解法 に操作を行うと または に移る。 つまり、 に操作を行うと または に移る。 ここで という変数を導入すると は操作後に または に移るといえる。 これで と を独立に考えることができるようになったため、答えは になる。 #include "my_template.h…

問題 解法 以下 0-indexed とする。 の場合、区間を一方向に伸ばしながら Segment Tree 上の二分探索を行うなどして求める。 それ以外のとき、各 に対し、自身より大きい値か小さい値かしか興味がないので便宜上 + と - とおく。 (1) +0+ や -0- のとき この…

問題 解法 現在時刻を とすると、ダイクストラ法で各遷移において となる最小の を求めることができれば良いので線形合同式が解ければ良い。 しかしこれを解くのは意外と難しく、法が素数ではないときに逆元がないが が解を持つという場合がある。（例： に…

問題 解法?（本題とは関係なし） まず、dp[i][j][k] = i 個目まで見て末尾が j で k 個続いているものの個数 として各要素の遷移に かけて全体 のコードができる。 （下記コードのコメントアウト部分に対応） 簡単に思いつく高速化としてほとんどの a は dp[…

問題 解法 公式解説の内容を（巨大近傍法を除き）実装（124895469点） に変更（コンテスト1位の shindannin さんのパラメータを採用） を線形に減少するように変更（ から に） 差分計算における prev, next の求め方を std::set を使わずに線形探索に変更（…

問題 解法 「mex を追加する、または mex 以外を追加する」という操作において、種類数という情報だけで遷移元と遷移先を表現できる（情報として十分である）ということに注目する。 dp[i] = 数列の要素が i 種類 とすると mex を追加する場合: 種類数だけで…

問題のリンク 解法1（LowLink） LowLinkのアルゴリズムをベースに少し改良を行い実装する。 ところで、LowLinkを改良するアルゴリズムを考えるときには、（実際にはまとめて行っているが）まずDFS Treeをとり、そのDFS Tree上にある辺かそうでない辺（後退辺…

問題のリンク 解法 線形代数の授業でやるような掃き出し法を、 行 列の行列で、左側を上位ビットとみなすイメージでやる。 すると、総XORで作れる要素を昇順に並べたときに 番目に来るような要素について、 の ビット目が経っている場合、基底の（2進数で見…

ICPC 2023 Asia Yokohama Regional に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。 メンバー pointN 構築やインタラクティブなど天才ゲーを担当する。 niuez データ構造や木が得意。実装を担当することも多い。 ruthen 2 人…

ICPC 2023 国内予選に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。 チーム名の由来は 3 人ともハンドルネームに N が含まれていたためです。 本番前 今年の4月下旬くらいにチームが決まり、毎週末のどちらかを主な練習日に充…

模擬国内2020D 公式解説以上の情報はありません。 問題のリンク 解説? 普通の括弧列の場合は ( に +1 を、) に -1 を割り当てて、総和を 0 に、prefix sum が常に 0 以上となるかを判定する。 今回は、 ( に +2 を、) に -2 を原則割り当てるが、連続する 2 …

問題のリンク 遅すぎるかも。 解法 シートA, Bは少なくとも1つ以上の黒いマスを含み、そのマスは必ずシートXのいずれかの黒いマスに対応する。 よって、それぞれのシートから1マスずつ選び、シートXのどのマスに対応するかを全探索し、シートXのそれぞれの黒…

模擬国内2017D 問題のリンク 解説 単調性があるため、 で二分探索をする。 を決め打ったときに、最小で何体モンスターを倒す必要があるか求めることができれば、それが 以上かを判定することで解くことができる。 倒すための最小のモンスター数について求め…

Div. 2 の E まで。 コンテストのリンク A の値が小さい順に を に足す。 提出コード B にするとする。 は素数だけ考えれば良い。 の倍数は連続する区間においては 個おきに出てくるので、最も頻繁に出てくる 2 の倍数にできれば良い。 1 回の操作で奇数は 1…

E まで。 E の計算量解析できないの危機感を感じる。 コンテストのリンク A ランレングス圧縮して各要素について個数が 2 個以上か確かめる。 提出コード B をどうするかで最終的な数列は 3 通りできる。 それぞれにできるかどうかは絶対値の差がすべて 1 以…

ABC275 で AtCoder 黄色になりました。 ほとんどがポエムなので、物好きな方以外は最後の「おすすめコンテンツ」だけ読んでもらえれば十分だと思います。

解けたのでおまけがメイン。 問題のリンク 概要 与えられた単純無向グラフについて、辺を 本以上取り除くことでいくつかの完全グラフに分割するときの、完全グラフの個数の最小値を求めよ。 解説 個の頂点集合を順に列挙し、それぞれの頂点集合に対し、その…

解説ACした。最適化が苦手。 問題のリンク 概要 正整数 が与えられるので、 が の倍数になるような非負整数 の組に対し、 の最小値を求めよ。 解説 のとき となる。(そもそも となる必要があるため) のとき であるとする。 は解なので、 のとき、 となるので…

ICPC 2022 国内予選に shuz*, nope, ruthen で shichifuku として参加しました。 このチームは 3 年目となります。 本番前 チーム練習は 6 月中旬から、サークル活動で AOJ-ICPC の問題を解きました。 模擬国内予選 2022 の成績は以下になります。 jag-icpc.…