SAKANAQUARIUM 2024 "turn" に参加しました。 参加したのは2024年4月21日の幕張メッセ公演2日目です。 ※内容に関するネタバレが含まれますので閲覧には十分注意してください。 前日まで 席はA注釈Lブロックでした。 事前にロッカー券（M）の購入は済ませてい…

問題 解法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上にある辺かそうでない辺（後退辺…

多い&難しい気がするが、思いつくままに…… 学業 M1の間に授業は取り切る 1週間に1本以上論文を読む 成果を出して学外発表をする 競プロ AtCoder Algorithm 2100 AtCoder Heuristic 1600 Codeforces 2100 AC Count 3500 作問してyukicoderに投稿 JAGでお手伝…