こんにちは、Yoyoyo8128です。
AtCoderは黄色です。
JOI2025/2026のセミファイナルステージで
100-100-100-31-68-0を取り、初の春合宿進出をしました。
本当にうれしい
結構競技以外のことが多そう、あと競技は割と解けたE問題を多く書いています。
1年前(背景知識)
2025より前の3年は部分点ゲー(Cで70とか取ると通りガチ？)でした。
JOI2024/2025本選は
AとBが自明、DがbitDPだけで46点取れるのに難易度11、Eは毎度恒例難易度12というABDEで差がつかなさそうなセットでした。
ここでCのミ・テレフェリコという問題がなんとJOI本選のCでは異例の難易度9でした。この問題は3つくらいの問題に分けられるのですが、その中でも1番簡単な部分問題を思いつかず結果は合計297点(100の倍数は満点と自明部分点を取ったり取らなかったりで人数が増えガチなのでそれに勝てないのは順位が悪くなりがち)
この出来事をまとめてテレフェリコと呼びます
2次予選
A 流石に自明
B 未証明の貪欲(w)3,4,5の団子とかが許されないのやばい、僕はA~Dの中では最難関だと思う、Eとは同じくらい
C JOIではない！！！JとOIの塊に分けてsort
D 三分探索して二分探索累積和 やるだけ 三分探索いらんのはわかってたのにやったのはなんで？
E 僕の方針だといい問題だと思った、偶数回で繋がるとこをUFで管理してあと1回でいけるとこを全列挙
別に超頂点でいいらしくよく考えたらそうであんまおもしろくない
F 偶数の時、exchange argument?により、ペアが自明、3以上を含むメリットはない
奇数の時、まず3のペアを作ればあとは偶数に帰着できる
2乗が通るので3の等比数列を全列挙して、そのあとは偶数の問題を解くだけで、それは00,01,02,03,11,12,13,22,23,24,34のセグ木を持つ(00,01,02,03だけでもよかったなぁ)とできる
実装重かった
嘘で通してた人間が多くて苦しい、僕嘘を考えないガチ(きっちりと証明するガチ)なので嘘が通るテストケースはかなり不利、某高3、競技に戻ってきてくれ
セミファイナル前日まで
すごい精神状態でここでは言えないようなこともしていました、、、
関係ないですが、授業はきちんと受けましょう。学校にはちゃんと行きましょう。
マジで、ずっと緊張してました。精進もマジでたくさんしてました。
セミファイナル当日
競技前
新橋に行く電車では、メダリストというアニメを見ていました。割と競プロと重ねてみてしまい、普通に電車内で泣いてしまった。これが今日1番の泣きでよかった。。。
11:00開店のラーメンを食べたいと思ったので、11:00に新橋に到着しました。←？？？？
なぜか(本当になぜか)知り合いにでんちゃオタクが多いので新橋のシンボルの蒸気機関車を使って撮り鉄ごっこをしていました。何をしてるんだろう？
本選鯖を見たら人が居そうなのでちょっと話してみました。普通にラーメン屋に早くいかなきゃいけなかったので自己紹介だけして割と一瞬で抜けちゃいました。暖色ということでおぉって雰囲気になったので、春に行くという決意表明をしました。これも割と謎行動、ラーメン屋に早くいかなきゃいけないのに
ラーメン谷瀬家に着きました。highlighterが先に並んでいて、akinyanとhirayuu_Atが出てくるとこでした。ラーメン屋の店主さんの気遣いのおかげで先に入ったhighlighterの隣の席で食えました。僕が固め、彼が普通だったこともあり提供時間が僕の固めラーメンの方が早かったので同時に店を出ました。
aさんっぽい人がいるなぁって思いながら僕は目を合わせてみました。違う人かもしれないので話しかけませんでした。これ僕の流儀です
おやつをコンビニで買って、「5円にご縁を」をしてきました。
寄り道をしたりしていたらTKPカンファレンスにつく頃にaさんと合流しました。あっちは僕とhighlighterに気付いてたらしい、highlighterはaさんに気付かず...
エレベーターのボタンがたくさん光るなど変なことが色々起きて何とか到着...
highlighterが韓国のり持ってきてたのが面白かった
競技中
A 座席3
条件はa<bの席があってaが奇数番、bが偶数番だけ、dpでやろうとしたけどよく考えるとdp要らないことに気付き累積max取ってAC(0:03:15)
B 宝石商
要するに区間が被るならCを足せみたいな問題、典型として、[a,b]、[c,d]の区間が共通を持たないのはb<c or d<aで、それは独立なので、累積和取ってAC、怖いからちゃんと時間10倍しといた(0:15:11)
C 衣服
23℃ってなんだ？？→23℃を超えたらOUTじゃね？→あー0~63の部分集合andゲーね、とりま1,2,4,8,16,32は満たすよなぁ、63^5を大小関係で120とかで割れば通りそう、それを1~4までコピペしました。AC or TLEだなぁと思ってた提出(0:36:26) なぜかWA、しかも小課題1から全部2個落ちてるので、小課題1が落ちてる、よく考えれば1 23の時は全裸でいい。なんで同じテストケースが2個入っているんだ？とりまAC(0:39:51)
D 川下り
とりま考察する、テキトーにマージの2乗の木dpすると満点？が解けそう、実装する、サンプルが合わない、よく考えると違う、は？？？を15時くらいまでする、この時点で300点、普通に怖くなった、こんなに時間を食って普通に解法すら立っていない(普通にみんなを見てるとDにはボコボコにされすぎて捨てる勇気が出たなぁとは思った、でもテレフェリコで負けたのを思い出して本当に心が苦しくなった)
とりあえずスターグラフとパスグラフは取ってEを見ることにする、18点を取り、318点(2:10:05)
E 新たな橋
最後の制約なし以外の部分点の68点が、O(N^2)、パス、Q=1、全部自明そうな部分点なので最後以外を取ることにする。
首都がsな総和じゃなくiに行くすべての首都の総和なのがキモいと思った、追記:そうじゃなきゃ別にN(N-1)/2じゃね？
まず、costをテキトーに処理して追加する順番にAとBを並べる(プリム法を知らなかったので、プリム法みたいなノリで木になることは普通に最後のパスまで気づかなかった←プリム法知らんくても気づけや、小課題2が若干重くなったぞ)
Q=1のとき、島Xが固定なので、普通に何回で行けるかみたいなのを持っておけば行けるくね？って思った、これ普通に非自明らしい、Xを含むAとXを含まないBを併合するときに、Bに属するものが首都なとき、B全体→あとはAから順番に...で行けることがわかるので、Aが首都なとき何番目に追加されるかを持っておいて、Bに属するものをテキトーにBFSしてBに属するもの全てにBのサイズ+Aが首都なとき何番目に追加されるかをメモしておく、これを繰り返す。更新は1回なのでO(N)、元々合体してる時を考慮して変なBFSしてTLE(2:33:19)、これサンプルがなんか奇跡的に1/2すれば通りそうに見えたのだるい、バグ取りして37点を取り、355点(2:37:04)←通過おめでとう！！！！
次に流石に自明そうなN<=2000を考える、小課題1は自明←木さえわかってれば2も同じだったのに...
同じ考察をすると、
併合してないAとBを併合するとき、Aと同じ集団に属するj、Bと同じ集団に属するkに対し、D[j][k] (j首都kに行く)がAサイズ+D[B][k]、D[k][j]がBサイズ+D[A][j]で、これは1回更新なのでO(N^2)、集合全列挙は別にsetを使えばいい(このループでN回せるのがわかってれば...)
次にパスを考える、テキトーに3つと4つを繋げた時を考える、AAABBBBとすると、スコアが+6+6+6+6,+5+5+5+5,+4+4+4+4,+3+3+3,+4+4+4,+5+5+5,+6+6+6みたいになる、一般化するとサイズがa,bの時に
(a+b-1)b,(a+b-2)b...,b^2,a^2,a(a+1),...,a(a+b-1)
これを(a+b-1)bとa^2を入れればあとは差分を遅延セグ木とかで持っておけばいいなぁと思った(2回積分的なことすれば自明にできるけどね？？そりゃ遅セグのが早い)、設定する座標は経路圧縮だけして最小値、最大値を親とする系のUnionFindを使えばいい
これを実装し、WA(3:01:00 3:01:41 3:04:14 3:05:51)、これ全部b^2とa^2の境界とかa(a+b-1)と0の境界とかミスったり提出の併合をミスったりのWAらしい、何をやってるんだ？
とりあえず、すべてを実装し、小課題4が通り、最後以外通った(3:08:00)、でも割と苦労せず通り、普通にDが二乗木dpで4乗dpも思いついてないのが怖すぎた。
ここで点数を落ち着いてみると386点、テレフェリコの影響で、目標点を400ちょいに設定していたので、400をどう取るかを考えていた。ここで、明らかに通りそうなDの小課題1のN<=8の13点は別に8^8全探索するだけなので取れるとずっと思っていた、しかし、これをとっても399点、まぁFを見ていないのでFの最初を通して400ちょいを取ろうと思った。
D 川下り
雑にN<=8を実装し、8^8ループの中でN^2を入れてしまいTLE...テキトーに上から光を持って行ってNに改善し、小課題1をAC、ここで399点(3:22:44)、開始2時間で300点の時、死を覚悟したが、あと38分でFの小課題1を通して、なんとか400点を取ってボーダーギリギリで通りそうでギリ精神が保てそうになった。
F 奇妙な機械
まず、問題文がありえなく長い、この見た目は本当にいかつかった
N<=6を見る、テキトーに全探索すれば通ると思った、ところが、テキトーに全探索が思いつかなかった、しばらくし、5番目以内のどれ？4番目以内のどれ？...1番目以内のどれ？で120通り全探索を思いつき、シミュレートする、でも、本当になぜか合わないしなぜかTLEしてしまう、本当に焦った、これで399で落ちるかもと思うと本当に耐えられなかった。本当に焦りがmaxに達し、本当に怖かった。結局最後まで通ることはなかった、これはムズイ
競技終了
なんで、399点なんだ、、、って思った、本当に終わったと思った。
まず、席が左で普通に焦ってそうな感じを出してた韓国のりさんに点数を聞いた。330点台？とかでとりあえず彼には勝った、もしかして爆死してる？と思った、その後、Magentor達がいる前の方に行った、Magentorとaさんには点数が勝っていた、その後聞いたkeisuke6さんやhirayuu_At達の集団が400点越えしてて本当に焦った。hirayuu_Atが540と言っていたので、Eの難易度を聞いたら激ムズと返ってきて、こいつはACをした問題を激ムズって言ってるんか？？って違和感を感じたが、とりあえずEで68点を取ったところはよさそうだと思った(彼は100-100-100-100-40-100らしい、Fが解ける見た目をしていなかったので本当にすごい)、その後ガチで爆死をしていたfactの阿鼻叫喚を聞いてみんなで終わったをしていた、今思うと、Magentor、highlighter、factあたりに勝っている399点は流石に通ると考えるのが普通だが、4時間のコンテストでメンタルブレイクしていて、普通になぜか落ちると思っていた。若干申し訳ない
ボーダーは、324点だった、拍子抜けした。通ったという安堵と、僕の焦りはなんだったんだ？？となった、highlighterとCが意外とむずかったのかなぁという話をした。今思うとそこにPython不利問題置くくらいならC++に縛れよ...って思った(定数倍高速化として、32以上の要素は1つしかないということを聞いてそれを理解した瞬間、本当におぉぉってなったなぁ)
水やおやつをたくさんもらった、入黄した時のように水のがぶ飲みをして気持ち良かった
本当に通ってよかった、気分良く09の人達と秋葉のサイゼに行き、カラオケに行った。通って気持ち良かったこともあり、本当に楽しかった。
普通に色々勘違いをしていて、家の方向的にkinugoshiと帰るべきだったところを逆向きと勘違いしてpotatoと帰ってしまった...政府の陰謀！！！普通に坂歩かされたの許せん
帰るときに話したのだが、僕は、名前順的に最後尾だったので、前から来る人が見えるはずなのに、3回トイレに行ったらしいpotatoに1回も気づかなかったらしい、ガチで集中してたらしい、potatoから応援をいただき、最寄りについて身内の09から離れた時に「よかったぁ...」という声がかなり漏れてしまった。
あっきはっばらー
最後に
このコンテストは人間の精神を破壊します。
マジで、Dが自明の2乗の木dpに見えたことや、前年がテレフェリコだったこともあり、300点台だったある程度強い人間全員落ちたと思って怖かったと思ってる。マジで全部の小課題が割と考えずに取れて怖かった、D粘着がたくさんいる中、Eを1時間で最後以外の小課題を通したのが本当に良かった、これが初の春進出です。頑張ってきます。
完徹してこの記事を書いています。では、これから開成生として中学入試の算数を解いてきます。楽しみ～
追記 : 74/85点でした。雑魚、おもろいセットなので、数研とKCLCの新歓成功して欲しいなぁ。本当に6月が楽しみ