JOI 2021/2022 春合宿参加記
人々よりひと足早い春合宿参加記です。
本選
JOI 2021/2022 本選参加記 を見てください。
D が解けてないので弱いほう
Day 0
2021 春合宿 2-2 Road Construction を解いた。
平面走査を何回もして二分探索で境界値を探したあと、set で具体的な答えを構築する
BIT は流石に書けるのでライブラリを使った（直書きしないことで春合宿への参加を最後まで隠蔽する最悪仕様）
午前 3 時 47 分に「そろそろ寝るか」と予約ツイートしておいて、日付が変わる頃に寝た。
Day 1
行きの電車で yuto さんに会った。渋谷で乗り込んだら見つけたので無言で隣に座ったら不審者だと思われた。 会場について控室に入るなり「おはようございます！」と叫んだ。（びっくりさせたかったので） define がちゃんと予約ツイートに騙されていた。 これで物理に行かない噂でも流れたら面白かったが、別にそんなことはなかった。
Jail は意味不明だったので、10 点しか取れなかった。 実は人ごとに一気に移動させていいらしい。「証明はかなり難しいと思います（E869120）」じゃあないんだよ
京都観光も何も分からず 10 点。むずすぎる。 40 点の部分点が種類数で抑えられそうな雰囲気はしていたが、かといって解法が分かるわけでもなく…
misspelling は、条件を区間に言い換えればあとは遷移がセグ木で管理できて、解ける。 どうやら、後ろから読むと楽らしい。AGC か？
Day 2
会場までは誰にも会わなかった。遅かったからだろうか。 そろそろ明日から物理に行くことが知れ渡っていそうだった。
Copy and Paste 3 は、マジで意味がわからなかった。とりあえずペースト部分で再帰的に解けるので雑な DP を書くと 15 点が取れる。ロリハで高速化しようとしたが意味がなかった。全部 a の場合は長さだけ考えればいいので、これは別の DP を書くと 5 点入る。満点がそこそこ発生していたが何も分からなかったのでこれは完全に実力不足。
Flights は面白そうだが、木を分割するとかオイラーツアーとかそういうのは思いつかなかったので、頂点の組をエンコードして足りない 6 bit 分全通りの情報を送ると 896 bit で 28 点が取れる。計算ミスで 29 点だと思って質問を送ったのは申し訳なかった。エンコードしたものを 48 で割って送ると 32 点になるらしい。自明な改善なだけに少し残念。
Team Contests は、順当に考えると二次元累積 max で 2 乗が取れる。x を昇順に見て、y を全探索、y の値ごとに z の最小値を記録する方針だと、73 点までは取れる。満点解法はここからの改善では思いつけなかったが、周りはかなり解いていたので反省。
Day 3~
ここまでで 241 点。最下位となることを祈って物理に行ってきます
JOI 2021/2022 本選参加記
JOI 本選に参加してきました ギリギリ春は通ってそう（行くとは言ってない）
得点獲得の記録
- 06:19 A 100 点
- 29:47 B 10 点
- 33:39 B 100 点
- 54:14 C 5 点
- 56:11 C 10 点
- 98:26 C 61 点
- 121:09 C 100 点
- 152:33 D 8 点
- 167:46 E 9 点
- 177: 45 E 19 点
- 222:30 D 16 点
- 237:46 D 27 点
合計 346 点
ムーヴメント
- 06:19 A 100 点
それはそう
これ難易度 5 ってほんと？の気持ちです ダイクストラと同レベルは、嘘じゃないかな…
- 29:47 B 10 点
A が始まって B に取り掛かります どうみても二分探索なのでコードを書くも、0 点が出て困惑
考察ミスを疑って小課題 1（max の min をとるだけ）を通すと通るので、バグを確信 結局オーバーフローでした
Cyanmond が、本選前に書いた気をつけることリストに「kaage」って書いてたおかげで気づけたらしくて、先輩として嬉しいです（全く嬉しくない）（参考 : JOI2021本選参加記）
- 54:14 C 5 点
嘘貪欲だった。$B[i]$ は昇順に取った方が良いのは当たり前なのだが、途中で取らないという選択肢がないのは、やばい（やばいので）
- 56:11 C 10 点
嘘貪欲をちょっと修正したら 10 点取れたが、嘘貪欲に違いはない。
- 98:26 C 66 点
嘘貪欲に気づき、DP を考える。そもそもメモリ制約に DP と書いてあるんだから最初から考えろよ
$B$ の昇順に考えるべきなのはそうなので、ソートして考えるとわりとすぐに分かる。得る協力者の数を決め打ちして、
$dp[i][j][k] = i$ 番目までで、$j$ 人の協力者を得て、$k$ 個の州を取るまでにかかる時間
とすると、$O(N^2K^2)$ で解ける。
- 121:09 C 100 点
まず、部分点を考えると、添字 $k$ がいらなくなる。
取らない州がある場合も、取らない州のあとに協力者を持ってくるのは明らかに損なので、「協力者と票だけ取る州の混合部分」と「票だけ取る州と何もしない州の混合部分」に分けることができる。そうすると、結局どんな場合でも添字 $k$ はいらなくなって、あとは票だけ取る州を貪欲に決めればよくなる。
こうして $O(NK^2)$ まで落ちるので、満点
- 152:33 D 8 点
自明 $O(N^2M)$ で辺を張って、お好きなように
- 167:46 E 9 点
自明、これは難易度 4
- 177:45 E 19 点
ほぼ自明、$O(H^2W^2)$ で長方形を列挙して、$O(HW\log HW)$ で判定すると、$O((HW)^3 \log HW)$ で、まあ通る
log 落とすとあと 5 点取れるらしい
- 222:30 D 16 点
残り 30 分くらいで、行ける場所が区間になるのに気付く 大急ぎで実装して取る
- 237:46 D 27 点
もとの区間の計算にセグ木を使うとこれが取れる
あとはどう考えてもダブリングするだけで満点なのだが、時間が足りず
感想
B のバグに時間かけたり C の考察が遅かったりするから ARC でいつも失敗するんですよ！？！？！？！？
ARC133-D Range XOR 解説
久しぶりのはてブロです。
解説
ある整数 $k$ があるとき、$2k \oplus (2k + 1) = 1$ なのを利用する。 区間の xor は、端の偶奇で場合分けをして次のように求められる。
- $l$ が偶数、$r$ が偶数のとき
区間の xor は、$r$ と、$(r-l)/2$ 個の $1$ の xor に等しい。
- $l$ が偶数、$r$ が奇数のとき
区間の xor は、$(r-l+1)/2$ 個の $1$ の xor に等しい。
- $l$ が奇数、$r$ が偶数のとき
区間の xor は、$l,r$ と、$(r-l -1)/2$ 個の $1$ の xor に等しい。
- $l$ が奇数、$r$ が奇数のとき
区間の xor は、$l$ と、$(r-l)/2$ 個の $1$ の xor に等しい。
これらの中で、$3$ つ目以外は簡単な割り算と和の公式で通り数を数え上げられる。 $3$ つ目は数え上げが難しいので、次のような桁 DP を組んで数え上げすると良い。
$dp[i][j][k][m]=i$ 桁目よりも上の部分を上位ビットとして、上位ビットの xor が $V$ のそれと一致し、$l$ の上位ビットが $L$ より大きい場合は $j$ が $1$、$r$ の上位ビットが $R$ より小さい場合は $k$ が $1$、$l,r$ の上位ビットが異なる場合は $m $ が $1$ となるような $(l,r)$ の通り数
ただし、これだと $l$ と $r$ の間隔の条件を満たせないので、最下位のビットの値だけずれてしまう可能性がある。ここで、$l$ が奇数で $r$ が偶数であるという条件を考えると、間隔が合う必要十分条件は、$V$ を $4$ で割った余りが $0,3$ のいずれかであることであるので、この場合分けを最初にしておけばよい。
以上で、この問題が解けた。
感想
桁 DP はコンテスト中に書き上げられたが、それ以外のパートをミスしていて通せなかった。
競技プログラミングは物理チャレンジの役に立たない
国際物理オリンピック日本代表候補に選抜されました。実感がありません。
第 1 チャレンジを通過した際もいろいろ（本当にいろいろか？）書きましたが、せっかく選抜されたのでもうちょっと細かく書きましょうかということで
きっかけ
数理の翼伊計島セミナーというものがあります。伊計島に集まって数理系のイベントをしようというやつです。（雑すぎる） 2020 年度はオンラインになって名前が変わるなどいろいろあったんですが、そこで @masageophysics さんが物理の話をしていました。 また、弊 69 期に JPhOer がいます。知り合いというほどでもありませんが、何度かマウントを取られたことがあります。 そんなこんなで、JPhO に参加しようかな〜と思い始めました。
確かセミナーのちょっと前に、休校であまりにも暇だったので河合塾の『らくらくマスター 物理基礎・物理』を買っていました。やってたんですけど三日坊主でやめました。（力学はギリ終わったかな…？）結果的に、中 3 の時は結局忘れたまま申し込みしませんでした。
参加
今年も例によって申し込みを忘れていました。申し込み期限が迫っているのに気づいたのは締切の 2 週間前です。 他にも物チャレ参加勢が学年に 2 人いたので共同実験をしようかとも思いましたが、2 人はすでに実験を終えていました。（悲しい、話）
物理科の I 先生に相談したら、実験設備は使えることになりましたが、怠惰（あるいは、他に何かすることがあったのかも）故、参加を決めて始めたのが 1 週間前くらいでした。とにかく毎日物理実験室に行って実験して、データを取りました。レポートの執筆自体は徹夜すればできるだろうという計画（それは計画とは呼ばない）です。結局実験にかけたのは 3 日間、レポートを書いたのは 2 日間でした。レポートはあとでどこかに公開します。
提出締切前日は徹夜して gnuplot でグラフを描いて、締切ぎりぎりに提出（兼申し込み）しました。この頃はマジで忙しかったです。みなさんは 1 週間前に科オリ参加を決めるのをやめましょう。
さて、実験レポートの提出は済みましたが、1 次には理論問題コンテストがあります。前述の三日坊主と、本校の授業カリキュラムのテキトーさによって、物理をやったことなど一切なかったので、勉強をする必要がありました。1 年間放置していたさっきの参考書と、良問の風を買ってきてやり始めました。
みなさん、物チャレ対策を急いでするときは、問題集を決して前から順番に解いてはいけません。相当暇でもない限り絶対に終わりません。そう、私はなんと力学までしか問題を解かないまま理論問題コンテストに挑むはめになったのです。 さすがにこれではまずいので、前日に昨年の問題を一通り解きました。解けてませんが。 でも、第 1 チャレンジは資料持ち込み OK なので、公式を覚える必要はありません。お気持ちだけわかっていれば大丈夫です。 結局これで参加して 65 点という散々な結果でしたが、なんか第 2 チャレンジに通ってしまいました。なんででしょう。 ちなみに、実験レポートの評価は BB でした。まあそんなもんかなあというところです。
第 2 チャレンジまで
通るとは全く思っていませんでしたが、通ってしまったものは仕方ないので第 2 チャレンジに向けて勉強を始めました。 この頃、Twitter で通った報告をしたら参考資料をくれた方が数名いました。いい話。
とりあえず過去問を解いて、知識的に不足があったら調べる、というスタンスで進めました。物理法則もその間に覚えていきました。 緑本（物理チャレンジ独習ガイド）はやるべき、と聞きましたが時間がなかったので流し読みしかしていません。読み物として通読するとためになりそう。 過去問もいくぶん分量が多いので 5 年分しかやりませんでした。誘導のおかげで覚えるべきこともそこまで多くなく、時間をかければほとんど解けたので、あとはスピードと計算の正確さがネックでした。何か言うとすれば、2020 の相対論の積分がわりと重くてびっくりした（解けた）のと、2016 の最後のほうだけは未だに解けてませんが、それ以外はよく考えれば誰でもたぶん解けます。夏休みが始まってから 3 週間の間にゆるゆるやっていました。
実験問題の対策はしていませんでした。実験ほぼしたことないし対策方法がわからんので…
第 2 チャレンジ本番
とりあえずコンテスト別に感想を。問題は公開されてるので見てください。
理論問題
大問 1
氷を浮かべる浮力の問題です。やるだけでした。一箇所計算をミスりましたが、本質ではないのでセーフ。 ここはほとんどの参加者が解けたと思います。
大問 2
振り子のやつです。問 2 で「2 階の微分方程式が、解けな〜〜〜い！（cv. 吉高由里子）」になりましたが、冷静になると sin でした。このくらいはすぐ浮かぶようにしろ。後に回しましたが、ここで時間をめちゃくちゃ食ってしまったので解き終わりませんでした。
大問 3
電磁気のやつです。 電磁気の基本法則をろくに覚えていなかったので、たぶん最初の方をそこそこ落としています。残りは黙って微積すれば解けます。
大問 4
誘導に乗っていきましたが、問 8 以降は解けませんでした。知識と経験の不足です。
実験問題
Web サイトに数値を入力すると実験結果が返ってくる仕組みでしたが、これって Python でスクリプト書いたりするとリクエスト一斉に送って実験結果集まったりすると思うんですけどこの辺のレギュレーションはっきりしなくて大丈夫なんですかね 大丈夫ではないと思います（まあコンテスト始まってから解析するなら手入力のほうが速いんだけど たぶん）
実験をしたことがほぼないのでオンラインで助かりました 来年までには…
大問 1
やるだけなんですが、逃げる熱の符号を逆向きにしていたため、無事死亡しました。熱力学第二法則しゃん…
大問 2
やるだけ 2
問 II-2 の説明にだけは自信がないですが、残りの計算は合っていました プランク定数くらいは覚えてると検算できて嬉しい
大問 3
ブラックボックスの中にコンデンサが入ってるやつですが、 コンデンサを途中まで逆にしていて、リップルの図を終了間近に全部書き直す羽目になりました 最悪
中 2 の時に技術教師がこの話をしていたので、感動…
春合宿まで
通るとは全く思っていませんでしたが、通ってしまったものは仕方ないので(ry
競技プログラミングは物理チャレンジの役に立つのか？
立ちません
「みんなのプロコン 2019」-E Odd Subrectangles 解説
解説
DP などを考えても解けそうにない。
行基本変形に思いを馳せる。$N \geq M $ を仮定して、掃き出し法を行ってみる。この行列の rank を $R$ とする。 処理後の行列を眺めると、$R$ 次正方行列についてこの問題を解いて、それに $2^{N+M-2R}$ をかければ答えとなることがわかる。 計算量に余裕があるので、正方行列について解くには、次の式を用いるといい。これは、正方行列においては、選んだ行と列の和集合のサイズに subrectangle の値の和が等しいことを考えると出てくる。
$$ \sum_{i\&1=1,1\leq i\leq R}\binom{R}{i}\sum_{j=0}^{R-i}\binom{R-i}{j}2^{R-i-j} $$
掃き出し法にかかる $O(N^2M)$ が時間計算量のボトルネックとなる。
第 6 回 ドワンゴからの挑戦状 予選-C Cookie Distribution 解説
解説 AC
組み合わせ苦手すぎる…
解説
求める値は、全ての配り方におけるうれしさの総和である。
ここで、うれしさを「子供が持っているクッキーの中から $1$ 枚を選ぶ方法の数」と言い換える。（これがめちゃくちゃ重要）
選ばれるクッキーを配った日ごとに分類して $x_1,x_2,\cdots x_K$ とすると、これらを子供に割り当てる方法の数は $\frac{N!}{\Pi_{i=1}^K x_i!}$ になる。また、残りのクッキーの配り方は、残り $N-x_i$ 人に $a_i - x_i$ 枚を配るので、$\binom{N-x_i}{a_i-x_i}$ となる。
これらを、ありうる全ての $x$ の組について足し合わせればよいが、これは DP で解けるので、 $O(N^2K)$ でこの問題が解けた。
感想
言い換え、大事！
JPhO 予選 参加記
正式名称は「物理チャレンジ 第一チャレンジ」
きっかけ
去年の数理の翼 N セミナーで @masageophysics さんの話を聞いた
その年は自分は申し込みを忘れて、彼は振り込みを忘れたんですが…
参加前
春になって物チャのことを思い出したので、本校物理科 I 先生に相談した。（これがだいたいレポート締切 2 週間前）
レポート執筆
実験場所は使えることになったが、実験を始めたのがだいたい締め切り 1 週間前で（？？？）、それから 3, 4 日通って実験をしていた。
レポートを書き始めたのは締め切り 3 日前で、締め切り前日に実験を終わらせ、その日の夜に徹夜してレポートを書き上げた。最終日に学校で少し手直しして、提出した。
おもりを吊り下げて、滑車で台車を横に引いて走らせて移動距離を記録し、記録テープや台車の摩擦を測定して差し引いて、最終的には重力加速度を計算する、という実験をしたが、実験の時間がなかったので、データは本当に最小限しか集めていない。グラフは gnuplot で描いたので、見やすかったとは思う。 「どこの高校にもあるような簡易的な実験器具で、なるべく精度の高い測定をした」と主張した。（まあ去年もそういうレポートあったし…）
計算した摩擦力の誤差は $0.03\mathrm{N}$ くらいだったので精度は悪くないとは思うが、全部のクオリティが中の下くらいだったと思う。
理論問題
物理はやったことがなかったので、河合塾の『らくらくマスター 物理基礎・物理』と、良問の風を買って解いた。ただ、これも時間がなかったのでやったのは最初の力学/熱力学あたりだけだった。（良問の風に関しては力学すら終わっていない）
特に電磁気に関しては何も知らない状態で試験に臨んだ。（参考書の閲覧は OK なので、試験中はらくマスに載ってる公式をずっと見てた）
過去問は試験 1 日前に去年の分だけ解いたが、半分取れるか怪しい感じだった。あとから聞くと、今年の試験問題は 4 問がそのまま過去に既出だったらしい（ええ…）。たぶん本番も半分も取れていない。
通過
さっき速達が届いて、通過していた。たぶん物理オリンピック日本委員会のミスだと思うが、夏休みがまた忙しくなった。
