はじめに
今年のJAG夏合宿は，国内予選と同じチームK1NTOKIのメンバーで参加しました。
いい感じに得意分野（と苦手分野）が分かれていてとても良いと思っています。
チームの方針としては，Aをキクタ ンさん，Bを僕が見て，それ以外をk1suxuさんが見るという感じです。ABを通した段階で解かれているor解けそうな問題があれば，適切に振り分けて実装するという流れです。
day1
コンテスト
B
コンテスト開始直後，予定通りまずBを見ました。直感的にソートが最善だとは思いましたが，証明がなかなか思いつかず。k1suxuさんに相談したらよさそうみたいなことを言われたので，信じて書きました。通ったのでよかったです。
L
Lが早々に解かれていたので，Lから逆順に見ることにしました。k1suxuさん枠を感じたので考察しつつ投げると，商列挙ですとか言われたので，一旦それを受け止めて考察を続けます。
A
その裏で，A問題にキクタ ンさんが苦戦しているのを観測します。提出してWAが返ってきたものの，その理由が良く分かっていないらしいです。k1suxuさんも加わって原因を特定していました。2人がかりでも解き切れていないようだったので，首を突っ込んでみると「問題概要は聞かないで一人で問題を読んでみてください」と言われました。誤読の可能性が高いため確かに有効な方策だと納得したので，落ち着いて読みます。読み終わって解法を伝えた結果，キクタ ンさんは(3, 3)と(3, 3)みたいなまったく同じペアを数え忘れており，k1suxuさんはidenticalを「異なる」という意味でとっていたようです。僕もidenticalの意味にはあまり自信がなかったので持ち込んだ英和辞典を参照して，「等しい」という意味であることを確認しました。意味を見てから，ああ確かにidentity mapで恒等写像 とかidentityで自己同一性とか言いますねと腑に落ちました。意味が明確になったのでそれを整理してAC。
F
次に，Fがほとんどやるだけだとk1suxuさんに言われたので，問題と解法を聞いて確かによさそうと言いました。しかし，問題が簡単すぎたので何かおかしいと思って問題文を一人で読んでみます。すると，LCA に行って偶奇のいい感じのところで待機を繰り返すとよいという結論になったので，実装を任せました。途中，Sを最初に2倍にすると偶奇性のところで何も考えなくてよいと言う係をして，AC。
L
さて，Lに戻って解法を考えます。k1suxuさん曰く，商列挙を2回やっても，調和級数 的に考えて全体
G
Gがある程度解かれていたので，キクタ ンさんと2人で考えていました。直感的には左下ARC205B を思い出して，実は操作に対して不変量があるのではないかと考察をすると，斜めに見たときの白の個数の偶奇が操作回数の偶奇により不変であることに気付きます。これに気付きさえすれば，あとは01列に対する区間 XORと全体の0の個数が取得できればよいので，遅延セグ木で解けそうです。具体的なデータをどう載せるかについては良く分からなかったので，k1suxuさんに頭を下げて，写経とともにやってもらいました。最初の白の個数を数えるのが少し大変でしたが，無事AC。
E
E問題は，良い感じにグラフを構築できればあとはやるだけであるということまではk1suxuさんが考察していました。ただグラフの構築が大変で，途中で球面上にある円の包含関係をどうすればいいですかと尋ねられたので，ベクトルの内積 とかをこんな感じで使うとたぶんいけますと図と式を描きながら返しました。その後もk1suxuさんは実装を続けていましたが，WAで最終的に通し切ることはできませんでした。
D
最後に2人はD問題に取り組んで，それらしき解法が生えたそうです。実装して愚直と比較するランダムテストを回すも，
6完11位でした。
day1結果
コンテスト後
この日の夜に関してはちょっと用事があったので，解説が始まったくらいのタイミングで帰ってきました。E問題以降がどうなったかを知ったのはその後です。
悪くない成績でしたが，欲を言えばEを通しきってあと1完欲しかったです。
Lについては，どうやら計算量解析が間違っていたらしく，eightくんが
とかでよいかと思います。調和級数 がlogになるのは，積分 が出てくるのがポイントであったことを考えれば，確かにという感じです。少し自分が早合点しすぎてしまったと思います。
お楽しみコンテスト
今年はコンテストがない時間に取り組むコンテンツとして，お楽しみコンテストが用意されていました。問題は全体的にCTFっぽい感じでした。
僕はwelcome以外はロリハのハッシュ衝突2問が解けました。解けたと言っても，Rolling Hashを殺す話 | PDF にすべてが書いてあったので，これを実装しただけです。こないだ苦労しながらSageMathを入れた甲斐がありました。
Good Numberはジャッジステータスや実行時間でテストケース特定を考えましたが，ジャッジがあまり安定していなかったのと最大実行時間しか表示されなかったので諦めてしまいました。
ABC
土曜日につきABCがありました。結果は惨敗。F問題のメビウス 変換というやつは，名前だけなんとなく聞いたことあるけど何やってるかは全く知らないシリーズでした。ただ，種類ごとにまとめ上げたあと適切な二項係数をかけるという方針でも解けるらしく，単純な実力不足を痛感させられました。
翌朝，k1suxuさんにメビウス 変換を教えてもらい，n次元超立方体の00...0に絵の具の塊を置いて，スライドさせながら全部の頂点をちょうど一回ずつ塗っていくイメージを得ました。次に出会ったときには解けるようになっていたいです。
day2
コンテスト
B
B問題はDPやるだけと書いてあるのでそれをします。爆速で実装が終わって9分でAC。FAが7分だったので惜しかったです。
この時点でAB以外のACが出ていなかったので，Lから見ていきました。Lが激ヤバドミノ敷き詰めパズル，Kがデータ構造構築っぽい何か，Jがたのしいパズル，Iが01 on Treeの進化版で，Kが若干可能に見えるものの，すぐ解けるものは見つかりませんでした。
A
A問題を横目で見ると，2人で考えていましたがかなり苦戦している様子でした。問題を聞いて，「外積 0かつ内積 負です」という係をしました。それをキクタ ンさんが実装してAC。
ここ再び順位表に目をやりますが，AB以外の問題をどのチームも通していないという異常事態に。どの問題を解くか決めあぐねていると，FGJKにFAが出てこれらに着手することが決まりました。
F
Fは僕が，Gはk1suxuさんが見ます。FはARC071C を見たことがあったので，キクタ ンさんがなんとなくの証明をしてくれたので，ある程度の自信をもって書き切りました。提出した直後に
直後にk1suxuさんが書いていたGが通りました。
J
さて，一段落したのでみんなでJKLを考えます。Jは結局どちらの角で曲げるかの2通りしかないので，色
2-SATライブラリを写経しているときに，val[e] ?: dfs(e)という三項演算子 の真のときの値を省略する記法に出会いました。その場では良く分からなかったのでそのまま写してACしましたが，気になって後で調べました。するとどうやらGCC拡張でこの記法は認められているらしく，ここではval[e] ? val[e] : dfs(e)のことらしいです*1 。0以外の評価値ならそのまま返す，でなければ別の値を返すということができる優れものです。ただし，評価は一度だけしか行われないので注意が必要です（が，これはむしろ嬉しいと思います）。
ここでクイズ
#include <bits/stdc++.h>
using namespace std ;
int main () {
int i = 0 ;
vector <int > a = {1 , 0 , -1 };
cout << (a[i++] ?: a[i]) << endl ;
return 0 ;
}
は何を出力するでしょうか。
閑話休題 。Lを書いていたk1suxuさんと何度か交代しながら，Jを一発で通しました。
K
その後，Kでキクタ ンさんが，元々の列が長さ再帰 をいい感じにとかやっていたのが馬鹿らしくなるくらい天才でした。バグを生みつつ爆速で実装しましたがWA。見返してみると「元々の列が長さ
L
あとはLを通し切ることができればかなり嬉しいです。2人で考察は終わっており，
車を遠くへ「ワープ」させるのは明らかに無駄（ワープできるならそこに新しい車を詰めれば終わり）
1マスの車のスライドで空白を上手く移動させ，2マス分隣り合わせたい
チェス盤を考えると，別々の色の空白を移動させるべき
これらを踏まえて，マス間に辺をはったグラフを考えて，BFSして経路復元して，swapを繰り返して盤面を構築しているそうです。
すでにこれで1回提出しており，なぜWAなのかが分かっていないとのことでした。僕も実装を眺めますが，特に怪しそうなところは見当たりませんでした。
しばらく進展のない時間が流れていましたが，残り20分の時点で，キクタ ンさんが車の「回転」 に気付きます。
#^.
.v#
は中央の車を45度「回転」 させることにより，
#<>
<>#
とできます。これを踏まえてk1suxuさんが斜め移動も許可した辺を追加して実装を頑張りましたが，回転の盤面構築が複雑で，残念ながら間に合わず。
6完10位でした。
day2結果
コンテスト後
k1suxuさんがLの実装をしていましたが，斜め移動もあることを考慮して最初の方から実装し直したらあっさり通ったそうです。考慮漏れに気付いたタイミングが少し遅すぎたと反省。
余談として，実はday1の自己紹介の時点で気付いていたのですが，高校のときの部活の先輩と偶然にも再会しました。文化祭はどうだったとか，かつての人々は今どうしているだとか，久闊を叙すなどしました。
Writer陣予想コンテスト+懇親会
day3のwriter（たち）を予想するコンテストが唐突に始まりました。スタッフの誰か？いやでもわざわざ出題するということは…？とか読み過ぎてどっちが表か分からなくなってきたので，どうせ誰も当てられないだろうということで，その場合の最適解であるところの空集合 を提出しました。
懇親会では，双子，実力あるチーム，海外の強い人，LLMなど，議論が白熱しました。中盤になって誰が何点を得たかの情報が公開され，自分が空集合 提出バトルに敗北していることを確認し，同時に単独writerであることが確定しました。
懇親会の終盤，過去の問題提供者の情報を精査した参加者によってwriterが特定され，その正体がDispersionさんであることが明かされました。直前までwriterが誰であるか何食わぬ顔で一緒に議論していた人がまさかwriterだとは思わず，とても驚きました。
day3
コンテスト
B
いつものようにBから読み始めます。問題はすぐに理解できましたが，優先度付きキューに入れる
Aは特にバグらせることなくキクタ ンさんが通してくれました。
H
順位表を見るとHがありえない速度で通されていたので見ます。0を避けるように余りを取っていくと，集合の要素たちが区間 をなすのは分かりましたが，具体的にどうすればよいかはよく分かりませんでした。そこで，day2を思い出して逆順に見ることにします。区間 の長さは変わりませんから，最後の一歩手前は区間 を考えればよいです。よって，
J
Jを考えていた2人に問題を振られたので見てみるとグラフの問題でした。こんなのはオイラー 歩道と同じような感じで，入次数とか出次数とかの偶奇か何かだけで決まるのではないかと雑なことを投げました。そのあとk1suxuさんといろいろやり取りをして，弱連結成分ごとに問題を見たとき，
が答えであろうという結論になりました。連結でなくても孤立点が存在するときにオイラー 回路が存在する場合があることを知っていた*2 ので，k1suxuさんが実装に取り掛かる前に，孤立点だけ例外処理をする必要があることを指摘しました。k1suxuさんが1ペナで通しました。
K
次に爆速で通されていたKを見るとゲーム理論 でした。局面がキクタ ンさんもたくさん手で実験していましたが，その規則性をつかんではいませんでした。
F
Kが全く分からないのでFにうつります。かの有名なAntsを題材とした問題で，各蟻の衝突回数ダイヤグラム を書いてみることにしました。
ダイヤグラム
このままの図では
線を等間隔にした図
これに伴い，x軸が曲がってしまいましたが，適切に直線の間隔を調整することによりいつでも戻れるので気にしないことにします。
さて，これにより大幅に問題が単純になりました。使うLの個数とRの個数を決めてしまうと，
上から
印がついた交点とついていない交点を分断するように，上から刀で「まっすぐ」（各糸についてちょうど1回ずつ切るように）カットすることができるか？
という問題になります。カットできたとすると，刀がLとRどちらの糸を切ったかを上から並べれば，それがそのまま答えになっています。
以上のことをよく観察すると，網が折れるまでの「前半」の段（上から
前半の段では
後半の段では
逆に，この条件を満たしていれば，上から刀でまっすぐ切れることが分かります。
ここまでくれば後は簡単で，
右下から見てまとめて計上した印の個数（図の黄色の
とすればよいです。
以上を実装して，1REの末にAC。
前に0が連続するときは最初に省いてから以上のアルゴリズム をやるというようにしていたのですが，assert(ans.size() == n); と書いてしまったのがまずかったです。先頭に連続する0を省いてnが変わっているにもかかわらず，そのままassertをしてしまいました。ただ結局これ以外にもバグっている箇所を見つけられたので結果的には良かったです。
assertつけて提出するのは，バグ発見においてとても効果的ですが，嘘のassertをしないようにだけ気を付けようと思いました。
K
最後に残ったKを考え続けます。ほとんど全チームが通しているので，実はめちゃくちゃ簡単なんじゃないかと，Bの位置の偶奇とかMの偶奇とかでごちゃごちゃ実験をしてみますが，全く合わず。グランディ数を考えると0,1,2しかないのか，いやこれは任意の局面
6完16位でした。
day3結果
コンテスト後
Kは2次元平面上の方針で合っていたようです。ただ，斜めで同じになることにはまったく気づきませんでした。こういうのは気づかないときは本当に気付かないものだと実感しました。
Fがここ1年で解いた問題の中で一番面白かったと言えるくらいいい問題だったので，チームメイトと後輩にこの感動を共有するなどしていました（そのため本記事でも，このFのパートが一番長いです）。とにかくとても気持ちのいい問題でした。
おわりに
開催にあたり準備してくださったスタッフのみなさん，交流してくださった参加者のみなさん，本当にありがとうございました。Yokohamaでは良い結果を残せるように日々精進していきます！
