feature image

2025年7月6日 | ブログ記事

ICPC2025 国内予選参加記 (o3-kayama)

チーム紹介

Ponjuice : 構築とか実験して嬉しい構造を見つける系の問題が好き
Series_205 : AGCで得たレートをARC参加者に配る仕事をしています
hir35 : 構築とかが好き チームメイトより400ぐらいレートが低いです

戦略

事前に用意したものはatcoder,他の様々なライブラリをexpandするものぐらいで変なものはたいして用意をしなかった

戦略としては1問目はPonjuiceがとき、B以降は印刷物がくるまで右画面に表示している問題文を都度進めて解き進める感じで進める

問題

A Ponjuice

n*(n-1)/2の二乗で終わり。
0分で通せてるところは何者ですか?

B Series_205

入力が小さいので、全探索。

C hir35

setで重複を除きつつやる
土曜日と日曜日の定義は書かなくていいのかなあなどと思いました。

D Ponjuice

最初、実装で詰まってしまって一回Eにパソコンを譲りました。よくよく考えてみると左上の文字が0になるように#.01の配列に直すとのxorになっているのと、1行目と1列目で.#が入れ替わる頻度が明らかに間違ってないことが条件でこっちで書き始めると意外とすぐ終わった。(最初に実装始める前にもう少し詰めればよかったかもだが、順位表見てるとそこまで悪くない?)

E Series_205

問題文に字が多すぎる!これを英語でやられると困ります。
その頂点にいなければならない時刻を考えると、木DPになる。各頂点の親が与えられるのでDFSすらいらない。
本来なら一瞬で解けるはずだったが、変数名を取り違えて終了。
たぶんEFをデバッグしている頃にやっと紙の問題文をゲットした。チーム数が多い大学の弱点。

F hir35

それぞれの操作は最初にある(A/B)の塊を一個右にずらす操作と思える。
数が違うとどう見てもダメで、他は可能だと信じてやると、後ろから合わせていけることがわかる
復元ミスって1ペナ
コーナーあってもう1ペナ(すみません、、)

G Ponjuice

サンプルを見てみる側面は基本三角形であるが、四角形になった分だけ麺の数が減っている。
四角形にできるのは辺が平行になるときだけであるが、平行である時に確実に平面になるかどうかがよくわからない。Fが終わったタイミングで他に解けていた問題がなかったため一応これを書いてみて出してみるとAC

H Series_205

G が書かれている間に hir35 と考察を進めると、普通に解けそうということに。
とりあえずランレングス圧縮をする。
2以上に出られるかが重要で、あとは偶奇しか関係ない。そのへんを頑張って計算すると、残りは ()()( みたいな文字列と等価で、これは自明。
(()())) みたいなやつは、どこからでも (())) に出られるので、()() の分を別で足す必要がないことに実装中に気付いて、えらい。

I Ponjuice

Hを書いてもらっている間にhir35で一緒に考察。
同じ数字をswapすることはないので1~Nの数字がそれぞれ2つずつある問題に直すことができることまではいけるが、その先が苦しい。隣り合っている数字をスワップしたいのは 1221のようにそれぞれの数字を結んだ線が交差してない時なので区間の中でペアができてる数字を探したくなりMo'sを書こうとする。実装中、Seriesからセグ木で後半部分を解けるよと言われ、0~N-1までの数字が二つずつになるように変換するところまで書いてSeriesと交換。最初にint n; をしていることを忘れ n*(n-1)/2 をして1ペナ。

全完後

それぞれ解いてない問題を読んで解法の共有や反省をしたが、時間は余った。ただ、順位表がかなり熱く、AMATSUKAZEが最後全完した瞬間には科学大から5チームいけるかと思ったが、その次の瞬間提出がでた。科学大からyokohamaに5チームの希望も一瞬で終わった...(来年はワンチャンないかな?)

感想

Ponjuice icon
この記事を書いた人
Ponjuice

競プロer AtCoder:A橙,H黄

Series_205 icon
この記事を書いた人
Series_205

23B のしりーずにひゃくごです。競技プログラミングをしています。

hir35 icon
この記事を書いた人
hir35

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
2023年4月21日
CPCTFを開催します
noc7t icon noc7t
2022年8月30日
【競プロer向け】母関数を習得しよう!
tatyam icon tatyam
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記