問題リンク 解説 時系列順に数列の様子を並べると，同じ数でできた三角形や平行四辺形の集合になるので，これを頑張ってセグ木で再現する． 平行四辺形に差し引きすると直角二等辺三角形と長方形にできるので，これらの加算ができればよい． 長方形の加算は…
問題リンク 解説 小課題から消化していく． 小課題 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$ の定数倍もしくは小さい別の関数がかかった形にする必要がある…
久しぶりに良いパフォーマンスが出た A 問題 非自明すぎる $i$ から $max(i+1, i+\lfloor(N-i+1)/2\rfloor)$ に張ったらできました 証明はしてないので自分で $O(N^3)$ ジャッジを書きました B 問題 たぶん公式解説より簡単 $f(l,r,b)\ (0\leq l,r
Xmas Contest, 別にネタコンテストじゃなくてただの激ムズコンテストなんだよな… 参加の流れ 画像を交えて振り返っていく penguinman に誘われたので承諾した ゆるゆるやりたかったのでこのまま二人で出ることになる コンテスト中 A を解こうとしたが絶対解…
verification-helper で、oj-verify all をしても 10 分でタイムアウトして verification が終わらない問題が発生して、困る。 今回、自分のライブラリの verification が終わらなかったので、タイムアウトを設定して回避した。 .github/workflows/verify.ym…
問題リンク 解法 とりあえず問題概要を読むと、完全二分木を書くとよさそうなので書いて考察してみる。 頂点を文字列に対応づけると、根から $x$ までのパスに $y$ が含まれるか、$y$ までのパスに $x$ が含まれるようなすべての $y$ は、$x$ で表される文字…
問題リンク 普通に難しかったんだけど黄 diff 前半… AGC 苦手すぎる 解法 ロボットを $0$ に到達させない方法は大きく分けて二つある。 つぶす（他のロボットに踏ませて壊す） 縮める（ボールを書き換えて $1$ までしか到達しなくする） まず、このままつぶ…
問題リンク 解説 $[L_i, R_i]$ を反転させる操作を、「$L_i$ から $R_i+1$ に移動する」もしくは「$R_i+1$ から $L_i$ に移動する」と言い換えると、次の3つのうち最小値を求める問題になる。 $A$ から $A+B$ への距離 + $A+B+C$ から $A+B+C+D$ への距離 $A…
問題リンク 解説 長さを区間 $[x,2x)$ で区切ると、この中にある魚の部分集合は自由に選んで飼える。逆に、全部の魚の部分集合のうち飼うことのできるものを適当に選ぶと必ずこのような $x$ をとれる。 区間の種類数は高々 $O(N)$ で、尺取り法を使えば $O(N…
問題リンク 解説 まず、順位を決める対象となる国の成績が確定していなかった場合、その成績をどう決めるか考える。 これは、その国の成績とできる点数の最大値でない場合を考えると、これを最大値と交換しても決して損しないので、なるべく最大値を取れば良…
筑駒文化祭2020「彩雲」が終了した。 3-B クラスデコでうまく行った点や反省点を雑にまとめていきたいと思う。 脚本 3週間かけたのが明らかにミスだった。 自分含めた4人で相談しながら書いたが、コストの割にはクオリティの高い脚本にはならなかったと思う…
20位でした。賞品にはさすがに手が届かなそうだけど、やっぱり競技プログラミングは最高ですね〜〜〜〜〜！ A Keyboard はい B Futon B にしては難しくない？はい C Neq Min C にしては難しくない？std::set で殴るとよいです D Squares D にしては(ry $2(N-…
コンテストリンク 問題ごとに解説を書くのは面倒なのでコンテスト単位で書いてみる。 A Reachable Towns ある方向に遷移可能なら逆にも当然遷移可能なので、Union-Find Tree で管理したい気持ちになる。 ただ、張れる辺は明らかに $O(N^2)$ でしか抑えられな…
週記をやめて1週間坊主をしたが、続けてほしいと言われたので続けてみる。 2020/9/13(日) 木の直径を求めたり、DFS で距離を求めたりするライブラリを書いた以外の進捗が生えなかった。 Trie 木も書こうと思ったが時間がなかった。 ABC178 に出て 324 位だっ…
問題リンク 解法 全部黒にできる長方形は、行の集合を選んで flip すると、必ず各列の色がすべて同じになる。 これは、操作をいくら行っても変わらない性質である。 この判定には本来毎回 かかるが、適切な前計算で高速にできる。 具体的には、隣接2列の組に…
こたつがめさんを見習って週記を書き始める。 2020/8/23(日) 朝起きて鉄緑の校内模試（英語）に行く。朝から模試やめてくれ。 前日同級生と例文をひたすらテストするだけの通話をしていたが、勉強時間はそれを含めて 3 時間くらいだったので危機感を感じて、…
問題リンク 解法 出てくる目を分類してみると、 2つ以上選んではいけない目 ともに選んではいけないペア 制約のない目 の つに分かれる。 これらの出る数を決めて組み合わせを計算しようとすると、一回の計算で かかり、全体で となって間に合わない。 ここ…
問題リンク 解法 まで出力できるので、 より大きい数を出力して辞書順で候補を絞っていく。 と を見分けるには を出力すればいいので、辞書順で絞ったあと続く の個数を決定できる。 のような数が残った場合のみ場合分けが必要。 感想 簡単めだった
競プロ作問に関する Tipsです。 他にも、作問に関する記事は これ などたくさんありますが、一回まとめておきたいと思いました。 上の記事は多少参考にしました。 急いで書いたので雑でも許してください Writer のやること 原案作成 原案作成はそんなに気を…
問題リンク 解法 ちょっと考えると、撹乱順列を作るみたいな問題に帰着できる ただ、ただの撹乱順列ではダメで、途中でループを作ってはいけないので、撹乱順列をふたつくっつけたようなものはダメというのも、サンプルを見てるとわかる 基本的には最小値で…
APIO(アジア太平洋情報オリンピック)2020 インドネシア大会に参加しました コンテスト前 対策が2日前まで全然できてなかったので、本来5時間のコンテストを3時間のバーチャルコンテストで走るのをたくさんやりました 5時間あれば全部銅メダル取れたと思いま…
RBST を書いた. Kodaman 君の記事にお世話になった. ところで, あの記事どこにも "RBST" とか "Randomized Binary Search Tree" という文字列が入っていなくて, 検索しても出てこないのでどこかに書いたらいいと思う. これに限らないですが, 競プロ記事は欲…
