JAG模擬国内予選&国内予選 参加記

はじめに

おはこんばんにちは。 JAG模擬国内予選と国内予選に参加しました。

僕の貢献が全然ない(;´･ω･)

チーム (StaticTopYutaka)

  • Taiki0715: めっちゃつよい
  • achapi: つよい
  • amesyu: よわい

戦略

解く。amesyuは実装をしない(できない(したくない))

JAG模擬国内予選

A: やるだけ。

B: 解かれてた。なにしてもよい

C: めんどそう。

D: こうするとできるよ。枝刈りをするとよいよ。実装できないよ！achapiに投げるとAC

E: bitごとに3回で特定可能。実装をachapiに投げるとAC

F: かっこ列っぽい話をしているとTaiki君が通す。

G: log2個が通らない -> ｾｸﾞﾂﾘ上のにぶたん的なあれで行けないかみたいな話をしてたら通されてた。

H: 01に帰着。0が解けたらしい。

I: う　し　た　ぷ　に　き　あ　く　ん　笑

16位。良くも悪くもないぐらい？

EFGがかなり綺麗な問題で好き

国内予選

お菓子買いすぎた。

開始直後にプリンターが壊れる。-> 2,3分ぐらいで復帰。

A: 微妙にめんどい。1->14, 2->15 にしてmax

B: しらない

C: しらない

D: 僕は何も知らない

E: jemありをを一個買うとjemありが全部買えるのであとはjemなしと合わせていい感じにやる。ほえ～

F: 長方形領域の端点で座圧すると m^2 程度の矩形領域に分けられるのでその矩形領域の角を頂点 -> ダイクストラ。同じ列で直接移動できるケースだけあとで場合分け。実装はTaiki君に投げる。 atcoder.jp これに似ている。

G: 998なのでTaiki君に投げるとAC

H: bitDP を書いてあるが何をするんですか？になってしまった。

I: Slope Trick っぽいね～わかりません

J: にぶたんをする。ギリギリをせめてよしなにしたいね～。このライブラリないかな

19位？良くはないぐらい？Hが可能枠であることの見極めが下手だった。問題割り振りとかのそれはよかったが、序盤の滑り出しが良くなかった。(僕のAがバグった。青コーダーさん？)

4年目にして初のYokohama出場なので気合を入れます。

雑談

JAG夏合宿の概要がこの前発表された。JAG -> TUNA が連結していてとんでもないことになっている。

会津はTUNAにセット提供予定なので全人類解いてください！

ICPC 2025 Asia Taichung Regional Contest 参加記

## はじめに

おはこんばんにちは。amesyuです。今年も ICPC 2025 Asia Taichung Regional Contestに参加してきたので経緯と結果などを書き殴ってみました。来年以降の参考になれば幸いです。去年の記事はこちら↓

amesyu.hatenablog.com

チーム(aizu_C)

  • amesyu: 精進をしていないおばかさん。そんなんだから負けるんだよ。日本語が下手(練習でマシになった)。担当は幾何とか構文解析とか変なdpとか変なものが得意目で、数え上げとか確率が大の苦手。<- 紙で考察をしない&立式をせず頭で式変形をすることが多いからなきがしてきた。チーム内で唯一青だがRatedで出ていないので絶対水である。
  • noshinn: ARC天才担当。なんで一生水にいるのかがわからない(圧倒的に典型力が足りていない気がすると思うし、本人もそう思っていそう。じゃぁやれ)。水抜けたら一瞬で黄色に行きそうな感じがする。
  • lmori: ライブラリマスターで全てに助けられた。Wavelet Matrix狂祖。安定力がない気がする？

参加経緯

日本予選で爆死してしまい、悔しかったため。(ﾃﾞｼﾞｬｳﾞ) 予選と横浜(他Regionalも)、問題風潮がかなり異なっていて、謎のDに一生殺され、Eはギャグだし、Fはnoshinnが一瞬でわかったがコンテスト終了後だった、幾何は幾何じゃないし...など全てにおいて下振れをして、100...何位だっけ？忘れてしまった。

会津チームが3チーム台湾に行くことになった経緯？

会津大学内でチームのAtCoderじゃんけん(?)で行く海外リージョナルの選択権が回ってくる風潮になっていたのでまず最初にbonsaiチームが台湾に最初に登録した。aizu_3は保留したらしく、aizu_Cもできれば台湾に行きたかったので登録チームが10大学に満たないまで台湾リージョナルに登録をしておき、10大学を超えたらレジを解除することにした。しかし何故か海外チームがあんまり集まらず、7か8チームがACされ、追加募集がかかったのでaizu_3が殴り込んできた(?????)たぶんこういうことだと思います。海外チームの選抜方法の優先度は国の多様性 -> 大学の多様性 -> レジ順番であり、基本的には複数大学が通ることが難しいはずなので今回はラッキーだった。

チーム戦略(ライブラリ)

lmoriにすべてオーダーした(ほんまにありがと)。Taichung Regionalは片面印刷の25枚(同じもの×3部)のライブラリが許容されている。結構高級なデータ構造とか幾何ライブラリをゴリゴリに入れても25枚行かなかったので、深く考える必要はないと思う。フォーマットはtatyamさんのICPC notebookを活用させていただきました。自動でラベルも振ってくれるので使い勝手が良い。メモもいれることができる。

チーム戦略(コンテスト)

aizu_Cはかなり得意不得意がはっきりしているので、得意な問題を各メンバーに割り振ることを考えた。amesyuが基本的にすべての問題に目を通し(読解というよりは内容把握)、得意不得意を選別する感じ。ARCを発見したらすべてnoshinnに投げ、データ構造ゲーはすべてlmoriに投げるつもりだった。練習ではこれがかなりうまく行っていたが、本番はそこまでうまく行かなかった。(あんまりわからんかった) 全員の不得意なものとして†実装†があって、ペナ(時間ペナ)勝負に持ち込むことが筋悪だったので、完数勝負に持ち込む必要があり、ペナ覚悟で提出debug気味に特攻する戦略を取った。本番ではそこまでペナは重なることがなかったが、練習では5ペナ↑とかザラだった。

Day -??

レジにACしたので練習を何回か行った。環境がVSCode使えないらしいので(後で発覚するが大嘘でカス)vimで練習を行った。練習では他のTaoyuen Regionalとかを用いたがイマイチな結果(Bronze Awardぐらい)で若干焦り気味だった。

Day -7か-6

PCKだよ〜。あちゃぴ君と配信係を任された(希望した？)ので配信をした。配信では予選問題の解説や、ちゃんと実況をした。人としてふざけていたので好きなデータ構造発表ドラゴンとか言ってしまった。WaveletMatrixです。lmoriの影響じゃ。 PCK本戦配信はこちら。

www.youtube.com

ところでなんでPCKはTeraPadとかいう骨董品を使ってるんですかね？あと手元とジャッジ環境の環境が違いすぎてやばいので直してください(手元cygwin vs ジャッジCentOS)

Day 0

出発。去年と同じルート行き、郡山近辺でサイゼを食べた。日本最後がサイゼて...。はじめてあぷりしあを食べた。思ったよりクセがなくて美味しい。イタリアンジェラート？もかなり美味しかった。会津に置いてくれ〜〜〜

福島空港でbonsai、aizu_3と合流をした。9人集まると修学旅行感が増す。 保安検査までまだ昼を食べてない人が食べに行ったが、飯が来るのが遅くて危うく出国failすることろだった。ちゃんと予定を立てましょう。

16:30出発で、現地の19:30ぐらいについた。そこから移動 [空港第一ターミナル(A12) <地下鉄> 高鉄桃園?(A18) <HSR(新幹線)> 台中(Xinwuri)] をしたので台中につくのがだいぶ遅くなった。去年行ったのでだいぶ土地勘があったから出来たものの、最初だったら出来なかったムーブ。夜をHSR台中でマックを食べた。見慣れないバーガーを食べた。日本のマックはバーガーが潰されてることが多いが、ビッグマックみたいに箱になっていてきれいだった。バンズも違う。

そこから宿に終電で着弾。おやすみ。

Day 1

あさあさ。そこまで朝早くないので遅起をした。朝はすき家でフリスビーを食べた。何気に初めて食べたかも。そのままバスに乗ってAsia Universityに直行。適当に受付を済ませPractice Contestを行った。Practice Contestでは __int128_t が使えることを確認し、VSCodeが何故か使えることを確認した。ちゃんと書いてくれよほんまに。ML、TL二分探索をしようとしたがジャッジが途中で壊れ、何も確認できなかった。ワクワクコンテストの開始や！ 帰りにランチボックス(パン)を受け取り、そのまま食べた。夜は追加で大戸屋に酢鶏？豚じゃなかったと思うんだよなを食べた。だいぶ美味しかった。野菜の摂取不足で困っていたのでありがたい。

コンテストを控えているのでABCの順位表に驚愕しながら就寝。

Day 2

朝はっや！！noshinnに起こしてもらった。ママかな？ Day1と同じくバスで直行！。受付を済ませコンテスト開始！！以下ネタバレ含む。

序盤

テンプレートの写経をlmoriにやってもらっている間、Aがnoshinnが読むと簡単らしいのでテンプレート書き終わってからAC(00:09)。何も覚えてないけどE(00:21)。Mがやるだけなのでlmoriに実装を丸投げし、M(00:30)。Fを見ると適当にでかい区間で良くね？になるので少し考察漏れをカバーしてもらいながらF(00:52)。

中盤

BIJはすべてほとんど自分が考察/実装をした。Bペナ2、Iペナ1すんまへん。

  • B: バスは一回だけで良い。制約を眺めると歩く速度y < バスの速度xなので(まぁなくても変わらんが) バスが自分より後ろのものしか乗れない。また、各バスについて、乗るといつまでにLに到着できるかを区間に見立てるとバスの開始地点でソートしたときと到着時刻は単調増加になってないといけないので包含を省く感じで不要なバスを省き、省いたやつで各クエリで lower_bound するとAC(02:18)。

  • I: 考察5分、凸包やるだけ。実装激重。と言ってもライブラリ貼るだけなのでlmoriとペアプロしながらライブラリを写経し、convex hull、円と直線の交点を求めるやつを書いてもらった。 凸包が(0, 0)を含んでない場合、自明な上界(πr2 / 2)が達成でき、それ以外の場合は凸包を構成する線分(直線)のみを考慮すれば良い。N=1で1ペナ。しょうもない(03:56)

  • J: 同じ値の連続部分列を区間とみなすと、その区間数はNで抑えられるのでよしなに管理するとO(NlogN)とかになる。BITを写経してもらって、自力で区間加算に対応させた。変なバグらせ方をしたがすぐに治って、提出するとAC(04:42)

終盤

中盤の時からLがARCっぽく、noshinnにやってもらっていたので全ツッパしてもらった。Kもほとんど考察が終わっていて、実装できる状態だったが、流石に20分ぐらいで合わせる勇気はない。Lはサンプルが合わずにend... 7完でフィニッシュ。やはり実装速度が課題だった。amesyuはC++に完全移行して実装が下手で(pythonだからうまいというわけではないが)、noshinnはいわずもがな(おい)なので来年までに実装力を鍛えていこうと思った。終わった後に順位表を見ると驚愕。bonsai、aizu_3強すぎだろ。9完て。あでも考察終わってるやつか...届きそうで届かなかった。

結果

ABEIJKM 7完の29位でSilver Awardでした。playoffはおそらく厳しいでしょう。でもなんだかんだSilverなんだと。下振れでもないし上振れでもないぐらいでなんとも不完全燃焼で終わってしまった。来年リベンジだな。今年は他の会津勢を全力で応援します。

順位表

切り替えが早いのでお楽しみタイム！ 去年はケンタッキーでバーガーを食べたが、チキンを食べ忘れたので食べた。これがまぁうまい。日本のケンタッキーはジューシータイプだが海外はカリカリらしくてずっと気になっていた。後謎のQQball(タピオカと同じ粉で作るさつまいものボール型お菓子)を食べた。もきゅもきゅで美味しい。

日本のケンタッキー(実はバ先)

これ食べていたらチームメイトにおいて行かれ、食べ終わって宮原眼科(アイスクリーム屋)で合流。去年も食べたがやっぱり美味しい。

夜市で食べた何故かみんなが離れていく臭豆腐君。美味しいんだけどなぁ。匂いと見た目で損をしている。

食いすぎじゃね？まぁデブなので。ふふん。

夜市から帰宅途中にクレーンゲームをした。さすまたちいかわが取れたが、なんかクッソ汚かった。後でまとめて服と一緒に洗濯した。

宿についた後、味覚が終わっているから行けるとか言われてまずいコーラを飲まされた。コーラから誇張なしの歯磨き粉の味がしてビビった。チョコミントとかそういうレベルではないガチの歯磨き粉

Day 3

観光Day。去年と全く違うところだった。朝の弱い頭によくわからない歴史の話をされバスで爆睡をし、次降りたときには宮原眼科にいた。また？まぁこんなのなんぼあってもいいですからね。その後ありえない量の昼ご飯をたべ、謎の歌劇院と謎の公園で懸垂とか逆上がりをした(???)まじでなんだったんだあれは。よくわからないまま観光が終わってそのまま宿に戻った。宿に戻る途中でタピった。台湾はタピオカが根付いていて、いつでもタピオカを摂取するJKになれる。

この黒糖ミルクティータピオカが美味しすぎて日本に帰った後に業務スーパーで1kgの黒糖と冷凍タピオカ、タピオカストローを買ってしまった。さて、お家タピパーティーでもするとしますか。

夜飯はaizu_3のei1903先輩と一緒にビールが飲める居酒屋を探そうとしたがよくわからず、結局屋台で買ってビールをコンビニで買うことにした。このとき選んだ屋台がおおあたりで、店主が日本語ペラッペラで300NT(1500円程度)でありえない量の一口唐揚げ、骨付き唐揚げ、謎、さつまいも、むらさきいも、などの揚げ物を買うことができ、優勝した。台湾ビールはかなりスッキリしていて、揚げ物を流し込むのに最適。

Day 4

帰国。ガチで朝早くて5:30出発だった。そのまま乗り継いで桃園空港でバーガーキングを食べた。店内にしたがトレーがもらえず、直大はうまいをできなかった。珍しいことにセットのドリンクでMountain Dewが選択できたので選んでみた。最近身内でブームになってる。その後特に何もなく離着陸して福島空港に到着し、気温が20度下がった(絶望)

夜ごはんはくら寿司に行ってあほをしました。後で変えられるやろ〜の気持ちでいたら変えられなくて爆音で到着音ﾆｪｰﾃﾞﾍﾝｸｼﾞﾝﾌｿﾝﾊｰｰみたいな音が流れ宇宙猫になっていた。

会津に変える途中、猪苗代あたりで雪が振っており、半袖を殺しにかかってきてた。会津は降ってなかった。なんだかんだあり、帰宅に成功！

まとめ

大事が起こらずに無事に日本勢が帰宅できたのが一番です。

???

精進が足りてないので (Sum of (Difficulty of Unique AC)^2/(1643^2)) + (Rating - 1643) >= 800 を目指すことにした。 年末までに出来なかったら焼き肉奢らないといけないらしい(値は要調整)。

Playoff選出方法について

※筆者はルールについて理解していません。去年の順位変動からの憶測です。 https://icpcapac.solved.ac/2026 に優先度順が乗っています。

現在のTaichung Regionalに参加した日本勢の順位は以下のとおりです。(Seoul Regional前)

  • bonsai: 10位 (JPN#1で優先されている状態なので他Regionalが終わると下がる)
  • aizu_3: 52位
  • y_1: 62位
  • Akai_Koibito: 80位
  • Tsukuyom1: 104位
  • aizu_C: 109位

これから順位が変動する要素として以下のようなものが挙げられます。

  • National Taiwan University(std_absなど)が他Regionalで優勝する(コレでRegional内部の順位が3以上上がる可能性がある。)
  • bonsai, aizu_3が横浜でいい順位を取ると高いほうが優先されるんですか？わかりません
  • 他Regional参加者がどちらの順位を採用されるかでmerge後の順位が変動する？

コレを加味するに去年は枠が65位までで、y_1まではほぼ確定？(下手なことは言えない)でAkai_Koibitoはまだ可能性がある状態。Tsukuyom1と僕らはよっぽど噛み合わないと難しい状態。

最後に

ICPC運営の方、本大会を開催していただきありがとうございます。日本人チームの方も情報共有ありがとうございました。

JAG夏合宿2025参加記

JAG夏合宿2025参加記(amesyu視点)

おはこんばんにちは会津大学のamesyuです。 JAG夏合宿2025に参加したので日記がてら色々書き殴ります。

ICPCチーム(aizu_C)

  • amesyu: 担当なし(典型担当らしい)
  • noshinn: 天才担当
  • lmori: ライブラリ担当

国内予選はABCD激遅4完で余裕で落ちてしまったので昨年と同じく台湾Regionalに参加することに。 予選との相性が悪いのか頭の出来が悪いのか(後者)

Day1(有志セット)

流石に三年目となると見慣れてしまったオリンピックセンターだが、迷子になりながらも到着。適当に説明を受けてコンテスト開始〜。以下問題の感想と事件など...

A: 戦略として僕は見ないのだが英語を誤読していたらしく英語を少し読んだ。読めなかった。(無能)

B: 全然読んでない

C: 制約にフローと書いてあるね！ -> 典型っぽいものに帰着できるがそこがわからないので早々に撤退(割と正しかった)

D: 文字列くっつけてSuffix Array取ったときの転倒数。こんなの解けるのか？と思いつつ実験するとぽいものが出たのでエスパー提出 -> WA。解説みてなるほど。

E: 幾何。幾何担当としてやりたいな〜と思うが英語が読めなかった。解説で日本語訳を聞くと割とそのまんまだった。

F: 本質(行きたい方に降りれないときは一旦逆行って上に行くで良い)をチームメイトに渡したらACが帰ってきた。つえ〜

G: noshinnが通した。何も知りません。

H: 2つのパスに対して同じものの個数の列があればRollingHash + BIT上の二分探索でとけるな〜Moにしようと思ったが２つのパスをMoにすると4次元になり爆散。解説で知見を得た。

解法とは全く関係ないが、ABC405-G のノリで列を平方分割するとlcpを求める部分をsqrt(N)にする代わりにMoのスライドがO(1)になるな〜と思うなどした。

I: 順位表を見ると解かれていなかったので見ていない。

J: I hate interactive probelm.

K: 問題文にstackが出てきたら区間dpらしい(え?)

L: [N / ij] = [[N / i] / j] なので同じ値のところはまとめて愚直を書いてランテス書くと1sぐらいで終わったので提出するとTLE(え〜〜〜〜〜〜) いまだ不明。配布されたケースためしてみるか...

コンテスト終わって一生Lが通らないことを喚いてしまった。弱い 夜はカレー＋ご飯を食べた(?)

Day2(JAGセット)

朝なにしたっけ。覚えてないのでコンテスト内容

AB: 見てない

C: 幾何〜〜初手2手ぐらいしか凸包の外側に置かなくて良いんじゃない？と思ってサンプル２個目を適当な初項、公差2で探索するとそれっぽい答えがあったので方針を考えた。凸包に含まれる点でP[i + 1] - P[i] と P[j + 1] - P[j] の外積が正であるような区間の最大のところを取っていきたいお気持ちになるがPC奪ってまで取る問題じゃない気がしてほかを考えた。

D: 2連幾何？？？端点は簡単に取れるんだけどグラフに帰着させるときにコーナーが多くて幾何ゴリ押しがつらそうだった。解説見るとかなりきれいですごい。

E: グラフと書いてあるけどよくわからない

F: とりあえずf(S)を表す状態が小さければdpで解けるのでいい感じの不変量を探してくれ！とnoshinnに投げると帰ってきたのでdpにしてもらった。良いチームワーク

G: 考察/実装すべて担当したけど言ってることはわかるけど実装をバグらせまくってダメ。

HI: 読んでない

J: 2-SATだよね〜2-SAT書くの...?をした。imoriに実装をさせたが良い実装をしてくれていてよかった。途中勘違いをしていたらしくて(交叉ではなく直角かどうかしか判定していなかった(う 笑))

K: 先頭M個しかいらないんだけどう〜〜ん。実力がない

L: Pass!

かなり実力不足を突きつけられる結果だった。それもそのはず精進をしていないのである。参加記を書きながら精進しています

Day2(懇親会)

謎のDay3Writer当てコンテストが開催され、勝者うるずにゃーさんにhintを渡した気がする(?)僕戦犯じゃん。 それにしてもDispersionさんがすごすぎる。JAGに参加したらたくさん原案なげたいね〜〜〜(soloは確実に無理だが...) 海外Regionalに参加するチームを探し回って飯を食べまくった。ポテトがかなり美味しかった。

Day2(ABC)

ABC出た。負けた。精進しましょうね

Day3(Dispersionセット)

AB: 見てない

C: 全方位木DPだろこんなの(違う)

D: 最後コレに取り掛かってもらったが惜しかったっぽい。あまり読んでいない。

E: 自明に分割が確定する部分以外Aa型を残してそこを貪欲に当てはめていく感じにはなったが最大化はA aが存在するときだけAaを選んでそれ以外はA, a -> Aaを選択、最小化はよくわからなかった。この問題好き

F: 1 2 1, 1 3 3 1みたいなのができるな〜と思ったので先頭から操作しながら更新していくようにやってみたが普通に間違っていた。この問題も好き

G: ﾌｧ-

H: すみません2ペナしました。[R/2]を選ぶのがいいらしいんだけど気づかなくてL - 1 + x のxを探してRが0にならない上界を選んだら0割したりで散々

I: ん？適当に折ったあとに2つの操作できる平行があるじゃダメなのか？(適当すぎだろ)

J: よくわからなかった。

K: 区間になるよ！と言ったら通してくれた。

ほぼ最下位でだめですね〜〜... D, E, F, Jあたりが惜しいところまで言っているが細かいところが詰められていなかったり、各々が別々の問題に取り組んでいるのでチームとしての戦略も考えさせられるセットだった。 Day1, 2, 3ともに最後に2~3問の問題がWAで印刷DebugしてPCを取り合うだけで思考が凝り固まっている気がしたのでもっとペアプロを取り入れたほうが良さそうに感じた。

おわりに

JAGスタッフの皆さん、有志セット作問の方、楽しいセットをありがとうございました。最近精進できていなかった中、良い刺激となり競技プログラミング意欲が湧いてきました。2年前は緑で参加し、夏合宿後に急激に伸びて入水したので、初心に帰って精進しようと思います。

ACPC2025参加記

はじめに

おはこんばんにちわ。03/22 ~ 03/24でACPCを開催したの参加記(開催記)+会津セットWriter裏話的なのを書きました。各コンテストページは以下のリンクです。バチャ＆upsolveお待ちしております。

Day1立命館セット

Day2東北大セット

Day3会津大セット

Day0

去年のRUPCの反省をもとに問題セットを準備しました。問題文校正に重きをおいてワクワクコンテストにならないようにしました。特ににストーリーが付随している問題の問題文校正が難しかった。

Day1(立命館セット)

朝早め()に起きていざ会場へ。去年のRUPC2024で見かけた人や有名人を生で見られて感動！適当な会場のルール等を説明して早速コンテストへ。Day1はAtCoderのレートが近い人同士で組むことになり、ごりちゃん(prd_xxx) + のしん(noshinn) + 僕(amesyu)(敬称略)のamenogoriで参加しました。以下感想。

A: 式変形をしなくても、その濃度の砂糖水になるために必要な水の量 or 砂糖の量を持つと溶ける(解ける)。

B: うお〜ライブラリで殴れない...解説がかなり綺麗でした。

C: O(N2 logN)もつかな〜と投げたら通った。前から貪欲

D: みてない

E: のしん君がSubtreeの定義を誤読していたのをサポート+ギャグを解消

F: O(NW + W3) を提案してのしん君にぶん投げ。

G: ほえ？

H: S側の中心しか探索しない嘘を投げ続けましたし、答えの最小値を求めてた。サンプルが最小値=最大値で困った。

I: 解法が秒でわかるけどめんどくさすぎる+面白い

J: memonumo

K: 全くわからなかった。

L: めんどくさい解法(HLDとか木上のMo)で解けそうと話してたらごりちゃんが天才を投げてた。感謝。

最終結果はACEFLの5完で全体的に調子が悪かった気がしたが、難易度帯がちょうど良いものが多くて歯ごたえがあるセットだった。運営作業をしていたら人がほとんどいなくなってしまったので残った人で夜ご飯を食べた。

Day2(東北大セット)

遅刻しました。ふえ〜〜〜〜〜？Contestant用の飲み物を買っていました(言い訳)

名札ガチャで決まったチーム"会津若松駅を庇い石にされてしまったあかべこ"で参加をしました。以下見た＆解いた問題の感想

A: 見た目がすごい綺麗。解けるわけもなく...

E: 0を括弧、1を適当な要素としてみると操作は[11 → 1](連続した要素を一個にする)、[010 → 1](中身が要素のみな括弧を外す)のような操作に該当して、0を開き括弧閉じ括弧どちらに割り当てるかになる。0が十分に少ないときは良い構築が簡単にわかるが、0が多すぎるときに0をどう割り当てるかが重要で実装を破滅した。0と()って似てるよね。

G: 幾何なので気合を入れる。どうせこんなのはConvex Hull Trick!と思ったら全然違った。だがアイデアとしてConvex Hull Trickの実装(追加する直線の傾きが単調増加(減少))を考えると自然に導出できる。おもしろい。

M: K≦2解けなくて何コレ...となっていたが冷静になると0~9いずれかになるだけだった(コンテスト後)。

P: 本当に簡単枠ですか？。グッと睨むとFrog1とわかる(え)

Q: 本当に簡単枠ですか？？。いもすやるだけだった。簡単です

R: 本当に簡単枠ですか？？？。括弧列 ( , ) を1, -1対応させてprefix sumが0以上、suffix sumが0以下になっている+総和が0。最終手番が後手に回った場合は負けるのでそれ以外で考えると、総和が1 or -1を維持したいかつ他の条件を満たせるならばOK(すごい雑)。こんな考察しなくても良かったらしい(˙◁˙)

解けたのはPQR + L(何も見てない)の4完でした。EM(G)とかが可能枠だったが、詰め切れずに解くことができなかったので反省。こういうタイプのARCあるあるなのでARC精進をするべきだなと思った。この後何をしたかは忘れた。

Day3(会津セット)

丹精込めて作りました。Writer, Tester感想を書いていきます。

A: 文字列問題。最後まで探索するの忘れがち。ACPCはAizu Competitive Programming {"Camp", "Contest", "Club"} などがあるらしいですん

B: nPr全探索が珍しい。

C: 原案+Writerです。(>w<)この顔文字を参考にしました(???) 元々磁石のストーリーがありましたが、磁石の大きさとか色々不鮮明なところが多すぎてやめました。ちゃんと詰めないとサンプルが微妙に弱くてWAを吐きます。

D: ACはしました。他Testerのパスカルの三角形の話に脱帽。

E: 解けなかった。

F: 景品が動き出さないでください！原案が出されたときに脳裏に浮かんだのがキャトルミューティレーションでうしさんが吸われてゆく映像でした。

うし

G: 原案+Writerです。元々ORで, OR Convolutionが解法でしたが、O(logNlogK)解法がTesterから提案+自分が簡潔な実装を思いつき微ギャグ落ちしたのでXORに変更しました。(N+1)倍してXORするやばいバイバイン。

H: むずい。u→vの辺の個数が調和級数で抑えられるので愚直に辺をはってSCCするTester解を書きました。最小素因数が頭良い〜

I: 原案+Writerです。幾何。対角線が多角形に完全内包されているかの判定が本質で、完全に外部に存在する場合を忘れる[WA]。操作で二角形を作ることができないので回避しない[WA]などとコーナーが多めでした。解説に書いた各対角線がO(N2 logN)で判定できるものはYukicoderに投げる予定です。どうやらO(N2) でできるらしい？

J: 原案者がSuffix Automatonとかいう未知を投げていて驚愕。勉強します。禁止文字が無いverの異なる部分文字列の"個数"はLibrary Checkerで既出でした。

K: う〜ん不可能！精進不足

L: Writerをしました。実装によっては定数倍が重くてTLを変えるなどをしていたが、異常定数倍高速化が早くて2sになりました。

M: 原案をしました。あの見た目で落ち着いた解法になるのが好きです。計算量証明などもしっかりやった。ケースが少し弱くて強い貪欲が通ってしまったのが心残り。In: 431101440000, Out: 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 をaftercontestとします。

N: 精進不足2。こういう添字ごちゃごちゃは僕には無理。

結果はkotatsugame_arigatouチームのみが全完。重大なClarも無く、完数の傾斜も緩やかで悪くないセットだったと思う。最初の方はずっとジャッジルームにいたが、後半はContestant部屋でkotatsugame_arigatouチームのIのWAをニコニコしながら眺めるなどをした。

おわりに

3日間お疲れ様でした。特にオンサイトの方は遠くからこんな†秘境†|会|津|大|学|まで足を運んでくださり感謝しています。様々な方と交流することもできて最高の会津合宿でした。作問もとても楽しくできたので来年以降会津セットを提供する機会があればしようと考えています(一部員の意見ですが)。

ICPC 2024 Asia Taichung Regional Contest 参加記

これは何

この投稿は Aizu Advent Calendar 2024 3日目です。リンクはこちら

あらためて

みなさんおはこんばんにちは。amesyuです。 11月16日 ~ 18日に行われたICPC 2024 Asia Taichung Regional Contest に参加してきたので参加記(旅行記)を書きました。 来年以降で参加される方の参考になれば幸いです。

チームについて

チーム名ChatGPT-5、チームメイトはamesyu、noshinn、nyuminyusupeでした。Atcoder色は青水水でおそらく参加勢でかなりレート低かった。

参加理由

日本予選で爆死してしまい、悔しかったため。

Day 0

  • 8: 00: 集合。車で福島空港まで。
  • 10:00: 到着。変なもの持ってないのでお荷物検査はAC。
  • 12:00: 搭乗。12:40にTAKEOFF。
  • 15:30(日本の16:30): 桃園国際空港第1ターミナル到着。ももえんじゃなくて、たおゅえんらしい〜。初めて時差(-1h)を感じた。あとスマホのシャッター音がなくなった(?)。降りて真っ先に2万円ほど台湾ドルに。朝以外食べていないので空港内のフードコートでお昼を食べる。(ここからは台中に移動するので台北がコンテスト会場だったりすると乗るべき電車等が違う可能性がある。)

なんとも言えない顔のamesyu

食事(コーラ多くない?)

  • ??:??: 時間を忘れた。地下鉄の空港第一ターミナル駅(A11)から高鉄桃園駅(A18)まで移動。ようするに新幹線の駅まで移動しています。地下鉄は飲食禁止で、罰金があるので注意。この後も鉄道ちょこちょこ使うのでICカードを購入しておくことをおすすめします(200元で100元が入った状態でもらえる)。
  • 18:50: HSR(新幹線で)で桃園から台中に移動。2000円ぐらいでした。自由席と指定席であまり値段が変わらないので指定席でも?
  • 19:35: HSRの台中駅=(在来線のXinwuri駅？)着。降りてホテルの最寄りの在来線の台中駅に移動。
  • 20:00: 晴れてホテル着。夜はコンビニでよくわからない辛い鍋っぽい何かを買って食べた。今考えるとなんちゅうもの食べてんだ。ホテルで一番衝撃的だったことが、トイレが紙を流せなくて、ゴミ箱に拭いた紙を捨てる形式だった。体力を消耗したくないので睡眠。

Day 1

HSRの台中駅でバスの送迎があるので移動した。朝はすき家。味噌汁おいしー

なんの変哲もないすき家

  • 12:00: 受付を済ませ、あひるを受け取る(???)
  • ??:??: ルール説明、practice contestが開始。環境はUS配列キーボード(謎に漢字がある)、使えるエディター等は公表されていたのでVSCodeを使うことにしていて、環境の使い方(ディレクトリ構成)の共有、プリンターの確認等を主にした。なんやかんやで写経練習とかしてたら1時間経っていた。コンテスト会場(大学)のトイレも紙が流せないタイプかつそもそも紙がなかったので困りかけた。紙は買っておくことをおすすめします。LunchBoxを受け取って帰ホテル。
  • ??:??: LunchBoxのパン食べたけど小腹がすいたので現地のケンタッキーに行った(ケンタッキー店員)。え〜おいしかったです(それはそう)。明日が超絶早いので睡眠。

LunchBox(左)とケンタッキー(右)

Day 2

朝マックでした。送迎で移動。諸々の受付、荷物預けてコンテスト開始！

コンテスト

開始後は問題を読むのを任せて、環境整備、テンプレートを書いた。

Aやって(雑)と言われたのでAC(5min)。Bも読んでくれていたので、誤読がないように一緒に読み合わせをしながら無難な二分探索でB: AC(16min)。E: AC(34min)、なんか通されてた。なにも知りません。Eを実装してもらっている間に、Dを読み合わせをすると実装が微重だったので、他の考察をしながら実装してもらっていた。D: AC(67min)。

順位表を見ると、M, Cあたりが通されていることがわかったので、Cを考えることにした。Mはやるだけだったが、細かいところが面倒なようで、提出デバッグ風味な通し方をして通してもらった。E: AC(?min)。Cは二次元分をbitで持つとN<=12でO(N2 × 22N)あたりで解けることがわかって、何も考えずに提出 -> TLE〜。最大ケースを渡すと15秒ぐらいかかるので異常高速化バトルの開始ｨ！。え〜状態数そんなないじゃん。-> C: AC(?min)。とコンテスト中に通せたのはここまで。以下ごたごた。

順位表を更に見るとH、I、Fあたりが解かれている。F、区間篩かぁ〜んで肝心の数え上げは？しりません...(愚直でよかったらしい？ﾓｯﾀｲﾅｲ~)。H、数え上げ僕できないんですよね〜noshinn君に投げる。O(Nmin(N,T))で解ける話をして、そこから何も発展せず...。I、あぁTrieやるだけですね〜え？ライブラリにない...?はい空で書きます。書けませんでした〜終了〜。終わった後10分後ぐらいにIがほぼできて、後30分あったら通ってたかもしれなくてちょっと悲しみ。途中休憩所でもぐもぐタイムしてたらなんかりんごジュースかけられました(not故意)

  • 終了〜おつかれさまでした。最後に僕はChatGPT-5なのでimport sysが敷き詰められた謎のファイルを生成して講堂に移動。
  • Yes/No開始！。ｽﾞﾗ〜(110teams)追加提出はなかったので祈るしかなく、なんやかんやでSilverAwardでした。Bronzeすらもらえると思っていなかったのでもらえて嬉しかったですが、日本人勢では最下位だったのでなんとも言えない気持ち。
    日本人順位表

こっからは観光part〜。夜市がとても気になっていて、日本人チームで行くとのことだったので同行させてもらいました。AとCのAC風船もって改札入ろうとしたら取り上げられてしまった〜〜〜。tokusakuraiさんが眼科行きたいと言ってて、眼科ってなんだ...とついていったらアイスクリーム屋さんでした。有名らしいです。その後夜市に同行して臭豆腐を食べました臭かったです。飲み物が欲しくなって甘い麦茶を買って飲んでいたら迷子になりました。え〜〜。Google Mapを頼りながらなんとかホテル着。睡眠。

激ウマアイスクリームと臭豆腐

Day 3

シティーツアーですね。同じく送迎があるのでバスに乗ってGO。どこに行くのか... HOHOCHAという紅茶工場で一生コンビニで目にしてた謎卵を紅茶と一緒に食べた。紅茶をお土産に購入。

HOHOCHA

移動してSumMoonLakeでボートに乗った。歴史があるらしいが、よくわかんない！。最後にめちゃくちゃ豪華な昼ごはんを食べてシティーツアーEND〜

よっしゃ帰るぞ〜となるが、便が7:40で激朝で、ホテルを取っていないので空港野宿です。無料ラウンジで土曜に参加していなかった分のABCをチームメイトと走った。負けた。寒かったが気づいたら寝てた。noshinn君によく寝れるなとお褒めの言葉をいただきました(いいえ)。

空港ラウンジ(無料)

Day 4

帰るぞ〜〜〜〜〜〜〜。 はっぱ(紅茶)は荷物検査引っかからなかった。空港職員にお茶って野菜じゃないんですか？とかいう意味わからんことを聞いてしまった。

終わりに

ICPC運営の方、本大会を開催していただきありがとうございます。また、日本人チームの方(特にkotamanegiさん)、情報共有ありがとうございます。とても頼りになりました。

Atcoder入青までにした精進

WAの化身から卒業したamesyuです。ABC377で入青したのでためになった精進方法などをまとめておきます。
初参加から2000日経っているらしい。大学入ってから推移がy=sqrt(x)からy=xレート推移になってる。

1. ABC200~ABC300のD埋め

このツイを見かけたのでやることしました。身内何人か集めて一緒にやってました。もともとある程度埋まっていたのもありましたが、7/5から始めて大体一か月で終わりました。200~300あたりは実装問題が少なくて、純粋なアルゴ問題が多い印象でしたね。その後E埋めるをしようとして破滅！やります...

2. ABC300~ 青以下

基本的にはなにも見ないで解きますが、1時間見て考察が進まなかったら解説は読むようにしていました(ABCの時間内に解けるかどうかを目安にしています)。8割方自力ACすることができましたが、ちょこちょこ緑でも解けない問題があって頭をバグらせていました(そういう問題は解説を読んでもよくわからないことがあったので解けている身内に助けてもらいました)。

3. ICPCバチャ、埋め

Atcoderではないですが、ICPCまわりを軽く埋めていました。最近はやりの実装重めの問題に対する耐性ははICPCをやると付きます。肝心のICPC予選はよくわからない構築&実装爆発で見事爆散しましたが(^~^)。リベンジ台湾Regionalも近いのでICPC埋めは続けて行こうと思います。

ところで僕が大好きな幾何問題がICPCにはたくさんありますが、Atcoderはこの風潮を輸入してくれませんか？大概実装激重ですが...

4. ARCはUnratedで出ます！

僕は天才ではないのでARC,AGCは基本unrated出ていました。爆死が怖いというのもありますが、ARC特有の構築と数え上げがあまり得意ではないのが大きいです。黄パフォ相当数回逃している気がしますが知りません。我こそは天才と思う方はratedにしましょう。

5. 作問

自分は作問をするときに最初に登場させるアルゴリズムを決めてから問題文やストーリーを肉付けしますが、これをするにはそのアルゴリズムを完全に理解する必要があるのでいい感じのアウトプットになっています。また、作問をするときは必ず証明をするので二重にアウトプットができて定着が捗ります。

まとめ

自分はあまり黄色以上の問題が解けることがなくてパフォが良くも悪くも安定して水～青で爆勝もなくてバグ負けもなく、レート推移がめちゃくちゃ直線でした。1個目の精進方法(200~300DE埋め)が典型をまんべんなく勉強できてバグ負けをなくすことに繋がってレートを確実に上げるために役立ったと思います。一度も冷えなかったレートと現在レートとの差が36で小さいみたいです。(差大きい人で200ぐらいあるのでだいぶ小さいほう？)

https://tarareba.onrender.com/result/amesyu/

余談1

Atcoderのプロフィールの画像動かしたいな～ってapng貼ったら動きました（笑）

Atcoderではあまり意味がない...。Yukicoderもごちゃごちゃしたら動いたので動いています。みなさんも動きませんか？ぐるぐるぐるぐる～

余談2

最近Arch LinuxでWeztermを使っていると激重になることが多発していて困っています。解決方法orおすすめのターミナルあったら教えてください。

余談3

ACPC2025を開催します。たぶんおそらくmaybe作問をするのでぜひ参加お願いします。最近作問欲がかなりあるので時間があったらYukicoderで単独コンテストなども開いてみたいですね。その時は参加していただけると喜びます。ここで問題です。

- MulDiv-Query

長さ 2N−1 の文字列 S が与えられます。文字列 S の奇数番目は 123456789 のいずれかであり、偶数番目は */ のいずれかです。 Q 個のクエリが与えられるので順に処理してください。
クエリは以下の三種類です。

  • 1 p x: Sp の値を x に変更する。この時、 p は奇数である。
  • 2 p c: Sp の文字を c に変更する。 Sp=c の時は何も行わない。また、 p は偶数である。
  • 3 l r: 文字列中に含まれる * を掛け算、 / を割り算とした時、S[l:r] を計算した結果を 998244353で割った余りを出力する。この時、 l,r ともに奇数である。すなわちS[l:r]は数式として解釈可能である。

これ自体はN,Q<=2e5で水中位ぐらいだと思っていますが、演算子+-とか追加したり全体が数式として解釈可能な範囲で数字が突然演算子になったりしても解けると思います。実装激重ですが。気が向いたらYukicoderにでも投げようと思います。

 

RUPC2024参加記

はじめに

WAの化身ことWAmesyuです。RUPC2024にオンサイト参加、Day2のWriterをしてきたので参加記を置いておきます。

Day1

会場が滋賀ということで朝っぱらから新幹線で長旅(三時間)をしました。早起きつらい。南草津着で昼を食べてきゃんぱすーに直行。

立命館セット

A: やるだけらしいです。チームメイトに投げました。

B: O(N2 + NQ) が通るのでは？っという話は投げたが108で通らないﾖｼ！(よくない)をしてしまった。Moったいない。制約メタ読みで(値は不変)からMo'sは見えていたが後回しにした。AOJはコンテストでもPythonのTLが2倍伸びてるらしく、試してもよかったなぁ。

C: 見た目ダイクストラ。辺の張り方を気をつける。

D: DはDPのD。実装てこずらせて解けませんでした...

E: 素数はいい数。素数砂漠の最大長がいくつかわからないので1000ぐらい取っ て区間篩をやったが過剰実装になってしまった。

F: おもしろい。操作順が必要で、値が変わるような操作回数が少ないことに気を付けていろいろやる

G: 実装が重い。なぜかWAが出た。

H: 手つけられなかった。にむ～

I: 幾何好きだが、やる時間がありませんでした...

Day1コンテスト後 - 懇親会

Day1の問題について駄弁り＆世間話をしながら歩いて店までいってラーメンを食べた。チャーシューがめちゃうまくて汁まで完食。戻った後はシャワー済ませてABC(unrated)。途中でデザリングが切れてスマホでデバッグしてE通してた。 ABCは爆死気味だったが楽しかったのでﾖｼ！(よくない)

Day2

起きたら八時で全員起きてた。みんな早起き。開始まで時間があったので数人で近くのいい感じのカフェでエレガントな朝食を食べました。えすぷれっそおいしー

会津セット

戻った後はClar対応の準備をしてました。Twitterを眺めながら開始まで待機。スタート後一気に静まり返って怖かった。以下実況。

最初Lなんすね～ とっつきやすいというか数え上げ典型なのでまぁそれはそう。次がB、H同じぐらいにFAがでました。

ここまでは予想どうりだが、ギャグのCが全然解かれない～にたにた。次FAが出たのがA-E-NでNがかなり早くFAが出た。これはluzhiled先輩のファンですね。

M-J-K-M...とそこそこ高難度な問題のFAが出てきてさすがですね～をしていた。Iが中難易度枠ではあったがなかなかACが出てこない～何！？がWriter陣で話題に。問題文が堅苦しすぎて直感的にわかりずらいとは思いました...。この辺でギャグCのACを確認。ごめんなさい。ここから続々Cが生えてきました。

ここからFAはあんまり生えなくて開始から2時間後、O-Dが流れ込んできた。 Oが原案だったのでACが生えてﾖｼ!

結局FGのACがコンテスト中に出なかった。

Writer裏話&余談(原案のみ)

B、H、Oの原案でした。

B: String Puzzle、原案時はスコアの定義が変でLiCiaoTreeが必要だった。スコアの定義で必要なデータ構造が変わってくるので面白かった。

BはBonus!のB (？)

Aを構成するときのスコアの定義を"Aに含まれる長さK以上の文字列の個数 - Aに含まれる長さK未満の文字列の個数"とする。
スコアの最大値を求めよ

H: 一時期next_permutation自体を実装できますか？→できませんみたいな話があって、じゃあcombination実装させるかみたいな発想で原案ができたが、dpになった。combinationをメモ化再帰で実装している方も見かけた。

O: 実はABC292Fのパロディー問題 atcoder.jp 任意の点群に適用できるのでは？→展開図とかいいな～で原案が立つ。 そのあと考えてたらあtenkaizu、部分文字列としてaizu含まれてんじゃ～ん(^^)になって愛着持ち始めた。

いろいろあって作業は難航を極めたが何とかなった。 公式解説として投げた解よりより効率的な解法が二種類ほどあるので別で記事を書こうと思います。

ビジュアライザー視覚的に興奮しました。

？

  • 雨と知っていたが傘持ってこなかった(´・ω・｀)
  • AOJ、コンテストでもPypy3は2倍、Python3は4倍TL増えることを知った。
  • AOJにNimがなくてすみません。追加するんでしょうか？
  • 終電に乗るという実績を解除した。

謝辞＆完走した感想

RiPProの皆様、RUPC2024を開催、運営してくださりありがとうございます。twitterで見かけるような方と交流できて楽しかったです。普段見ないような問題(特に幾何)があり、問題を楽しむことができました。

p.s. AUPC2024が夏にあるかもしれないらしいです。続報をお待ちください