米 Starry Story EPの名前がめちゃくちゃ出ていますが、これは普通にハマってるだけです　あとリンク先はもれなくSpotifyです ちなみに競技終了当日とかに書いてるから記憶の捏造が少ない代わりにあとの展開がわかってなかったりします 0日目 表彰とか 銀賞ということでしばらく暇だった。後の方で賞の人たちといっしょに登壇することになった。 結構立たされた。祝辞とかしてたけどさっさと壇上から降ろしてくれ…

Algorithm (Typical) 想定点数はABC基準 問題 想定点数 おすすめ度 ひとこと Great Move 100

ついに念願の単著コンテストを作れたので作問記を書いておきます。例によって雑です。また問題のネタバレを盛大に含むのでまだ解いていない人はブラウザバック推奨。 いきさつ ARC182のwriterをしてからちょくちょく原案を提出していたらコンテストが開けるくらいにはたまったので作りました。writerの片割れのsounansyaさんがARC191のWriterだったのは全くの偶然です。びっくり。 各問題の感想 A - ARC Arc 原義カスのギャグ。どうしてもこの問題名を出したくて設定を考えた。シンプルながら $N\bmod 4=2$ のときがかなり非自明で好き。 解説放送の通り文字が円周上に置かれていてその間を1にするイメージだった。問題文を厳密に書こうとするとその部分は消えてしまったが…

はじめに この記事を書き始めたのはアピールの後だから具体的な時間なんも知らん！ （追記：UpSolveのときに見れたけどめんどいから書き足さん！） 本選中の記録 A まあ B

計算量的に嘘っぽいDPをするときのテクニック $1$ 選です。ただしこの $1$ は $10$ 進法とは限りません。 連想配列を使う メリット 実はこの添字が他の添字の内容から求められて～、みたいなときにその添字を残しても計算量を落とさずにできる使わない添字があるときは無意味なうえに連想配列で計算量が減らないことがあるので消す 実は有効な範囲だけ見ると計算量を削減できて～、みたいなときに実際に計算量を削減できる 遷移にもそういう制約があると無意味なのでそっちは真面目にやる

まさかの全問未履修。$3$ 問目は解けなかったのだが… $1$ 問目は特筆すべきところもないので略す。 Planar Tree ネタバレ防止用 種類数の少ないところから考える。 $1,2$ の $2$ 種類の場合、$N=2$ なら問題ない。$3\leq N$ のとき、$1,2$ を結ぶ適当な頂点を結ぶと、その両側にできた領域は両方とも $2$ 種類であり、帰納法が回って可能なことがわかる。

未履修が最終問題しかなかった。 Two Histograms ネタバレ防止用 はじめに、うまくいかなかった考察を供養しておく。 $0$ と $0$ の位置によって新たな $0$ が、$2$ と $2$ の位置によって新たな $2$ が決まる。また、$2$ の前に $0$ があってはいけないことがわかる。このように自明な条件をすべて満たしたものが実はすべて条件を満たすのではないか？大嘘。$N=3,M=3$ で、$((0,1,0),(1,1,1),(0,1,0))$ には自明に不可能な場所はないが実現不可。 $0$ や $2$ を置くと、いくつかの部分について候補が削れ、さらにそこを決めるとさらに候補が削れ…、のようなことができるが、これをDP的に高速化できないか？

乱択を使うまいとして考えた解法が公式解説とやや異なっていたため、私の解法を記す。ここで、多重辺は先に除去しておく。 選ぶ赤い星の集合を決めた時、青い星は明らかに選べるだけ選ぶのが最適である。 ここで、選ぶ赤い星の集合を補集合に取り替えてみる。このとき、選べる青い星の集合はどのように変化するだろうか？ 星をすべて選んだ時、奇数個の赤い星に隣り合っている青い星を明るい星と呼び、このような星を考える。明るい星は、選ぶ赤い星の集合を補集合にした時に選べるかどうかが入れ替わる。 逆に、偶数個の赤い星に隣り合っている青い星は暗い星と呼ぶ。暗い星は、選ぶ赤い星の集合を補集合にしても選べるかどうかは変わらない。

公式解説とは全然違う方法で解いていたので書き留めておく。 $$\lfloor \frac{k^2}{10000} \rfloor=n \iff \lceil 100\sqrt{n}\rceil\leq k\lt \lceil 100\sqrt{n+1}\rceil (0\leq n)$$ であるから、 $$ \begin{eqnarray} \sum_{k=1}^{10000}\lfloor \frac{k^2}{10000} \rfloor &=& 10000+\sum_{k=0}^{9999}k(\lceil 100\sqrt{k+1}\rceil-\lceil 100\sqrt{k}\rceil)\ &=&10000+9999\lceil 100\sqrt{10000}\rceil-\sum_{k=1}^{9999}\lceil 100\sqrt{k}\rceil\

公式解説と本質的には変わらないだろうが、数学初心者の競プロerなりに考えた方法を書き留めておく。私はこちらの方が考えやすかった。 A と B を 0 に、C を 1 に置き換えた文字列を考える。たとえば、ACBAC は 01001 となる。定義より、0 が隣り合うことがあっても、1 が隣り合うことはない。 このようにしたとき、操作は以下のように置き換えられる。 0 と 1 の間には、0 を挿入する。 1 と 0 の間には、0 を挿入する。 0 と 0 の間には、1 を挿入する。

例によって全問題を見る。インタラクティブ2問なのが怖そうだが、唯一のBatchであるbooksはがんばればいけそうな気がしてくる。正直OIのこういう系の問題はかなり苦手なのだが、そんなことを考えていても仕方ないので考察を始めた。 暫く考え進めるうちに、サイクルをいい感じにつなげばいいらしい。ひとつのサイクルを処理するとき、その区間内にあるやつはコストを増やさずについでに処理できるのだが、外にあるやつはその距離ぶんだけ出張しないといけない。というわけで区間のマージでよさそうな気がして実装するが、実装途中でグループがaabbaaみたいに分かれていてかつ b からはじまるとやばそうということがわかった。ついでに謎だった $s=0$ の意味も理解できて、$s=0$ ならこういうことがないらしい。確認のため、実装しきって提出すると案の定50点が返ってきた。それはそう。 ここからセグ木を持ち出していい感じにやれば満点が取れそうな気がしたが、実装していくうちにだんだん細部を詰めるのがやばそうな気がしてくる。提出してバグを取ってを繰りかえし、ここで2時間くらいを徒に浪費してしまった。 しばらくして、やっていることがそもそも間違っていることに気付いた。さっきみたいなやつのもっとも外側に出れればあとは $s=0$ と同じことをすればよくて、結局ダイクストラ法みたいなことをすればいいだけであった。実装して漸く満点が帰り、安堵のようなものを覚えた。ここまでで2時間半ほど。 prizeとsimurghのどちらを考えるかは迷わなかった。prizeの部分点をよく見ると、なんかクエリの数を減らさずに90点が取れ、そこからはかなり頑張らないと100点にはならないみたいなことが書いてあった。90点だけ取ってsimurghに行こうと考えた。

初めて日本に関係ないOIを触った。 例によって全問題を見る。abracadabraとprizeはかなり苦しい気持ちになるが、それに紛れてなんか実家がいる気がした。homeworkをよく見ると、構文解析してDPするだけ。構文解析は前回書いて自信があるので、とりあえず凸った。 特筆すべきところもなく、普通に40分くらいで通った。しかし、ここからはとても苦しかった。 abracadabraもprizeも本当にわからない。Aに至っては10点の小課題すら自明でない。本当にやばい。 prizeの小課題1は自明だが、実装がつらい。それ以降は本当にわからない。本当にまずい。

まず全問題を見る。見た瞬間にExamination2の解法を完全に理解したが、木に対する高度なデータ構造と構文解析が必要になり、絶望する。とはいえほかの問題はよくわからないので実装することにした。 構文解析もうまく計算量を落とすのが難しかった。結果的にNlogNになったが、線形時間の方法はあるのだろうか。実装するうちに、セグ木とHL分解でやればよさそうに感じたが、これだとlogが2つになる。TLが2秒で怖かったが、C++を信じて実装すると少しバグったが通った。ここでHL分解を空書きできたのは偉かったと思う。ここまでで2時間ほど。 Library3を見る。クエリで得れるのはFunctional Graphの連結成分の数っぽい。そう考えるとN<=100は自明で、すぐにとることができた。N<=500はわからずHeatに移る。 C=1がそこそこおいしそうなので考えると、区間DPが思いついた。実装もそんなに重くなく、割と簡単に通すことができた。その勢いで小課題1もゲット。 ここで私は選択を迫られる。HeatのCが大きい解法を考えるか、Library3のN<=500を考えるか。私はLibrary3の方を選んだ。

もう1,2週間前の話ではあるが、IOIに向けた練習をはじめた。QOJのコンテストサイトを見ればわかる通り、集団的にやっているがそれはそれとして。 IOI18を両方走った。私は取れる部分点をすべて集める、堅実な立ち回りといえるものを好んでいる。実際、これで失敗したのはJOIspのDay3とAPIOくらいだろう。APIOは取れる部分点を堅実に集めたらshowが全人類に解かれていて終わったのでかなりトラウマだが、それはまた別のお話。 ということで、今回もその戦略で走った。コンテスト中の立ち回りとその反省をまとめる。 Day1 問題を見る。精進中に簡単枠であることを知ってしまったCombo君がさりげなくいるが、とりあえず全問を見る。たぶん知らなくてもComboから挑むであろうセットだったからセーフということで… 真面目に考える。初手の文字をとりあえず2回の質問で特定すれば、あとは2N回くらいで特定できそう。まあそれではだめで、もっと改善しないといけない。乱択とかを考えたが通る確率がすさまじく低そうなものしか思いつかず、そういえば4N文字使えるなあ、今2N文字くらいしか使ってないなあとか考えていたら生えた。Aが最初の文字だとして、B,XB,XX,XYをつけて質問すればよい。最後の文字を決めるときだけ困るが、ちょっとだけ余裕があったので2回質問すればよし。普通に実装も楽で、簡単に満点が取れた。