国際物理オリンピック日本代表候補に選抜されました。実感がありません。 第 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)$ が追加される。 このとき、追加した辺を利用した最短距離は、先にダイクストラ法で前計算しておけば簡単に求められる。 しかし、辺が削除されることには対応できない。 辺が削除…

問題リンク 解説 時系列順に数列の様子を並べると，同じ数でできた三角形や平行四辺形の集合になるので，これを頑張ってセグ木で再現する． 平行四辺形に差し引きすると直角二等辺三角形と長方形にできるので，これらの加算ができればよい． 長方形の加算は…

問題リンク 解説 小課題から消化していく． 小課題 1 愚直に実装すればよい．$O(N^2Q)$ で解ける． 小課題 2 すべてのペアについて探索すると，グリッド上での長方形内の最大を求める問題になる．2次元セグ木を書くと，$O(N^2+Q\log^2N)$ で解ける． 小課題 …

問題リンク 解説 木上の始点が根に固定されたパスについて， パス上の頂点の値を並べたときの転倒数を求める パス上の頂点の値をすべてある値に更新する という操作を繰り返し行う． すでに操作されたパスの部分パスが操作されることはない． さて，転倒数を…

問題リンク 解説 まず，濃さ $D$ のリンゴが入荷したら，配列の $[D, D+M]$ に $1$ 加算して，$N$ 個の出荷クエリが来た時は，配列のうちで $N$ 以上の最も右の値が取れれば良い． 出荷するべきリンゴは std::set などで容易に求められるので，出荷するとき…

問題リンク 解説 制約を見ると，時系列順に DP をしてやれば解けそうだが，ある社員が鍵を持っているかどうかの影響は，出た直後と戻る直前両方の時間に対して発生するので，時系列順に見るのは得策ではない． ある社員が鍵を持っていないとき，出た直後の区…

問題リンク 解説 答えを二分探索する． 答えを決め打ちすればその答えよりある貴族の踊りが上手いか下手かだけが問題になる． トーナメントのような表を描いて，「この位置にくる貴族の踊りが答えより 上手い/下手な 条件」を考えてやる． その子部分木で最…

問題リンク 解説 どのような移動が可能か考えると，「上り路線から，ある駅で下り路線に変えていくらか戻ったりスタンプを押したりして，またどこかの駅で上り路線に乗り直す」という動きの連鎖になることがわかる． 次のような DP ができる． $dp[i][j]=i$ …

問題リンク 解説 まず、$P$ 頂点のグラフを構築できれば、その中での経路のうち辺のコストの最大値の最小化をすればいいことになる。 このグラフ上でクラスカル法みたいなことをやれば、木上の問題になるのもすぐわかる。 さて、この木の構築方法だが、各建…

問題リンク 解説 bit DP くらいしか解けそうな方法がなくて困るが、制約を眺めると $D_i\leq 7$ になっている。つまり、一定以上に離れた位置にある小籠包を食べる順番は美味しさの総和に関係ない。 次のような DP をする。 $dp[i][j]=i$ 番目の小籠包を食べ…

問題リンク 解説 小課題は自明なので略 $Y_i=0$ の場合を考えると、トポロジカル順で DP をしてやれば解ける。 データ構造などで処理するのは難しそうなので、$Y_i$ に付随する計算量は、 $Y_i$ の定数倍もしくは小さい別の関数がかかった形にする必要がある…