JAG 夏合宿 2024 参加記

はじめに

hint908 といいます。AtCoder 黄色です。橙が見えてきてほしいのですが、8 月の 4 週連続 Rated でレーティングが 3 しか伸びませんでした。横浜までにもうちょっと積んでおきたいです。 今回は JAG 夏合宿 2024 の参加記です。

チーム紹介

チーム名 : kotamanegi_hint_kureya

メンバー 1 : shinchan
諸々担当

メンバー 2 : Daylight
色々担当

メンバー 3 : hint908
なにかしら担当

Day 1

時間順のようなそうでないような雑な順番に書いていきます。

問題順がランダムということで、二人は前から（あるいは中盤から）読み、自分は後ろから見ます。

L は問題文読解ができず諦め

K は https://atcoder.jp/contests/abc369/tasks/abc369_f を思い出しながら PC を奪って LDS を書く。13 分で FA。

J は全探索ですねと言いながら PC を 奪う。27 分で AC。

E は式に起こすと累積和 2 本を持っておいて愚直に [tex: O(n2B)] を通せる制約。46 分で AC。

この間に I、少し後に H をチームメイトが通して順調だったがここから炎上

C のハノイに取り掛かる。一番下の同じ大きさのディスクをそのまま残してそれら以外を移動させるが最適なのに、その中で最も下のみを残して移動が最適だと思って、手計算でどうみても計算が合わず。勘違いに気づいたのはコンテスト直前で時すでに遅し。
チームメイトは A と G をやっていたが通せておらず、そのまま 5 完 14 位で終わり

感想

韓国の 3 時間 12 問セットで、頑張って 8 問解かせてくれる（優勝は 10↑ 完）と思っていたがそんなことはなく...（ABC の 3 完追加でようやくという感じ）

Day 2

最初の 2 問が簡単だと思っていたらそんなことはなかったので 今日も今日とて後ろから

N、adjacent ってなんだっけと聞いてしまいました。自分の研究で頻出の単語なのに...
分からんので投げたら shinchan が解いてくれた。

M を読む。わからんので投げる。説明のときに 2 つに分けるの分け方をうまく説明できなかった（は？）
1,2 番目を単独で持つのがよさそうとは思っていたが、だからなにとも思っていた。
Daylight 証明 + 解法提案をして実装。WA ったので Help したら TLE した挙句、実装もミスっていた。結局 AC できず。

L を読む。増加列と減少列の 2 つに分けるとかか？と思っていたがそんなことはなかった。

K を読む。わからんので投げる。 N\sqrt(N)\log N に重めの定数倍で通したらしい。

J を読む。コンテスト中は嘘にぶたんと呼んでいた。開区間でびっくりした。
当てるまでの回数と右側をなくす回数で式は作れそうと言って後は投げた（が、通せなかったらしい）。

解かれていた G を読む。81 通り列挙すればよいですねと言って AC。

次に解かれていた F を読む。理解したと思ったがサンプルがよくわからず SOS を求めると最初のフリップだけ永続、それ以外はそうでないらしかった。変化分が簡単にわかるので、最初時点のを求めればよさそうで、そのとおりにすると AC。

この後は B の括弧列問題。prefix と suffix でそれぞれ括弧が何個余るかを見ればよいと思って PC を奪ったが、どの変数がどの括弧を表しているかで迷ってしまった。紙に書いて落ち着いて実装して AC。

J を少しやった（前述）後、I に取り掛かる。一手目に時間がかかったが、三角形をなすとこの重みの積が平方数なら木にすればよく、後はハッシュを頑張る。
サンプルが弱くて変数名のミスに気付かないなどで 2 ペナを生やしたが何とか AC。

チームメイトが AEKN を解いていて 8 完 5 位で終了

感想

有志による 14 問 5 時間セットでした。サンプルが弱いよと終始嘆いていたし、説明はつけてほしかった。 4 位が 10 完で、ペナ差的に +2 完していても届かなかったらしい。

問題番号 = 問題名の頭文字だったので、Day 3 は OtoZ かなぁとか思っていました。

Day 3

AB が簡単ということで、そちらは二人に任せて C から読む。
途中で Daylight が合流して後ろから読んでもらい読解だけ終わらせる。

B で 9 ペナしていてうひゃーとなれました。

簡単問がどれか分からず、構築が欲しいと言っていた shinchan に E を投げる。

結局順位表情報から D, I を AC。

K は UF + マージテクでなんとかならんかと投げつける。

G は T も 1000 以下であることを読解担当の hint908 とかいうやつが見落としていて、そのまま T が 1001 以上も投げていた。結構後に気づいて AC。気づくまでに 5 ペナも出させてしまった。

F はよくわからず投げた。解法が実装されて WA ったときにランテスを書いてもらっているのに割り込んで何個か手動でチェックしたら原因を発見したが、時間切れ。

6 完 13 位でした。

感想

12 問なら OtoZ でよくないか、それとサンプル弱くないかと嘆いていた。

その他

１日目、居住地から開催地まで約 4 時間かかるのに午前十時半に部屋を出ました。
前日がインターン最終日で東京出社が必要となっていて、そのためにホテルに泊まっていたためです。

２日目、チームメイトの無線マウスが電池切れになったためインターン用に持っていっていた有線マウスを急遽取り出しました。
有線しか勝たんわ。

３日目、落とし物（充電ケーブル）をコンテスト会場に落として帰ってしまいました。（関係者の方々、本当に申し訳ありません）
会場で充電していないので、充電ケーブルを出す理由も出した記憶もなかったので自分のものではないと早合点してしまっていました。
もともと充電ケーブルが入っていたポーチに有線マウスも入れていて、２日目で取り出したときに落としてしまったらしいです。
宿泊部屋では別のケーブルを使ったためなくしていたことにも気づかず、結局気づいたのは帰りの新幹線を待っているときで時すでに遅し。処分していただくという事態に...

全体を通して

運営の皆様、３日間ありがとうございました。そして落とし物を置いて帰ってしまいすいませんでした。

解法が思いつけなかったときの難易度推定が下手すぎるという感じでした。

横浜までに地力を底上げしておきたいのですが、研究ががが...
夏休みも学会 + インターンで今日までほとんど何もできていないのも痛い。

Playoff 進出で海外に行きたいところです。

JAG 夏合宿2025 作問経緯

はじめに

hint908 です。 JAG夏合宿2025 Day2 の作問をいくつかしたので、どのような経緯でその問題ができたかについて覚えている限りで書いています。

問題を見たい方はこちらからどうぞ → 2025/Practice/夏合宿/問題文とデータセット - ICPC OB/OG の会

B: Broken Keyboard

キーボードのキーが 25 個しかないのにアルファベットは 26 種類あって困った、という趣旨の問題です。

ノートパソコンを掃除しようとキーボードのキーを外していると爪が壊れるなどして A キーがうまく取り付けることができなくなりました。キーボードにはアルファベットでないキーがたくさんあり、そのなかのいくつかのキー（無変換、Caps Lock、Fn など）に A を割り当てて何とかしました。

この出来事をもとに問題にしようとするとこういう問題になります。

C: Triangles

三角形分割をしようという気持ちになりました。
三角形分割をするだけだとライブラリとか算数とかで殴ればなんとかなると思ったので、追加の要素を探し求めていたときに点を追加することを思いつきました。

部分問題の 99.9 % がギャグであることに気づいてからが本番です。

F: 00 → 1

文字列の操作をする問題を作りたいという気持ちになりました。
論理演算系はたくさん出てそうだったので、それ以外でなにかないかと考えていたときに同じ文字を詰めて flip することにしました。

設定上、いろいろな形式でなにかを問うことはできるのですがそれを問題にしたところで面白い / 難しいかは別だったので、シンプルだが虚無ではなさそうだと判断した形式で提案しました。

この設定で限りなく難しくしたものが AtCoder にあったらしい。

G: Driving Playlist

ドライブをしに行くという設定で何か問題を作ろうとしました。
1人よりは複数人の方が問題にしやすそうとか、ドライブに行くならその道中では曲を流し続けるよねとか、集合するよりは拾っていった方がいいかなとか考えます。
Playlist 関連の問題が AtCoder にあり、それを改題できそうな気持ちにもなっていたはず。

そこからは割と一本道です。
みんなでドライブに行くのだからプレイリストにはみんなの好きな曲はいれたくて...車に載ってから目的地に着くまでに一回は好きな曲を聴きたいよね...とするとこの問題になります。

中盤のそこまで難しくない枠で考えていたら思ったより簡単枠扱いになりました

H: Count Unique Packing

第一回問題選定のときに数え上げが不足していたことが分かったので、新たに数え上げの問題を作ろうとしてできた問題です。

条件をすべて（もしくはいずれかを）満たす数列なりグラフなり文字列なりの個数を求めさせるのが数え上げ問題の主な問い方なのですが、肝心の条件が何も思いつきませんでした。数え上げが個人的に苦手なのもあって既出に引っ張られまくりました。
そうこうしていると「何かの条件あって、それを満たすのは 1 種類だけである」という条件が降ってきました。この条件自体が珍しそうだったので中の条件は既出でもよいという気持ちでとりあえずナップサックを引っ張ってきました。
あとは問題として自明ではなくなるように設定をつけました。（とりあえず複数のナップサックに詰めさせることにして、マージできると虚無なのでマージできないという条件をつけるとあら不思議）

そこからの一番の問題は解けるかどうかなのですが、解けたので作問成功です。

個人的にかなり好きな問題です。なので別の機会まで取っておくかかなり悩んだのですが、JAG に投げようという動機で作ったので JAG に投げました。（このあと AGC の話が生えてやっぱり...と思うことになります）
内部コンでの評判がよさそうで嬉しかったです。（本番でも評判がよいといいな）

K: All Copy Paste

なかなか問題が生えず困っていたとき DEGwer 式作問法｜DEGwer の記事の無料部分を読んでとりあえず設定を考えようという気持ちになりますが、設定が生えないから問題も生えないんですね～と言っていました。

そこで同記事内出てきている「コピー操作」を使って問題を作ることにしました。
試しに数列に対して Ctrl+A, Ctrl+C, Ctrl+V を繰り返してみると...この問題の出来上がりというわけです。

簡単枠のつもりだったのですが内部コンでは大変なことになっていそうな雰囲気があり、さらには色々な道具が取り出されていてびっくりしました。
そのうち、永続 BBST を使った解法を通さないために N,M,Q が 1e6 になりました。

JAG 模擬国内 2025 G: 花子さんの芸術

夏合宿ではなく、その 2,3 か月前に行われた模擬国内で出題した問題です。
いい機会なのでついでに書いておきます。

ある寒い日、こたつにはいっていたわけですが、人々と一緒にこたつにはいると足がぶつかりがちです。

ここから人々がこたつにはいっていて、体ぶつからずに...みたいな設定が生えました。

後は首までうずめたり対辺まで足を延ばしたりする人がいて、頭と足の対応のさせ方の数え上げができるな...! みたいな感じだったかと思います。

原案提案時にここらへんの設定を消し飛ばし、この設定を誰にも言わず、問題文を書かなかったので設定の付け方は問題文担当者の方におまかせしました。
言っていても採用はされなさそうだけど（頭と足の対応のさせ方とか、嫌だろ）

おわりに

覚えてないところが勝手に補完されて別物になっているかもしれませんが、何卒ご容赦を...

OUPC 2024 の Writer をしてきた

はじめに

hint908 (kureha) です。OUPC 2024 Day 1 の作問をしたので、そのコメントです。

onlinejudge.u-aizu.ac.jp

A: AlphAbet

簡単枠です。その時点であった最簡枠が A 問題レベルかと言われると微妙な気がしたのと、別の問題で hint908 が出てきたのでその原案者の名前を使ってやろうと画策したのが合わさってできました。

AtC とは違い、正誤判定がスペースや改行含めて完全一致かどうかなので、改行を入れろと書いたのはよかったと思っています。
ちなみにスペシャルジャッジを除いて空白区切りで出力させる問題はなかったです。

当日までに AtC に出題されて爆破されなくもなさそうとか思っていました。（爆破されても生やせばいいのですが）

B: Give Me a Hint

その時点であった最簡枠です。
shinchan は仕事しろ

D: Give or Take

お手軽考察枠です。と書いていたら全然通されなくてびっくりしました。燃やす埋める Easy を考えていたら生えました。
もともと、両方先手に渡せば +z、両方後手に渡せば -z を（共通の）スコアに加算しこれを最大化せよという問題でしたが、Tester の Y.Y. さんが flow やるだけで通してそうだったので、構造に気づかないと解けないようにしました。
この -z という露骨なのをなくしてしまって難しくなったのかしら。

既出っぽさはあるとか言っていたら既出だったらしいです。すみません。

E: Periodic Sequence

インタラクティブ一問欲しいよね枠です。色々考えてたらいつの間にか生えました（過程はあまり覚えてないです）。

色々なバージョンを考えていました。もともとは質問回数を 20 回で A_x = A_y のときは情報を与えないバージョンもありましたが、ジャッジが明らかにやばいので断念。 そのときのバージョンから継いで質問回数を 20 回にしていたのですが、vwxyz さんの提案により 900 以下 15 回で行けそうと言われたので 1000 以下 15 回にしました。
手で解くのはほとんど不可能で、きちんと全探索コードを書かないと AC できなくなったと思います。というのが想定でしたが、どうやら手で解くのは不可能なケースを予め除くと通るらしいです。

vwxyz「面白かった」
kuhaku「おもろ」

この E 問題から K 問題の 7 問に難しい問題が固まってしまいましたが、ランダムなので仕方ない。（え、D もこのなかですか？）

F: Repeating Decimal

原案その他諸々 KowerKoint です。計算量解析で口を出しました。

素因数分解のところがネックで、素数の個数を考えると～という感じで進んでいましたが本番４日前に実際には log 2 個でできる解法があるという話をしていました。
vwxyz さんに面白いと言われましたが、制約調整をする時間はなかったのでそのままになりました。（解法の区別も微妙そうだったのもあります）

writer 実装例を見たいという要望があったので、他の問題と一緒に後日 公開されるかと思います。

G: kotamanegi_world

ナベアツ Extreme です。
Give Me a Hint (= kotamanegi_hint_kureya) がすでにあったので、kotamanegi_world を借りて問題名にしました。

10^{12} で提案していましたが、vwxyz さんに間に合うかは微妙そうだが 10^{18} でもできそうという話をされ、実装してみると案外速かったので 10^{18} と相成りました。

解説用に世界のこたまねぎ君を用意していたのですが、オンサイト 0 AC で特に読まれてなさそうだったので飛ばしました。 そのページだけ見せればよかったですね。

H: Segment Graph

クエリ形式兼グラフ枠です。これを書いていてグラフ枠が少ないことに気づきました。（テストケース大変だから仕方ない）
ABC355-E: Guess The Sum を二重和にしたら解けるのだろうかと言っていたら解けたので提案しました。

もともとはクエリなしでの提案でしたが、vwxyz さんにクエリありを提案されました。（代わりに A の最大値が 230 から 220 に減りました。）
用意していた解法が結構無理やり気味だった気もしていたのですが、すっきりした解法となりました。

TTPC で似たような問題が出されています。原案者（自分）が解けていなかったのでセーフと言われていたらしいです。
そのときは実装でバグり散らかしていて解けませんでした。
逆に TTPC 運営方を含むチームが苦戦してそうだったので、既出ではないということで...

J: Reveratory Graph

構築兼グラフ枠と見せかけた整数枠です。難しい問題の中ではギャグよりです。

もともと別の問題として生えていたのですが、そちらが乱択などが通りそうで解体。ただ、想定解法をうまく利用できないかと生やしました。
灯台下暗し感があって好きです。 X が正整数なのはもやもやする。

K: OU Language

原案は KowerKoint で、解法を生やしました。

証明はきちんとしたつもりです。不備があったらすみません。

L: Double Elimination

お手軽考察枠です。元ネタは Apex Legends (ALGS) です。
強さ通りに勝敗が決まったらどうなるんだろうと思ったら強さ通りに決勝進出しました。

よわよわサンプルなり制約なりで解法が透けないようにしたつもりです。
確率ではなく通り数でもよかったのですが、初心者に逆元 mod を出したくない気持ちだったので確率にしました。（逆に敬遠されてしまいそう気もしますが、必要ないのでご容赦を...）

M: Ikomiki String

だいたい littlegirl112 です。
問題文添削をしました。わかりやすいと思って頂ければありがたいです。

N: Super Knight

shinchan は仕事しろ

O: Perfect Viewing

何も担当してないですが、解法の話をば。

dp をする際に、右端二つを持って遷移を頑張るというのが主流の解法そうですが、右端だけを持って傾きの小さい順に更新するだけでよいです。（TLE, MLE しやすいので実装には注意です）

典型枠かもしれないが簡単枠ではないだろうという気持ちがあって、C の次にこれを見にいくのは初心者には厳しかろうという話をしていました。

P: Pure OUPC Project

原案 shinchan です。

最小化・最大化の対象が定まっていなかったようなので、計算量不明の解法とともに提案しました。(そのあときちんと計算量を出しました）
嘘解法が怖くてマルチクエリ + マルチテストケースというあまり見ない形を採用しました。諸々を [tex: 109] ではなく 10^{12} にしているのも同じ理由です。もともとは 10^{16} にしようとしていたのですが、重かったので下げました。

log 2 個になる理由が同じところから派生してていいね。（片方を見つけて、さらなる計算量削減のために別のアプローチを探してそのまま...となった人もいそうです）

思えば簡単枠を増やすためにも、案としてあった別のも出しておけばよかったですね。

出題しなかった問題とか

３問提案１問改題をしていましたが、１問は既出が見つかり爆破、１問は準備期間中に類題が出題され爆破、１問は想定解法が通らず（別の解法も見つかっていますが）爆破、１問は逆元関連で問題があったり面倒なだけで他の問題を生やしたことに満足したりして爆破しました。
今度どこかで公開しようかな。

その他

７問提案１問改題し、その８問の writer をしました。（あと問題文添削）
はっきり言って大変ですが、あまり大変ではなかったです。 writer 作業のなかでテストケース作成が一番大変だと思っていますが、そこがあまり重い問題を提案しないようにしていたのがあります。（フロー想定とか、面倒な場合分けが多いとか）
問題文添削をしたのが結構直前で運営陣には申し訳なかったなと思いつつ、clar もほとんどなくよかったのかなと思いました。

最後に

参加者の方に楽しんでいただければ何よりです。ありがとうございました。
問題文とかもっとこうした方がいいよ、とかあれば教えてくだされば幸いです。

来年も作問側で参加するつもりなのでそのときはよろしくお願いいたします。
提案量はそこそこにしたい気持ちなのですが、そうすると問題数が足りなくなりそうな気もします。
つよつよな方に魔改造をしてもらうつもりでいますが果たして...？

就活です。内定が欲しいな。

AtCoder 橙になりました

はじめに

kureha（hint908）です。AtCoder で橙になりました。
今回はいわゆる入橙記事です。

入黄まで

入黄までの話はこちら。今見ると変なことしか書いてないです。

kureha908.hatenablog.com

統計情報

画像を入手した時点までの統計情報です。

まずはレート推移。Rated 参加回数は 75 回でした。

続いて寄与グラフ。（AtCoder Graphs より）
パフォーマンス 2800↑ を取るとレートが 100↑ 増えてよいです。
2400↑ を取った回数が明らかに少なく、停滞すらできなさそう。

最後に実績的なやつ。（https://kenkoooo.com/atcoder/#/table/より）
AC 数について、入黄時点で 1300↑ だったのでほとんど倍。

入橙までにしたこと

レーティングの上昇につながったこと（精進など）というよりは単純にあった出来事の話です。時系列順でもないです。

AtC の過去問を埋めた

1ヶ月で 700 問解いた時期がありました。
灰 diff が約半分を占めていて、青 diff 以上が 100 問弱くらいらしいです。本当に埋めていっただけ。

ABC / ARC / AGC にたくさん参加した

黄色になってから半年くらいはすこしアンレ気味になっていましたが、年が明けてからはほとんど参加しました。
レーティングを上げるためには ARC / AGC に出る必要があります。
知らないデータ構造や典型アルゴリズムもまだまだあるので、ABC もかなり参加しました。

CodeForces バチャ

大学の部でバチャをやりました。
定期的にやる予定だったぽいのですが、いつの間にか立ち消えました。

ICPC 2023/2024、JAG の諸々

ICPC 2023 の横浜 Regional では実装をバグらせ消化不良な結果に終わってしまって、頑張ろうという気持ちになりました。
ICPC 2024 国内予選では結果を出せたので満足。
JAG の模擬国内や夏合宿にも参加しました。こっちはチームへの貢献が薄くなってしまった気がしています。

OUPC 2023

2024 年 1 月上旬に開催した OUPC 2023 で問題提供しました。
はじめてのさくもん というのもあって、今見るとあまりよくない問題を作ってしまっていた。
いろいろ問題を考えてみていますが、どうすれば猛威を振るう問題ができるのかがよくわかりません。
OUPC 2024 でも問題提供をするつもりなので、ぜひご参加ください。（参加登録 : OUPC2024 - connpass）

Universal Cup

今年の ICPC チームで途中参加することになりました。
初参加が入橙した日の前日で、これがあったから橙になれた...! というわけではなさそう。
でもチームには貢献できているのでよさそう。
5 時間コンテストは消耗が激しすぎて、ABC に参加する気力がそのうちなくなりそう。

コンテストへのオンサイト参加

ICPC、OUPC、学生コン、夏合宿がここにはいりそうです。
コミュニケーションが不得手で、あまり交流はできていませんが...

入橙までしてないこと

得意分野 / 苦手分野の把握

ずっとわからなくて悩んでいます。これを把握しておくと、複数の問題を見比べたときに突撃すべき問題が分かって良いとは思っているのですが、直感的にしか選べてないです。
最近は数え上げ・幾何以外の ARC 前半レベルの速解きが得意で、数え上げ・幾何が全くの門外漢な感じがしてきています。
ただ、全方位木 dp と期待値 dp ができないことは分かっています。

これから

ICPC 2024 Yokohama

競プロで海外への切符を手に入れたいです。
10 位以内なら確実、15 位も行けなくはなさそう、20 位は微妙そう。
データ構造、アルゴリズムはチームメイトに丸投げしていて、数え上げもできないので、仕事はあまりないかな。

数え上げを鍛える

先日の ARC186/187 は合計して 10 問中 6 問が数え上げでした。
加えて、ICPC のチームメイトに数え上げ担当がいないので鍛えるしかないという話。

それはそれとして、一つの分野として確立されていると言ってもいいと思うのですがここまで偏るのはどうなんだという気持ちが大いにあります。
構築 3 問とかインタラクティブ 3 問とかも出してくれるのであれば矛を収めます。（ARC 175 がそれっぽいが、CD をあまり構築だとは思っておらず...）

競プロ以外

研究は修論とか論文誌とかとか...。
就活はとりあえず内定・内々定・内々々定・... がもらえれば気楽になれる。

おわりに

ICPC 横浜まで橙維持できれば、いいな。（Rated が 4 回くらいありそう）

ICPC 2024 国内予選参加記

はじめに

kureha といいます。AtCoder 黄色です。橙が見えてきてほしいのですが、8 月末まで Rated が 3 回くらいしかなさそうで、まだまだ道のりは遠そうです。 今回は ICPC 2024 国内予選 の参加記です。

チーム紹介

チーム名 : kotamanegi_hint_kureya

メンバー 1 : shinchan
諸々担当

メンバー 2 : Daylight
色々担当

メンバー 3 : hint908
なにかしら担当
shinchan曰く「自分と Daylight は安定タイプで、908 は天才タイプ」、別チームの強い人曰く「一発型」らしい。（ほんまか？）

コンテスト前

プリンターが三台あってどれにするかを決めたり、Y.Y. 先生が問題作ってるならマトロイドとか DM 分解とかか...? とか言ったりしつつ時間をつぶす。

ちなみに RAINBOU の Twitter (現 X) に投稿されているチーム揃ったよのポスト、こたまねぎの世界って書いてあるけど直前までこたまねぎ〇〇でした。

コンテスト開始

だいたい時系列順に書きます。提出履歴とかどこかで見れたりしませんかね...?

コンテスト開始直後は事前の取り決めにより（印刷ボタンを押した後） Daylight が A を見ます。
実装中は画面半分使って shinchan が B を見るとか言ってた気がするけど結局見てたのだろうか。
なお印刷待ちで確実に暇な方がおひとり。

[02:33] A : Daylight

shinchan が B を見て実装します。
A を通したくらいか少し前に問題が一セット届いたので D を見て、Daylight に C を渡します。

[08:33] B : shinchan

Daylight にパソコンが渡され、shinchan は E へ。

D、簡単だけど書くの面倒だなぁと思いつつ細部を詰めます。
過去問を使った練習ではペナを生やしまくっていたので、そうならないように紙に疑似コードを書いていました。

[18:31] C : Daylight

パソコンを渡され、D を実装します。
Daylight は F を見に行ったはず。

疑似コード、役にはたったがまあまあ雑でした。
途中で Segmentation Fault を吐いたけど原因は容易に特定でき、特に詰まることもなく実装完了し提出。

[28:04] D : hint908

模擬国内のときは CD で詰まったのですが、本番はここまで予定通りに進みました。
ここからは高度な柔軟性を維持しつつなんとやらというやつです。

shinchan は E を解けてなくて考察中、Daylight が見ていた F は手を動かしながら考えたいタイプの問題だったようなので Daylight に パソコンを渡します。
自分は E~G のどれを解くかでしたが shinchan の指示で E を一緒に考えることに。

長さ N の正整数列 c に対して条件を満たす N \times N 行列があれば構築する問題でした。
c_1 = c_n の場合は自明なのでよくて、 c_1 \neq c_n の場合は裏側からも見ることを考えると c_1 \dots c_n \dots c_1 \dots c_n ならよさそうという提案をする。
色々手で解いたりしていけそうという結論になったので実装は任され shinchan は G へ。
ただ c_1 \dots c_nc_1 \dots c_n のケースしか手で解いていなかったことに気づいたがどうにでもなったのでパソコンが空くのを待ちながら疑似コードを書き書き。

F がバグったのかペナったのかは忘れたけど交代し、3 行しか書かれていない疑似コードを装飾しながら実装。
軽実装なのはわかっていたので疑似コードが書けた段階でパソコンを奪った方がよかったのかもしれない。
n \leq 3 のときは全探索するかとか shinchan と話し合ってたけど面倒だったので書かなくてもいいかという相談。
サンプルにないケースも合ってそうだったので、全探索なしでいいよということになり提出。

[1:14:57] E : hint908 + shinchan

一発 AC やったぜ。

Daylight にパソコンを渡し、shinchan の指示で H へ。
英語混じりのクソ長問題文と入出力説明を読み終わったくらいで G の助太刀を頼まれます。

また構築かよと思いながら見ます。
E は数列 → N \times N 行列でしたが G は数列 → 2 つの数列でした。

総和が偶数でないといけないのは自明で、偶数である要素は半分にすればよさそうな感じに見えるのはそう。
問題は奇数をどう分ければいいかで、これは偶数が１つでもあればこうやればいけそうという提案をする。

納得してもらえたので自分は H を考えて、２人は交代しながら実装。
いろいろ考えると最短経路問題になりそうで、ABC あたりに似たような問題があった気がした。
(1, (N+1)/2) から (N, (N+1)/2) へ行くことができなくするにはどう障害物を置けばいいかみたいなやつ。
明らかに実装が面倒とか思っていると G が WA った。
コードを見てみるとあら不思議、奇数しかない場合が No 固定ではありませんか。
自分はここを偶数が１つでもある場合と同じように実装すると Y/N が判定できると思っていて、shinchan は 偶数が１つでもあれば存在すれば Yes、それ以外なら No と思っていたらしい。
これについては言うのを忘れていて (= No だと思われるのは当然の話で) 、要反省ポイントでした。
とりあえず s = (1, 1) なら a = (0,1), b=(1,0) でいいことを伝えて考察しなおし。

この後に要素をちょうど半分にわけたとき、それぞれの総和が等しいことが Yes になる条件だと判明し、自分の考察も嘘だった。
これはただのナップサックなので実装をしてもらう。

なんやかんやでもう一回 WA が出たけど G が通る。

[2:18:20 + 2 ペナ] G : shinchan + hint908

バグ続きだった F もなんとか通る。

[2:27:31 + 1 ペナ] F : Daylight

H は間に合うかわからないし、なんか 2 チーム AC してる I も分からんし、ただ横浜に行ける順位は確保できただろうということで残り 30 分間は休憩タイム。
良い感じに他チームが通して 7 位になれとか言いつつそのまま終了。

結果と感想

結果は 7 完 5 位で、大学内 1 位。
無事突破できてよかったです。

教員方のお金で打ち上げが開かれました。
教員方の一人が所属研究室の先生で、shinchan「自分と Daylight は安定タイプで、908 は天才タイプ」 というのがその先生経由で研究室 slack の全体チャットに投下されていて泣いた。

ICPC Replay (追記)

ICPC Replay というものがあったので、その出力をペタリ。
DE を早めに通せているのが最終順位に効いてそうです。

ICPC2024 模擬国内参加記

はじめに

kureha といいます。AtCoder 黄色です。レーティングも伸びてきて橙がそろそろ見え始める頃でしょう。 この度 ICPC 2024 模擬国内 に参加してきました。

チーム紹介

チーム名 : kotamanegi_hint_kureya

メンバー 1 : shinchan
諸々担当

メンバー 2 : Daylight
色々担当

メンバー 3 : hint908
なにかしら担当
shinchan曰く「自分と Daylight は安定タイプで、908 は天才タイプ」、別チームの強い人曰く「一発型」らしい。（ほんまか？）

コンテスト前

事前にチーム（+ 大学内の複数チーム）でどこかの研究室に集まってやるかという話でもしていたわけですが、行きませんでした。

言い訳としては模擬国内が 6 月 29 日にあったわけなのですが、25 日から 28 日まで東北のほうに行っていました。期間中はそれほど寝ていたわけでもなく、最寄りの空港にギリギリ着陸できたくらいには帰宅が遅かったのもあり、眠かったんですよね。
起きたのはもともとの開始時刻である 14 時で、遅延はあったらしいのですが行く気力が起きずオンライン参加しました。

コンテスト中

D を見てと言われたので D を見ます。教科ごとに独立に計算していいのか分かりませんでした。お荷物カウンター ++

15分ぐらい悩んで C を見てと言われたので C を見に行きます。
全探索しかなくねと思い全探索を実装。入力を取って実行すると 6 分で終わらず。
結局 45 分悩みましたがわからず、チームメイトが生やしてお荷物カウンター ++

A-F までは通っているか生えてるかしていたので G を見る。
区間 dp で 4 乗log だなとか思いつつ 40 分くらい悩んでチームメイトが F までを通して一緒に考えることに。
3 乗の嘘が提案されて、挿入とか考慮して 3乗log にはなりそうと言う。(40 分でこれ思いつかないの控えめに言ってやばいだろ）
そこから K 値 dijkstra を思い出して提案しようとすると dp[i] = priority_queue<ll, int> と言われた。
実装を任されたのでやった。一発 AC やったぜ。

以降は H, I の嘘を生やしたり生やされたりで終了。

感想

結果は 7 完 12 位で、大学内 1 位。
本番なら突破圏内で、自分が何もしていないのは置いといてチームとしての出来は上々といったところ。

一人だったら壊滅するような問題も他の2人のどっちかは解けるでしょ、みたいな感じのチームにはなるのかな。
この日にあった ARC もそんな感じでした。
横浜はいけるんじゃないかな。

OUPC2023 で問題を作ってきました

はじめに

　kureha といいます。AtCoder 黄色ですが、半年ほど Rated 参加できてないのでそろそろしたい気持ちになっています。OUPC2023 Day1 大阪大学セットにて問題作成陣として参加してきました。原案を出した問題について色々書いています。

　楽しんでいただければ何よりです。

 

D - Han Burger

　ハンバーガー的な文字列を作りたいと色々試行錯誤していたところ、括弧列から定義を引っ張ってきて問題と相成りました。

　サンプルが弱いのは意図的なのですが、ペナルティがたくさん出たのは特に想定していませんでした。最初の 15 分くらい AC が出なくて冷や冷やしていました。

 

E - Han Burger 2

　原案を出したわけではないのですが、出来た経緯をば。

　Han Burger を区間クエリにして文字列の長さを聞く形にしようとしたところ、その性質から vwxyz さんがこの問題を生やしました。強い人はすごい...。

 

G - Impassable Game

　問題文が長く、N - Bench と並んでそもそもあまり読まれなかった枠になるのでしょうか。やってみると案外解けるのではと思っています。

　テストケース作成は KowerKoint さん、vwxyz さん、maspy さんにお任せすることになってしまいました。（ありがとうございます）

　想定解法は O(NM/w + N^2) なのですが、python に合わせて 6sec にしたところ O(N^3/w) とかが通ったらしいです。

 

P - Score for Cutting Graph

　Day1 唯一の構築問題でした。

　着想は相加相乗平均の式から得ており、もともとは数列の並び替えでしたが、いろいろあって木を切る問題になりました。（vwxyz さんに証明していただきました。ありがとうございます）

　部分点の実装を行う → 色々実験してみる → エスパー → 満点を取るという段取りが必要な想定となっています。

 

感想

　楽しんでいただければ幸いです。ありがとうございました。

　来年も作問側で参加したいと思っているので、そのときはよろしくお願いいたします。

 

 

 

 

 

 

 

 

 

 

　卒論期間です。1文字も書けてません。