本邦でおそらく規模最大の模試である Day1 倫理，政治・経済 感触は難化だった。過去 3 年分の問題（追試含む）では、かなり粗い知識でも倫理が取れた（政経と合わせて 85 ~ 100 点程度）のだが、要求精度が高くなった印象がある。 政治・経済は普通くらいの…

問題リンク difficulty 高くない？（位置の影響かなあ） 解説 先手も後手も操作と最適化の内容が全く同じなので、適宜先手と後手を入れ替えて考えればよい。 $dp[i][j] =$ 区間 $[i,j]$ から始め、互いが最適に行動したときの先手 - 後手の値 として区間 DP …

書くのが面倒なので極力まで省略します 自己紹介動画 めちゃめちゃ急いで撮りましたが、左上にぼざろを貼りました 競技 1 問目 map と stack で実装しました バグったのでランダムチェッカーを書いたけど 20 分くらいで通った 2 問目 影響力の降順に見ていっ…

物理チャレンジ'22 に参加し、金賞と理研計器賞（高 2 以下総合優勝）を頂きました。（単独で本名が完全に特定可能になってしまう情報が初発生。JOI 本選中学生最高得点とかもあったけど非公開な気がするので。） 去年も書きましたが、布教のために私が物チ…

nullcon HackIM CTF 2022 に参加しました。 ctftime に載ってて Weight も 0 だったのでとりあえず出てみようということで。 1 完ですが、半分くらい解けたやつもあるので writeup っぽいものを書きます。 Web Jsonify 置いてある URL にアクセスすると PHP …

運営がみんな運営記を書いてるので、書きます たいしたことは書かないので細かいことは オリバー奮闘運営記 を見て 全体運営 基本的にほぼ oliver しかやってなかった。そもそも大学セミナーハウスとの連絡を彼が全部取ってるので自然とそうなる。実質運営長…

背景 JOI 夏季セミナー ハイレベルコースの実施が、情報科学の達人の実施に伴って停止されました。 > 上級層の育成強化は，「情報科学の達人」プログラムの活用を図り，従来の夏季セミナー（ハイレベルコース）は，当該プログラムが実施される間は，開催を見…

人々よりひと足早い春合宿参加記です。 本選 JOI 2021/2022 本選参加記 を見てください。 D が解けてないので弱いほう Day 0 2021 春合宿 2-2 Road Construction を解いた。 平面走査を何回もして二分探索で境界値を探したあと、set で具体的な答えを構築す…

JOI 本選に参加してきました ギリギリ春は通ってそう（行くとは言ってない） 得点獲得の記録 06:19 A 100 点 29:47 B 10 点 33:39 B 100 点 54:14 C 5 点 56:11 C 10 点 98:26 C 61 点 121:09 C 100 点 152:33 D 8 点 167:46 E 9 点 177: 45 E 19 点 222:30 …

久しぶりのはてブロです。 問題リンク 解説 ある整数 $k$ があるとき、$2k \oplus (2k + 1) = 1$ なのを利用する。 区間の xor は、端の偶奇で場合分けをして次のように求められる。 $l$ が偶数、$r$ が偶数のとき 区間の xor は、$r$ と、$(r-l)/2$ 個の $1…

国際物理オリンピック日本代表候補に選抜されました。実感がありません。 第 1 チャレンジを通過した際もいろいろ（本当にいろいろか？）書きましたが、せっかく選抜されたのでもうちょっと細かく書きましょうかということで きっかけ 数理の翼伊計島セミナ…

問題リンク 解説 DP などを考えても解けそうにない。 行基本変形に思いを馳せる。$N \geq M $ を仮定して、掃き出し法を行ってみる。この行列の rank を $R$ とする。 処理後の行列を眺めると、$R$ 次正方行列についてこの問題を解いて、それに $2^{N+M-2R}$…

解説 AC 組み合わせ苦手すぎる… 問題リンク 解説 求める値は、全ての配り方におけるうれしさの総和である。 ここで、うれしさを「子供が持っているクッキーの中から $1$ 枚を選ぶ方法の数」と言い換える。（これがめちゃくちゃ重要） 選ばれるクッキーを配っ…

正式名称は「物理チャレンジ 第一チャレンジ」 きっかけ 去年の数理の翼 N セミナーで @masageophysics さんの話を聞いた その年は自分は申し込みを忘れて、彼は振り込みを忘れたんですが… 参加前 春になって物チャのことを思い出したので、本校物理科 I 先…

タイトルが小泉進次郎すぎる 概要 $dp[i][j]$ のうち、$0\leq j\leq |\mathrm{children}(i)|$ に定義されて、子から遷移していくタイプの木 DP では、計算量が $O(N^2)$ になる（常識） $N$ 個の頂点をマージしていく形に帰着できる。サイズ $S_l$ と $S_r$ …

準備やりました。 問題リンク(Twitter/原案) 問題リンク(AtCoder) 解説 「家 A に入る前に家 B に入らなくてはならない」という条件がたくさんあるので、燃やす埋める問題です。 最大流問題を解けばよいです。 サンプルコード #include <cfloat> #include <climits> #include <iostream></iostream></climits></cfloat>…

準備やりました。 問題リンク(Twitter/原案) 問題リンク(AtCoder) 解説 木は二部グラフなので、大きい方から $\frac{N}{2}$ 個取れば良いです。 サンプルコード #include <algorithm> #include <iostream> #include <vector> #define rep(i, n) for (int i = 0; i < int(n); i++) #define </vector></iostream></algorithm>…

「kaage精進録」に精進のしょの字もない記事を載せるのは初めてな気がする。 ここで「しょの字もない」と「しの字もない」どちらにするべきかで5分くらい悩んだのは置いておこう。 さて、昨日俺ガイルの聖地巡礼に行ってきたので、なんか書こうと思う。 なお…

問題リンク 面白かった 解説 累積和みたいなことを考えると、上矢印と下矢印をつなげて、縦幅をなるべく小さくする、みたいに読める。 すなわち、初期位置を $0$ とすると、'0' が出てきたら位置に $-1$、'1' が出てきたら位置に $1$ を加算していって、その…

準備やりました． 問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ) これも QCFium 法が通ったので，制約が上がりました． 解説 小課題は略 円環の問題だが，実は好きなところで切って考えられる． 互いに被覆し合わない，重なる区間の組の数が数えたい．こ…

準備やりました． 問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ) QCFium 法が通ったので制約が上がりました． 解説 $A_i$ をソートして，$B_j$ の前後にある数との差の小さい方を取れば良いです． $B_j$ の $A$ の中での位置は，二分探索によって求めら…

考察のほとんどいらない別解が思いついたので，書きます 問題リンク 解説 答えを二分探索する． まず，必要な日数は明らかに $2\cdot\mathrm{sum}(A)\leq3600000$ で抑えられる． また，日ごとに出勤する従業員の組み合わせは高々 $O(2^N)$ になるので，全日…

なんでこんな記事を書いているか CTF やろうと思って適当な記事を読んだら意味不明だったので… Villager A 問題リンク CTF です． 解法 まずはサーバーにアクセスしてみると，flag.txt と q4 というふたつのファイルが見つかる． cat flag.txt を試みると，…

二分ヒープを書きました 二分ヒープ is 何 平たく言えば std::priority_queue みたいなやつ 次の操作がいい感じの計算量でできる top() 最大値を取得する $O(1)$ pop() 最大値を削除する $O(\log N)$ push(value) 値を追加する $O(\log N)$ 構造 二分木を持…

問題リンク 解説 まず、$N'$ 頂点の木に対しての場合を考える。 次数が奇数になる頂点の集合を適当にとると、要素数を $x$ 個として、$x$ が奇数ならそのような部分グラフは $0$ 通り、偶数なら $1$ 通りとなる。 $N'=1$ のとき明らかに成り立ち、それ以外は…

問題リンク 面白かった。 解説 まず、愚直な DP を考えてみる。「$dp[i][j] =i$ 番目までで、$j$ で終わっているときの、ここまでの置き方の通り数」とすると、自明に解けるが、これでは当然通らない。 $A_i$ を座標圧縮して、同じ区間に含まれる数はまとめ…

問題リンク シンプルながら FFT への帰着がきれいで、良い問題だと思う。 解説 ビット文字列 $T$ を $S$ の部分文字列とするには、最小何ビット反転させればよいかを求める問題。 単なる文字列検索なら KMP 法を使ったりすればよいが、今回はビットの反転数…

問題リンク 数え上げ，苦手 解説 数をグループにして考える．$h$ に含まれる $i$ の数を $n_i$ としておく． $n_i$ 個の数があるグループの中に重複を少なくとも $k$ ペア作る方法の数は $\binom{n_i}{2k}(2k-1)!!$ 通りある． これを多項式の係数にして畳み…

破滅 10:00 開始 A が永遠に解けず、11:31 まで粘着する 諦めて B に行き、13:03 に解ける A に行って頑張るが解けないので、点数最大化のために C に行って、一瞬で部分点 12 点が取れたので、取る これが 13:41 残り全部 A に粘着したけど解けず 112点 破…

問題リンク 解説 辺 $(u, v)$ を反転させるとき、$(u, v)$ が消えて $(v, u)$ が追加される。 このとき、追加した辺を利用した最短距離は、先にダイクストラ法で前計算しておけば簡単に求められる。 しかし、辺が削除されることには対応できない。 辺が削除…