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でお手伝…

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

2022年9月に友人に誘われてVALORANTというゲームを始めたのですが、1年とちょっとかけてようやくゴールド1になることができました。 何をしたかや今の自分の考えを整理しておくためにも、約1年間を振り返る記事を書こうと思います。 プレイ時間の内訳 モード…

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

Macbook Air Apple M2 を購入し、競プロの環境構築中に遭遇したエラー。 すでに Homebrew で gcc をインストールしており、g++ で clang ではなく gcc が呼び出されているようになっている。（Homebrew GCC 13.2.0） 再現コード #include <vector> int main() { std:</vector>…

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のそれぞれの黒…

ABC307 F - Virus 2 でハマったのでメモ。 ツイートは こちら。（教えてくださった方に感謝。） a < b という関係が成り立つときに a から先に要素を取り出したいとします。 ダメなやつ auto comp = [](const T& a, const T& b) -> bool { return a < b; }; …

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

個人参加で13位でした。 [Easy] [Reversing] passcode以外のEasyまでの全ての問題と、MediumのPPCを解きました。 [Newbie] [Misc] 2DCode 1 Hintを開けるとDotCodeだとわかり、free barcode scanner dotcodeなどと調べるとオンラインリーダーがヒットする。 …

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.…

day Topcoder Codeforces AtCoder AOJ yukicoder library-checker Sum 2020/11/06 0 52 890 58 0 0 1000 2020/11/16 0 57 914 70 0 0 1041 2020/11/23 0 64 928 70 0 0 1062 2020/11/29 0 76 934 70 0 0 1080 2021/01/12 0 94 937 71 0 0 1102 2021/01/19 0 …