東京大学一般選抜不合格記

ペーパーテストでこういうことをしてはいけない、をいっぱい書いていきます。

day1

国語

順当に現代文をやって、順当に漢文をやって、順当に古文をやった。
漢文、漢詩だったが文章の位置を見間違えてできる推測を一個ミスったのが悔しい。
国語の時間配分
現代文80分
古文eps分
漢文20分
古文ができない人間にとっては正当な戦略ですが、そもそも古文ができないのがダメです。

数学

開いてみて、2,6がCNだったので、2->6と解いて、その後他を考えることを決定。
2が自明すぎて、今年の東大数学はゲロ簡単なのか？と思って渋い顔をする。
2を検算こみで30分くらい、6を30分ちょっとで完答。
この時点で、2は簡単だし、6は質が低い(一般に簡単かは知らないが、少なくとも質は低いだろうと思った)と思ったので、今年の東大数学は簡単で質が低い感じか、と思った。(ため、時間かけすぎだとちょっと焦っていたが、最悪5完でも問題ないだろうと思っていた)
しかし1をやってみると(1)で-1 \leq \theta \leq 1であることを忘れたため、(2)が不可能問題となり、いくら粘っても解けなくて焦り始める。
諦めて3をやってみると(2)で(a-3)^2+b^2=4かつax+by=a^2+b^2なる(a,b) \in \mathbb{R}^2が存在することが条件だとわかり(嘘で端点(?)を除かなきゃいけないですが気にしないでください)、とりあえず包絡線でできると思ったが、なぜか実行せずどうやって文字を消そうかとクネクネしまくる(ここで、二つ目の式からa^2+b^2を消すとうまくいくことに気づけてないあたり腰がもう据えられてない)
時間がまずいので5に行ってみると、5(1)は当然解けるものの、(2)で誤読をかまし(めちゃくちゃ冷静になれば面積が無限になるが)、誤読に気づけずわからない問題に時間を浪費
最後時間がない中で焦って4を見て、(1)でとりあえず加法定理を書いてみたところで、加法定理がはずれ方針であることに気づくも、頭を壊して間違った解答をする(冷静になれば、雑に指定した範囲内の確認が簡単な点で確認すれば自明だったのだが)
最後3(2)の包絡線が双曲線になるのはわかってたことなので(?)、お絵描きだけ描いておく(ちゃんと点や曲線を明示するのに失敗)

day2

理科

前日レンズの出題予想の話をしていたので、物理開いた時レンズが見えてちょっとおもろって思う。
物理→化学の順に解いた
序盤はなんとなく不安だったので物理の記述をちょっと書いたが、別に無意味だしだるいという気持ちになったので力学の途中以降やめた。力学は最後から2番目の問題を方程式をミスることによってミスし、最後もしゃばい記述を書いた。
電磁気は簡単だったのだが、ちょっと怖くなってめちゃくちゃ丁寧に計算をした(が、時間をかけすぎでだめ)
この時点で力学電磁気どっちも30ずつくらい使ってて非常によろしくなくて、波動でちょっとスピードを上げるも、最後ボケの大きさの定義がどこに書いてあるかわからず、代入するだけらしい問題3つを落とす。(20分)
ここで物理は80分くらいなので、まあ想定されていたくらいの時間。
化学を解き始めると、全て選べが結構多く、困ってしまう。全て選べでクネクネしていると、時間があかんことになってしまい、無機はほぼ捨てて有機をやるも、有機も全て選べでクネクネして終了。(全て選べ、知識に自信がないためにクネクネしたり、余計な選択肢を選んだり選ばなかったりするという行動をとってしまうので、知識をつけよう)

英語

色々形式が変わっていてびっくり。2Aは一回書いた後、なんか違うなと思って書き直したが、正直どっちでも内容が微妙な気がしている。普通に一発で文法ミスなくかくとを最優先すればいいんだけれども。文法ミスは信じるしかないので、信じた。2Bは簡単だったが、もっとうまくできたなあとは思った(周りの英文に必要な単語が載っているので)。
普段2A->2B->4Bの順にやっているので、4Bをやると、(イ)が完全に意味不明文章でお困り。そもそも下線部分が長いのもあり、(ア)を意味わからない部分を適当に補完しながら書いて(ちなみに、予備校が出してる模範解答的には補完しなくていいらしく、普通に直訳をしまくればいい説がある)、(イ)(ウ)を途中まで書いてクネクネしてたらリスニングが始まる。リスニングは、いくつか選択肢が奇妙(?)だが、とりあえず順当に終わる。とりあえず4Bを眺めながら1Bをやった(1,3が結構迷う選択肢で困った(外した))。
次に1Aをやってみると、後半が完全に意味不明なので(結局フロイトがすごいということしか言ってなくね？)、頑張って適当に書くと、4Bイウと5を残して20分しか残ってない！(4Aは存在しないものとして扱います。)
とりあえず、とにかく書こうと4Bを無理やり書いて、残り10分弱で5をやって、間に合わない部分は勘で埋めた(うーん)。

Olympiad in Informaticsとのお別れ

『そっか、そっか……、こうすれば通ってたんだ……、どうしてちゃんと考えなかったんだろう……、どうして気がつかなかったんだろう……、悔しい、悔しいよぉ……、もっと精進すればよかった、もっともっと他に何も考えられないくらい競プロのことを考えなくちゃいけなかったのに……』
- @rian_tkb

何か自分が多少なりとも情熱を注いだもので、ラストチャンスの何かをするというのは自分にとって初めての経験でした。このような経験をする機会は人生の中でもそう多くないと思いますし、その中で失敗するのも貴重な経験だと思います。

自分のOIとの出会いは、自分が中学に入学した年に、いわゆるパソコン部に入って一次予選に出させられたところにありました。最初は、本当にただ出ただけで、競プロと向き合ってもいなければ、向き合い方も知らないという感じでした。松尾凛太郎(QCFium)っていうすごい先輩がいるんだなぁくらいにしか思ってなかったとおもいます(始業式とか終業式とかで生徒の活動実績みたいなのは紹介されるので、これだけは明確に認識していました)。競プロと向き合うきっかけは、やはり同期の競プロerが多くいるSimploというDiscordサーバーで会話するようになったことでしょう。中1の3月くらいからコンテストに出続けると言うことを覚え、そして次第に精進することを覚えていったと思います。競プロに熱意を注いでいく中で、自分がOI系統の問題が苦手意識を持ち始め、少し好きになれないような感覚がありましたが、やはり自分も一中高生であり、自分が意識するものとして、情報オリンピックは自分にとっての競プロの核の一つであり続けました。過去問は多く解いてないですが、自身のOI人生が終わった喪失感から、OIは自分にとって大切なものだったんだなということがよくわかります。しかし、OIを失ったからといって、これで競プロを辞めるつもりはないわけなので、この失敗も後にただの思い出話にできるように、自分の失敗をここで学んで前進したいと思っています。

これからがある人たちに向けて失敗した人なりのアドバイスをします。

落ち着かないときはいっぱい飲み物を飲んで、食べ物を食べると落ち着くことがあります。また、腹式呼吸も有効な場合があります。まずは焦りの仕草を身体に出さないところから始めるのが良いです。プレッシャーを感じていつも通りの行動ができないという問題は、常に自分のことを客観的に捉えれるようになった上での別の問題として存在していて、術というものを時間をかけて身につけるしかないのです。

JOIは時間が長いから順当になんとかなるもののように見えて、実装の重さや詰めの難しさが原因で一個の問題にハマりやすいものなので、ちゃんと一度問題を見渡し切って十分に全ての問題と向き合うことが重要だと思います。春合宿は本選よりこの傾向が強く、自分は一度春合宿を経験していますが、これはOIにおける最大の難点にして最重要課題だと感じました。

本選競技

あまり書くことはないです。有権者レート9位(？)だったので、まさか本選で足を掬われるとは思ってもみませんでした(というと流石に嘘な気がします)。

15分経過くらい　B　AC

30分経過くらい　A AC

Dで一回大嘘フローを書く。馬鹿

最小パス被覆で連続するラベルの頂点は両方消しちゃダメというところまで考察を戻す。

Dilworthの定理からLDSなのは気づかなかったが、最小パス被覆を得る貪欲アルゴリズムは構成できたので状態数N*2^max(A),遷移O(1)のdpで46点を取れることがわかったが、すぐ状態数が2^max(A)のdpに落とせることがわかったので、考察を続行するも、思いつかなかったのでここで72点くると信じて(実測上は早いはずなので)状態数2^max(A)のdpを書き始める(どれくらい時間経過してたか覚えてない)。書き終わってサンプル試したりコードを提出したりしてみたが、WAだったり、REだったりで大変。これがずっとうまくいかないままラスト1時間をの時点を迎えて、かなり落ち着けなくなってしまいました(終了1時間前よりも少し前からそんな感じだった気がします)。だいぶストレスを感じてたと思います。紅茶を飲んで、お菓子を食べて腹式呼吸をして、しばらくしたらようやく落ち着いたと思います。そこから少しして、多分終了40分前くらいにようやくDの72点が通ります。そこから少ししてから2^max(A) log(N)にできたつもりになって、それをやりながらC問題とE問題の部分点を全部中途半端に手をつけるという行動に出てしまい、結局何もまともに点が取れず282点。まさかCが簡単だとは思っていませんでしたが、ちょっと落ちていそうという感触はありました。そして、C問題が簡単だったとわかるとともに、ああ、終わったんだなという喪失感が襲ってきました。そんなことはないだろうと思っていた失敗をしてショックではありましたが、最初に湧いてきた感情は悲しみではなく、どこか自分がここにいないような感覚になりました。これが自分の最後だと認識するとともにようやく悲しくなってきて、でも同時に開き直ったような気がします。

さいごに

これからも人生をがんがります。

無駄にラグランジュの反転公式を使うとよくわからない等式が生えてきたりする、こともある。

次の様な問題を考えましょう。

  • 長さ2nの01列 "11...1"に対して"11"を"00"にしたり、"00"を"11"にしたりすることが0回以上できるとき、作ることができる01列の個数は？

解法1 : 奇数番目の01を反転します。すると、"0101....01"に対して"01"を"10"にしたり"10"を"01"にしたりする操作になり、つまるところswapができるので"0"がn個、"1"がn個ある01列全てが生成できる文字列であることがわかり、\displaystyle\binom{2n}{n}が答えだとわかります。

解法2 : 生成できる様な文字列のうち、分割してしまうと生成できる文字列で無くなってしまうような文字列を既約な文字列と呼ぶことにします。生成できる文字列はこの既約な文字列の連接として一意に表すことができるので、既約な文字列の母関数をf、生成できる文字列の母関数をgとするとg=\displaystyle\frac{1}{1-f}と表せます。ここで、既約な文字列について、両端の文字は同じであり、構造として"a(両端がaでない既約な文字列の連接)a"という構造を持つため、f=2hを満たすような母関数hをとると、\displaystyle h=\frac{x}{1-h} \Leftrightarrow h(1-h)=xという方程式が成り立ちます。ここで方程式を解いて直接gを求めないことが肝です。ラグランジュの反転公式より、\displaystyle[x^n]g=\frac{2}{n}[x^{n-1}]\frac{1}{(1-2x)^2(1-x)^n}という等式が成り立ち、実際に二項定理を用いて展開してみると\displaystyle[x^n]g=\displaystyle\frac{1}{n} \sum_{k=0}^{n-1} (k+1)2^{k+1}\binom{2n-2-k}{n-1}です。

解法1と合わせると、\displaystyle\sum_{k=0}^{n-1} (k+1)2^{k+1}\binom{2n-2-k}{n-1}=n\binom{2n}{n}とわかります。自分にとってはこれは結構びっくりで、知らない等式の登場でした。ところで、解法1を利用しなくても、ちゃんとhについての方程式を解いて、代入してgを求めることによりg=\displaystyle\frac{1}{\sqrt{1-4x}}から\displaystyle[x^n]g=\binom{2n}{n}を得たり、実はラグランジュの反転公式で導いた\displaystyle[x^n]g=\frac{2}{n}[x^{n-1}]\frac{1}{(1-2x)^2(1-x)^n}という等式から、\displaystyle[x^{n-1}]\frac{1}{(1-2x)^2(1-x)^n}を\displaystyle\frac{x(1-x)}{(1-2x)^2(1-x-y)}の対角としてみることによって[x^n]g=\displaystyle\binom{2n}{n}と導いたりすることができます。


\displaystyle[x^{n-1}]\frac{1}{(1-2x)^2(1-x)^n}を\displaystyle[x^{n-1}y^n]\frac{1}{(1-2x)^2(1-\frac{y}{1-x})}=[x^ny^n]\frac{x(1-x)}{(1-2x)^2(1-x-y)}とみることにより計算する方法以外で計算方法が思い付いた人は私に教えてくれると嬉しいです。TwitterでDMするなりメンションでもしてください。

\displaystyle\sum_{k=0}^{n-1} (k+1)2^{k+1}\binom{2n-2-k}{n-1}=n\binom{2n}{n}の組合せ解釈についても募集しておきます。

(追記: この等式を得る別の方法として、母関数を計算しにいき、Σを交換することによってn \binom{2n}{n}の母関数を得ることができました(式変形典型を忘れており、恥ずかしい....))
(追記2: 両辺をnで割って、n \times nのグリッドのパスと解釈する。左辺が、kごとに、対角線にk+1回触れるような経路の個数になっており、この和は確かに右辺と一致する - 37zigenさん (https://x.com/37zigen/status/1923065268957299039))

JOI予選アドバイス

例年通りなら300点くらい取れれば通ります。300点がどれくらいのラインかっていうと、競プロ典型90問の☆4〜5が解けるくらいだと思います。今から全部解いてくればほぼ確実に通るので今から解いてください。
人々が解いた結果予選突破の難易度が上がってしまった場合は知りません。

真面目な話をすると、わかんなくても部分点を全部潰すみたいな気持ちになってると結構点数が盛れたりします。盛りましょう。あと典型を唱えると良いことが知られています。

ABC209-F Deforestation O(N log^2 N)解

atcoder.jp
がO(N \log^2 N)で解けるよという話です。特に何か面白いと言ったことはなくて、ただの土木ですが、一応。

必要十分条件は
各i=1,2,\dots,N-1について
・H_i < H_{i+1}ならP_i > P_{i+1}
・H_i > H_{i+1}ならP_i < P_{i+1}
となっていることです。

ここで、H_i = H_{i+1}であるようなiについてi,i+1で区切って、それぞれの列について問題を解いてからその積に適切な多項係数をかければよいことを考えると、結局各iについてP_i > P_{i+1}またはP_i < P_{i+1}という条件が設定されていて、その条件を満たすような順列を数え上げれば良いです。これはEDPC-Tなわけですが、これは包除原理を考えると、分割統治+FFTでO(N \log^2 N)で解くことができます。
詳しくは、Nachiaさんの裏EDPCなどを参照してください :

www.mathenachia.blog

実装例だけ載せておきます:

atcoder.jp

JOI2023/2024本選参加記

2024/1/28,2/4に開催されたJOI 2023/2024本選に参加しました。その参加記です。

2/3以前

今年のJOIの自己紹介動画はなんか期限が去年よりもかなり早く設定されていて、今年は同学年の競プロerでやる新年会でロシアンたこ焼きやるのでは間に合わなくて、ネタに困ってしまった。ずるずる引きずってたらついに期限の大晦日になってしまった。家の事情で忘年会に行っていて、普通に諦めて夏撮った自分の写真に言葉を添えて提出した。

本選競技については、今年は春合宿に行きたいと思っていたのだけれども、普段からJOIサボる人はずっとサボるらしく、結局本選競技の週になってようやくJOIの過去問に触り始めた。でも結局触ったものといえば、去年の本選と一昨年の本選だけで、結局数問しか追加では解いてなくて、JOI本選には
難易度7 : 8/51 AC
難易度8 : 3/33 AC
難易度9 : 4/60 AC
難易度10 : 1/48 AC
難易度11 : 0/59 AC
難易度12 : 1/41 AC
という悲惨な状況で挑んだ。

海外OIも、同学年の競プロer数人でバチャで手をつけようとしたが、自分は通した人に解法は正しいと言われたのに、実装が下手すぎて永遠に通せなくて、萎えて結局1問も解けていない。2/3にtatyamさんがJOI本選模擬を立ててくれていたが、自分はちょうどその時間にUniversal Cupをしおむすびと走っていた(途中で17も合流した)ので出れず、結局本選当日も起きてもJOIの過去問すら全然できてないのに海外OIを触る気持ちにはなれなくてぼーっと今年の二次予選の問題を眺めていた。

1/28 開会式/交流会

開会式、せっかくの開会式ではあるのだけれどもなんかその時間帯は鬱になっていたのか、全く開会式の映像を見る気が起きず、JOIの過去問をぼーっと眺めていた。

夜は双子によるチューター企画/交流会があって、今年もヒューリスティックなのかなあと絶望していたところ(ヒューリスティックが全くできないため)、今年のチューター企画は、10問の暗号化された問題文から問題文を復元してその問題に答えるというのをはや解きするというものだったので救われた。チューター企画のチームメイトはhiikunZとかめで、チームメイトが強くて色々上手く行って、結果としては最速提出でunique全巻できて、自分のチーム的にはアツかった。hiikunZとかめありがとう！

チューター企画後、DiscordのVCでGartic Phoneをやったのだけれども、今まで見たことのない人数が通話に入ってるのを見て、少しビビった。

2/3

Universal Cupに出るところまでは上に書いた。21:00からABCに出た。全完したのだがパフォーマンスが黄色ギリギリで順位も300+で、どういうこと？になってしまった。問題は配点の割に簡単だったし、どうやらEは既出でGはLibrary Checkerから貼れば解決したらしい。Eの既出は、覚えてなくてもまあありうる話だったが、Gを解くときLibrary Checkerの存在が完全に頭から抜けていて、それはまずいですねという感じ。そんなこんなでGは永続セグ木で解く問題に見えたので、永続セグ木で解いた。Fで大変なことになった結果、全完が遅くなる+ペナがいっぱいつくなどでこんな感じに。

2/4

ABC後、通話で虚無のABCの話は終えて、kemuniku鯖でBGAでアグリコラをしてる人たちに合流し、自分は一回オリフラムをして寝たが、時間が1:30くらいをまわっていて、起床が少し心配だった。無事10時前に起きると、それから朝ご飯食べるなど支度をしてJOIの過去問を眺めていた。本選開始直前にAtCoderのコードテストが不穏な動きを見せて、これは愛しのpaiza.ioの出番か？と思いきや復活したのでAtCoderのコードテストで行くことにする。ヤシの実サイダーを用意して競技に臨んだ。(ちなみに適当に手に取ったヤシの実サイダーは御坂美琴缶だった 。きっと味方してくれるだろうと信じて競技に臨んだ。)

競技パート

とりあえずkaichou243伝統芸能の問題順を無視して解くをやろうと思っていて、まずB問題を開いた。割といつもので少し心が落ち着いた。満点解法を実装して提出。(13:10, 合計100点)
一旦A問題をやろうかと思って見てみると、ぱっと見わからなくて結構ビビる、最大値の最小化なので二分探索か？とか血迷って言い始めたけど、冷静さをなんとか取り戻して全然そうじゃないことに気づき、満点解法を実装して提出したが、一回実装ミスをして満点が取れず、A問題にして2回もビビる羽目に。実装ミスに気づいて直して提出。(13:30, 合計200点)
次にDを読んでみると、完全マッチングの判定をすることを要求されていることがわかり、一旦Dに粘着する気分になる。絶対Hallの定理だなと思いつつも、一旦興味本位で適当に書いた嘘貪欲を投げてみると落ちた。それはそう。Hall条件を書き出して一旦そのままをコードに起こして50点を獲得。(時間不明, 合計250点)
絶対その先の小課題や満点解法へのキーは掴んでいるはずなので、このまま粘着してより高い点数を狙おうとして、少し考察して条件を整理すると一個次の8点課題が定数倍が厳しそうだがMo's algorithm + lazy seg treeでできるかなと思い、かなり時間をかけて実装するもTLEだったので、かなり参った。(15:00くらい)
流石にちょっとまずいと思って、定数倍高速化を試みるかと思いコードと睨めっこするが、全然ダメで結局一旦撤退する。(15:30)
急いで小課題だけ回収しようと思い、パッと見えたCの24点コードを提出。(時間不明, 合計274点)
かなり焦っていて、Cの続きが全然見えなくて、一旦Eに移るとなんかとりあえずいつもので16点が取れそうなので、コードを書いて提出。(時間不明, 合計290点)
Eの続きも見えず、やっぱりDに粘着しようと思い、定数倍高速化でやり損ねた、std::set→64分木とlazy seg tree→starry sky treeの書き換えをやり損ねていたことに気づいて、大急ぎで両方書いてみるんだけど、ダメだった。もう終了間際で、あまりできることがなかったので、一旦Mo's + lazy seg treeを捨てるつもりになって考察を巻き戻して終了後にでも解法を理解するつもりになって考察を始めたところで終了。

終わった後、自分が取った部分点から考えて290点だと結構怪しい気がしていて、春合宿落ちたかもしれんと思って本当に怖かったが、Cyanmondに通りそうと言われたのできっと大丈夫だろうと信じ始める。お祈り。

終了後Dをかなり考えても、Mo's + lazy seg treeよりまともな計算量の解法が全然生えなくて、だけど満点を取った人たちと同じ条件を考えているので方針は間違ってないらしくて困った.... 典型練習不足。結局Dは理解したが、50点止まりだったのが本当に情けなかった。Cも後でしばらく考えてみるとともういくつかの小課題が見えて、本当にDの8点課題でMo's + lazy seg treeをしようとしていたのが時間の無駄だったなと感じた。反省。

一つ思うことがあるとすれば、本選競技中に4回もトイレに駆け込んでいて、本当に何？みたいな気持ちだった。

2/5

去年に倣えばこの日の午前中に成績優秀者発表があるので、朝からかなりそわそわしていた。
学校に行って、1限が始まろうとしていた時TwitterでtatyamさんがJOIボーダーが載ってるリンクを貼っていて、見てみるとJOI春合宿通ってるぽくてよかった。本当によかった。

総評

もちろん春合宿通れたのは嬉しかったが、本選競技はやり残したことがいっぱいあるように感じられて、悔しい。
しっかり精進して春合宿では成功したい。
今年はzhoukangyangがIOIに来るらしいので、なかなかに厳しいが今年IOI日本代表になりたいものだ。

ABC221-H Counting Multiset ヤング図形で考察する

atcoder.jp
を解きたいです。整数の分割の数え上げですね。問題の条件を満たす整数の分割に対し、ヤング図形の転置を考えると、以下の条件を満たす整数Nの分割(\lambda_1,\lambda_2,\dots,\lambda_l) \ (\lambda_1 \geq \lambda_2 \geq \dots)の数え上げになります。
・\lambda_1=k
・\lambda_i-\lambda_{i+1} \leq M
これの数え上げはdp[i][j] := \lambdaの総和がi,\lambda_1=jとして解くことができます。明らかな漸化式から累積和dpを導出することもできますが、\lambda_1=j-1である分割をとり\lambda_1をjに書き換えることを考えると、\lambda_2=j-M-1であるようなものを余分に数えていて、逆にこれを除けば\lambda_1=jかつ\lambda_2 \neq jであるような分割を全て数えられているので、漸化式
dp[i][j]=dp[i-1][j-1]-dp[i-j][j-M-1]+dp[i-j][j]
を得ることができ、累積和なしでも解けます。(上記の漸化式は、noshiさんのユーザー解説やkanpurinさんのユーザー解説に載っているものと同じです)