久しぶりに良いパフォーマンスが出た 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" という文字列が入っていなくて, 検索しても出てこないのでどこかに書いたらいいと思う. これに限らないですが, 競プロ記事は欲…

問題リンク 問題概要 回にわたって整数 が与えられる。 を満たす整数 の組で、Euclid の互除法を走らせた時の反復回数の最大値と、それを導く組の個数を求めよ。 解法 まず、最大値を求めることを考える。回数ごとに組の最小値を貪欲に考えていくと、フィボ…

問題リンク 解説 求めるべき長方形がどのような形をしているか考えてみます。 題意より、求める長方形は3頂点が異なる色で、残りの1頂点は残りのどれかと同じ色です。 このような長方形には、3頂点が異なる色になるL字型の部分が必ず2つ含まれています。 よ…

問題リンク 解説 それぞれのジャンルごとに売る冊数を決めたとき、ジャンルごとの価格の最大値は明らかです。価格の高いものから貪欲に売るのが明らかに最適であるからです。 これを先に求めれば、ジャンルごとに売る冊数を適切に決めるだけで価格の最大値が…

問題リンク 解説 動的計画法を適切に高速化する問題です。 を、 番目の階段に来る方法の総数とします。 を求めるとき、どこの階段からここまで上ってこられるかを考える。これは、尺取り法や二分探索を使えば高速に求められます。 そのような段のうち最も低…

問題リンク 解説 初歩的な動的計画法の問題です。 を、 行目かつ 列目のマスにいる状態とし、残り2つの添字で「どちらの方向から来たか、次に曲がれるか」を保持します。 この動的計画法を と の昇順で回すことで解けます。 このように、典型的な動的計画法…

問題リンク 典型寄せ集めみたいな問題 解説 まず、道の本数が高々 本なので、作れる道を列挙できれば、クラスカル法で空港の数と道のコストの組を計算できる。 空港の建設コストは会社ごとに異なるので、これを変数だと考えると、上に挙げた組は一次関数にな…

Li Chao Tree を書いた. 一次関数 の追加と, での取る値の最小値の取得が、取得したい点の集合のサイズを としてそれぞれ になるデータ構造. 使い道 最適化DPの遷移でこういう式が出てくることがあって, これで高速化ができることがある. JOI で出ることもあ…

問題リンク 解法 重要な考察がいくつかある すべてのテストの重要度は のどちらかである。これは、 どんな場合でも損失を最小化/得を最大化するのはこの2つの値のどちらかになるからである。 時間勉強するとき、その内訳は、重要度が で 時間勉強する教科、…

問題リンク 解法 先頭に追加していって辞書順最小を目指すので、操作を後ろから考える。 数列のうち、使っていない数でできた連続区間の長さがすべて偶数となるように、同じ連続区間からふたつの数を取っていけばよいということがわかる。 問題は、1個目に取…

問題リンク 解法 前からDPしていく. 2以上の要素が2連続するとそこから先はすべて埋まり、そうでない場合1を置くか、2以上の要素を置いた後十分になるまで1で埋めるしかない。 これを考えると、 を、「 要素目以降がまだ決定していない場合の数」としてDPが…