はじめに
ICPCのときにかっつ君と「絶対ACPC行こうな」と盛り上がる。そのとき他にも何人居たはずだがいずこに……？
day1
例によって東武鉄道や会津鉄道を乗り継ぎ会津へ。移動中一生かっつくんと過去のACPCの話をしていた。
#ACPC2025
— olphe (@_olphe) 2025年3月21日
会津合宿の朝は早い pic.twitter.com/ekZ0ivkgXd
途中めっちゃ雪積もっててすごかった。
あいづっこ宣言を見たかっつ君が「yamadを思い出す」と言っており懐かしい気持ちに。yamadの顔っぽい広告たくさんあると思っていて、情報を募集しています。
喜多方ラーメン pic.twitter.com/lU5laZPxCT
— olphe (@_olphe) 2025年3月22日
— olphe (@_olphe) 2025年3月22日
コンテストは立命セット、kotatsugame, n_o_n_o_nと共にkotatsugame_marunageで参加。オンサイト2位
D ある行について着目したときに、最も近いものの集合はマスについて連続であり、かつその行には一塊しか存在しないため二分探索によってそれぞれが何個ずつ存在するかを調べられる。
E ギャグ
F 高度ごとにimos法
H |S|>|T'|の場合は、|T'|を全探索してTの後ろから貪欲法でT'を構築できるか調べられる。そうでない場合はTの後ろからRev(S)を取り出し、残った部分での最長の回文をLCSのようなDPで求める
kotatsugameが高難易度をバシバシしばいていて格好良かったです。終盤はn_o_n_o_nさんと考察出しながらKを考えてて楽しかった。
夕食は集団で焼き鳥や焼き豚の店に行く。日本酒の会津政宗がめちゃおいしかった。
day2
コンテストは東北大セット、かっつ、MMRZと共にthunderbirdで参加。オンサイト3位
E 文字列を1で区切った時に各区間にある0の数を持った数列に着目すると、操作1は隣接する2要素から1を引く操作に、操作2は端以外の0を一つ削除する操作に言い換えられる。数列の最大要素と総和に着目すると各操作が何回行えるかわかる。
L 1要素の追加で構築できる場合は自明に判定でき、sとtの差がでかめの奇数かでかめの4の倍数なら常に2要素追加すれば構築できる。どちらでもない場合は1要素を追加してから2要素の場合に言い換える。
終盤は全員解けそうな問題に取り組んでおり、誰かがもう1問解けると幸せだった……
kotatsugameと夕食の後、富士の湯へ、合宿参加者が割といて楽しい。
ARCはABCEを解きパフォ2800でカンスト、あまりに嬉しい……このまま橙まで復活していきたい。
ARCの後でixmelと部屋で飲酒をしていたがixmelが一瞬で寝たので一人寂しく日本酒を消費していた。
day3
朝早起きして鶴ヶ城に行く。多くの場合戊辰戦争は明治政府側の視点で書かれるが、鶴ヶ城においては会津藩視点での歴史が書かれており非常に興味深かった。見学時間は全然足りんかった……
— olphe (@_olphe) 2025年3月24日
コンテストは会津大セット、toam,ococonomy1と共にtouhokudaiで参加。オンサイト2位
B 人の配置をnext_permutationで全探索
D 行列累乗 去年一生Antimatter Dimensionsをやったいたのでうれしい気持ちに
E 包除だという主張をしていたが、toamさんによりセグ木解が提示されそのまま実装も任せた。それはそうすぎる。
G bitごとに考える。そのbitが立っている数と立っていない数を持って行列累乗
I 残す頂点を持つDPで解けるというところまでたどり着いたが、残す多角形に使える辺の条件に関する考察漏れがあり解けず……とても悲しい……落ち着いて考察を行います。
J ococoさんがある程度考察をしていたところに、ロリハで部分文字列の同一判定をすればよいと指摘をし、実装も行う。
N Nより桁が少ない数については、dp1[桁数][使用した数の種類数]=の通り数,dp2[使用した桁の集合][そのような集合を含む合法な集合のサイズ]=の通り数 を求めておくと通り数が求められる。桁数が同じで小さい場合は初めて異なる桁を全探索し、dp1,dp2を使用して通り数が求められる。Nについては条件を満たしているか調べる。
この日は様々な問題でチームメイトと考察を進める場面が多く、一番チーム戦してる感があった。
おわりに
一生擦り倒していたACPCに再び参加できて感謝の気持ちでいっぱいです。運営の皆さんありがとうございます。
