2023-08-03

Div1 バチャ日記4 - Codeforces Round #599

Cで大変なことになってしまった...

f:id:Mitsubachi88:20220127160514p:plain

AB2完。Cは終了後にAC。

A - Tile Painting

最後の TCB で似た設定を見た。素因数を $2$ つ以上持つなら上手く $1$ からその素因数を足し引きすることで全部の index を覆えるので答えは $1$ で、 $1$ つならそれを $p$ として $\mathrm{mod} \ p$ で考えれて答えは $p$ になる。

B - 0-1 MST

これ面白い。最初頂点を半分ずつ分けて再帰する形かと思ったが、 $3$ 頂点のコスト $1$ の辺からなる完全グラフの各頂点にコスト $0$ を伸ばしたもう $1$ 個の頂点をつけたので $0$ ではなく $1$ になるので嘘だった。

大人しく $1$ を取り除いたものの連結成分数を考えると、愚直に縮約しても計算量がそこまで大きくならないことに気づく。 priority_queue を使って実装したが、使わなくても良かったかもしれない。

C - Sum Balance

サイクルを見つけて再帰する形にして実装してたが、同じサイクルを複数回舐めるハメになるのでこれでは TLE になってしまう。そこで $O(3^N)$ の DP を考えて、先に頂点集合ごとにサイクルがあれば $1$ つ見つけてあげるという実装にした。同一サイクルを $2$ 回以上辿っていそうなら強制終了するのを組んだが WA が取れないので TLE 覚悟で外したら通った。なんでやねん。

$N \leq 15$ で $O(3^N)$ が頭によぎらないの、かなりダメだった。

2022-04-05

ARC100-E 「Or Plus Max」(700点) 別解

再帰的に解けたので。

問題文

概要

整数列 $A_0,A_1, \cdots , A_{2^N-1}$ について、 $i \neq j$ かつ $i\ or\ j \leq K$ を満たす $i,j$ についての $\max(A_i+A_j)$ を $1 \leq K \leq 2^N-1$ について求めろ。

解法

長さ $2^X$ の数列 $Y$ について $f(Y)$ を上の問題の答えとなる数列の先頭に $0$ を付け加えた長さ $2^X$ の数列とします。

$X=1$ の時 $f(Y) = \left( 0,Y_0+Y_1 \right)$ です。 $X \geq 2$ とします。長さ $2^{X-1}$ の数列 $B,C$ を以下のように定めます。

$B_i = Y_i$
$C_i = \max(Y_i,Y_{2^{X-1}+i})$

$f(Y)$ の前半分は $f(B)$ に帰着できます。後ろ半分について、 $f(Y)_{2^{X-1}+i}=\max(f(Y)_{2^{X-1}+i-1},f(C)_i,Y_i+Y_{2^{X-1}+i})$ です。

よって、長さ $2^X$ の数列について $f$ を求めることは長さ $2^{X-1}$ の数列 $2$ つについて $f$ を求めることに帰着できます。

よって、 $O(N\ 2^N)$ でこの問題が解けました。

実装例

2022-03-21

JOI 2021/2022 春合宿参加記兼爆死記

目標は15位/29人ぐらいのつもりで参加しました。 todo : なんか写真を貼る

Day 0

前泊組は競技1日前の17時ホテル集合なので9時ぐらいから観光をした。具体的には渋谷や明治神宮、歌舞伎座や銀座を見て、下見としてNTT駒場と近くの大学入試センターと筑駒を見た。

ちなみに15分ぐらいホテルに遅刻した。申し訳ないです。

7時ぐらいに配布される弁当を食べて、ホテルの目の前にあるスーパーに買い出しにいった。お椀で食べるカップヌードルを初めて見たので買って、日が変わったころに食べた。(デブの元)

8時とか9時に科甲をしてきた十六夜さんが最寄り駅について、雨が強かったので道案内をした。パソコンを2台持ってきてるとのことだったのでお借りして仮想マシンでの挙動を確かめる。ありがとうございます。

Day 1

午前4時ぐらいに目が覚める。どうやらベッドの上でYouTube見てたら寝落ちしたらしい。ベッドに潜って寝なおして、7時ぐらいに起きたがもう少し行けると思って寝た。この時点でまずいのだが7時20分ぐらいに街宣車が通って目が覚めたのでそれに救われた。

適当に朝食のビュッフェを食べて8時のロビー集合に間に合わせた。

適当にdefineに「身長変わらないですね」とか煽られたり適当に人と交流したら競技会場に移動とのことだったので移動。ちなみに水とかお菓子を持っていけるが、持ちすぎると移動が大変なので注意しましょう。

9時10分に競技開始。封筒を開けて実装上の注意を見ると京都観光だけ問題名が面白いのでまず見る。シンプルな設定だが難しそう。

一通り見るとkyotoの小課題1が自明なので取る、9:33:45。jailの小課題1も思いついたので9:51:01に回収。mispellingの小課題1も大小関係決め打ちと思いついたが実装が重かった。10:24:41に回収。

考察をしていく。まずjailの小課題2が「一方のパスがもう片方を完全に包含している」が必要十分だと思ってDFSとかで回収するのを書いたがパスすらWAを吐いて辛い気持ちに。結局通せなかった。

並行してkyotoの小課題2とかを考えていたが思いつかず。

mispellingの小課題3も実験をしたが全然性質が見えてこない。

成果を出せないままドバドバ時間を浪費していく。前の席のyutoが提出したらお祈りをして通ったらぬいぐるみの犬を抱きしめてたりして面白かった。

結局mispellingは=は無視出来て、<とか>が重要で、よく考えると最後の出現位置だけが気になると気付いて小課題2を回収。なんとこの時点で14:00:05であり非常に沼をしていたことに気づく。

得点は 5 - 10 - 28 で43点。最下位を覚悟した。

昼食会場でjailの嘘を指摘され辛い気持ちになった。

解析&解説が始まる。この時に順位表が配られ。25位/29人であることを確認、厳しい。kyotoはあまりにも天才だと思った。jailの嘘にもっと早く気づいていたらもう少し点が取れていただろうなとなった。

ホテルに戻ってPCTと十六夜さんとカードゲームで遊ぶ。SETを布教したり大富豪をしたりした。食事を食べてダラダラしてCodeforcesに出て、日が変わるころに寝た。

Day 2

今日も相変わらず絶起。

9時に競技開始。Communication Taskが出て少し嬉しい気持ちに。まあ結論としては最難関枠なんですけど。

一通り問題文に目を通してcopypaste3からやる。雑に小課題1と小課題2を9:33:34、9:55:57に回収。小課題3がパッと思いつかないのでチラ見して点が取れそうなteamに行く。

小課題1を適当に拾って(10:10:05)、残りの部分点も回収できると気付いたが、結構実装が重たかったので後回しに。

copypaste3の小課題3を考えているとX=(空文字列),Y=(Sのsubstring)の状態があることに気づいて、dp[i][j]で[i,j)をYに持っていくまでの時間というのを思いついてこれを書く。10:53:44に回収。高速化して小課題4もいけるかなと思ってロリハとか書いたけど無理だった。1時間ぐらい捨ててしまった。

諦めてteamに戻る。小課題3、小課題4はサクッと思いついたので11:57:58に回収。この時小課題4も解いていたが提出したときは小課題3までのつもりだったからちょっとビックリした。

小課題2を考察すると、座圧して2人決め打ちしてあげると二次元累積maxとかでうまくいくと気付いて12:21:13に回収。

少しflightsの考察をする。木の全辺情報を共有するのを投げてとりあえず12:56:25に7点。

ここらへんでteamの小課題5と小課題6あたりが小課題2と同じように解けることに気づいて13:13:11、13:33:51に回収。

最後の最後でflightsのいい解法が思いついたので急いで投げた。20秒前に出したので解析まで結果が分からなかった。(結論としては単純なミスで落ちていた)

20 - 7 - 73 で100点。厳しい。

昼に行く。defineとひらきちと駄弁る。defineの感じ的に100点は耐えてそうだなと思う。まあそんなことはない。flightsやばくないですかって聞いたらひらきちが「あれは激ヤバだよ」って言ってた。

解析/解説が始まる。上がってるかなと順位表を見たらむしろ2つ下がってて27位/29人。逆日本代表圏内でまずい。一応Day2内では24位なんですけどね...

kaageに「僕は今日でおさらばなんで後2日でhoge点取れば最下位は回避できますよ^ ^」って煽られる。生きててすいませんでした。

flightsの解説で「95点は人間的で、100点は非人間的な解法を使います」「これまでのJOIの問題のどれよりも難しいと思う」「難しすぎてWTFにも出せないと思う」とか言っててすごかった。解法を聞いたけど本当に難しいと思った。確かに人間枠ではない。

Day 3 以降

(放置してたので書くだけ書きますこれいる？)

Day3 10-41-0 : 51

Day4 22-13-14 : 49

でした。

Day3: sprinker で遅延セグ木を頑張って書いて 41 点まで回収したが本解法は全然高度なデータ構造を使わなくてビックリ。遅延セグ木無限バグらせ編をした覚えが。

Day4: dango3 に関しては limit の倍まで回数を落とせていたが昼食の時間に limit 分簡単に落とせることを penguinman に教えてもらい解析中に実装したら通ってしまった...

合計 243/1200 で 26/29 位。悲しい。

表彰式で chokudai さんと写真を撮ったり JOIG の人と交流したりした。三田に住んでる友人が「三田は何もないド田舎」とか言ってたので三田出身の女子に「三田って田舎ですよね」と言ったらえ？みたいな反応をされた記憶がある。

表彰式の後は渋谷の EST で yuto, forested, rheo, penguin とビリヤードとダーツをした。ビリヤードが人生初だったので下手すぎて全員から一生笑われてた。

2022-02-13

JOI2021/2022で入賞した話

よくあるやつ

f:id:Mitsubachi88:20220213192605p:plain

f:id:Mitsubachi88:20220213192715p:plain

本選時点

AtCoder 2049(Highest 2093)

Codeforces 2153(Highest 2153)

-1日目

JMO本選に出る。長くなったので別記事にした。

1日目

開会式+プラクティス。開会式、Zoomで参加者挨拶を流しただろうけどラグがひどかった。去年みたいにYouTubeにすればいいものを。

僕の挨拶は自分の声を聴きたくなかったので抜けたが、discordを見るにウケたっぽい。滑らなくてよかった。(校歌歌って滑ったら、嫌なので)

プラクティスはいつもの5問。最初の3問は書いたけど残りがだるいのでAtCoderから過去の自分が書いたものを持ってきて貼る。ついでに出力形式の確認をして、

空白区切りを改行区切りにしたりその逆をするとWA
末尾に余計な空白とか改行をつけてもAC

であることを確認。(先頭につけた場合はやらなかったな)

Among Usで軽く交流して日が変わる前ぐらいに寝た。

２日目

7時に起床。落ち着かないので朝食後ストレッチと朝風呂をしてYouTubeを見る。9時に競技開始。

[1] インターカステラー

f:id:Mitsubachi88:20220213142438p:plain

雑に二分探索だなとなり雑に書いてAC。難易度5かな。

[2] 自習

f:id:Mitsubachi88:20220213142639p:plain

とりあえず $A_i=\max(A_i,B_i)$ としてよくて雑に考えて二分探索が見えるので書く。余裕やなとか思って出すと0点が帰ってきて焦る。

$M=1$ の小課題1は $\min(A_i)$ であることを確認して考察が間違ってはなさそうなことを確認。コードをよく見たら判定中にオーバーフローしてそうなので雑に枝刈りをして出す。通って一安心。

[3] 選挙で勝とう

f:id:Mitsubachi88:20220213143433p:plain

マジで山場だった。辛かった。例年の傾向的に3問目にあるであろう難易度9を通せれば勝ち、そうでなければ負けと思って開く。

小課題1はいいとして、2以降うまく思いつかない。協力者の人数を決め打つとDPがうまくできて $O(N^4)$ が得られるので小課題4,5,6をAC。

小課題1,2もとりあえず通す。 $N=K$ の小課題7を考えるがよくわからない。

ここで協力者の人数を決め打ったときの最適値がいい性質あるんじゃないのかと思ってやると三分探索の形になる。けどTLE。

ここらへんでパソコンでコンパイルはできるけど実行がなぜか不可能になったので泣く泣くコードテストの民になる。

次に考えたのは $i$ 人協力者がいる場合と $i+1$ 人いる場合でそんなに差がないのではないかという予想。サンプルで試すと各州の役割の変化が高々 $2$ 人ぐらいであることに気づく。これを利用して書く。お祈りしながら出すと10点。(11:31:57のやつ)

絶望しながらどこが落ちたかを見ると小課題3に該当する1ケースだけということに気づく。というわけで $N \leq 100$ だけ場合分けしてAC。幸運すぎる、よかった。

[5] 砂の城 2

f:id:Mitsubachi88:20220213145414p:plain

問題4と5を両方見るが、5しかパッとわからないので、雑に書いて小課題1,2を回収。

[4] 鉄道旅行 2

f:id:Mitsubachi88:20220213145539p:plain

これも小課題1しかわからない。しかもダイクストラで解くとTLEで01-BFSじゃないと通らないという鬼畜っぷりだった。解き方が悪いのかもしれない。

結局 100+100+100+8+19=327点でフィニッシュ。

[4]と[5]の部分点を全然回収できなかったので絶望してたけど終わった後にdiscordとか非公式順位表を見たが16位なので入賞圏内に入れてそうなことを知る。めちゃくちゃうれしい。

交流会

双子が交流をするので参加。後輩と同じチームだった。特にキャリーできなくて申し訳ないという気持ちに。

おわりに

長い競技科学人生でしたが最後の最後には春合宿に参加できそうでうれしい。春は...まあどうせ代表にはなれないのでエンジョイ勢します。ソラでセグ木も書けない人間。

セグ木をソラで書けなくても、2次予選Bランクでも人差し指タイピングでもここまでいけますので希望を持ってこれを見てる若い人は精進しようね。

追記

入賞してました。本当にありがとうございます。筑駒10人っておかしくない？

2022-02-13

JMO2022 敗退記

試験前

中1,2はJJMO予選落ちで中3から毎年JMO本選に出たのでとうとう3年目。

名古屋会場は待遇がよくて飲み物とか置いてくれる。今年はペットボトル2本(麦茶と桃のサイダー)、去年はペットボトル3本とお菓子だった気がする。一昨年はエルおおさかで受けたので知らないけどhayarinaさん曰く同じ感じだったらしい。エルおおさかはアクセスも悪いし終わっている。

炭酸はいらないので前にいた人の麦茶と交換して(サイダーを押し付けて)試験を受ける。(前にいた人、ありがとう)

試験中

肝心の問題は1と2しか解けなかった。後ろのkkkaaaが4完+aを主張していた。怖すぎ。

1がどうみても $m=1011$ っぽいのだが全然うまく書けない。先に2を解くことに。

解の予想すらパッと立たない。頑張ると $f(x)=x+1$ っぽいのでとりあえず十分性を示しておく。

雑にやって $f(x) \geq x+1$ と $f^{f(n)}(m)=f^{f(m)}(n)$ が示せるので、これを使って何とかしたい。 $f(1)=1+x$ とすると $f^{f(1)}(x+1)=f^{f(x+1)}(1)=f^{f(x+1)-1}(x+1)$ より $f(x+1)=f(1)+1=(x+1)+1$ がいえる。で、 $f(i)=i+1$ となる $i$ があるとして $f^{f(i)}(i+1)=f^{f(i+1)}(i)=f^{f(i+1)-1}(i+1)$ より $f(i+1)=f(i)+1=(i+1)+1$ となるので帰納法的に考えて $n \geq x+1$ について $f(n)=n+1$ がいえる。後は $f^{f(1)}(1)+1=f(1)f(1)$ を考えて $2x+2=x^2+2x+1$ がいえるので $x=1$