ei1903の競プロメモ

競プロの解説など

ICPC Taichung Regional 2025 参加記

University of Aizuからaizu_3としてICPC Taichung Regional 2025に参加しました。

www.icpc.tw

メンバー

Day0

福島空港から台湾へ。初めての飛行機でテンションが上がった。

台湾の交通事情に精通していない場合、新幹線の予約はあまりお勧めしない。駅までたどり着くのが大変なので。

Day1

この日はRegistrationとPractice Session。後ろにはbonsai、向かいの席はPCkomachiでした。PCkomachiとPCKのマスコット、少し面白かったです。

チームメイトが持ってきたパソコン赤べこ

ラストイヤーだし記念に参加するつもりだったがaizu_Cからplayoff狙えるという話を聞かされ衝撃を受けた。もうすこしちゃんと準備してくればよかったな～っと思ったが時すでにおすし。

Day2

本番。ここからは問題のネタバレを含むので注意。

コンテスト

言語：C++

エディタ：Vim

難易度が分からないのでとりあえずnyuminyusupeが環境構築をする間にachapiが先頭から、私が後半から読むことに。問題文はチームで1部なのでホッチキスを外す。

環境構築中にachapiがA,Bの読解を終わらせ、Aは簡単らしいので実装してもらいAC(0:10)

Bの内容を聞くが重実装しか思いつかず一旦置いておく

Mが解かれているので読むと幅優先探索をするだけなのでnyuminyusupeに投げるとACが返ってくる(0:28)

Eもやるだけだったのでachapiが実装しAC(0:38)

achapiがFをエスパーで実装したがWA、考察を続けてもらいAC(0:59)

nyuminyusupeにBを見てもらうとバスに乗るの1回だけじゃね？って言われたがまだ実装がダルそうなので投げるとACが返ってきた(1:13)

I,Jを見るとJが実装が難しそうだが雰囲気をつかめたので私が担当し、Iは幾何なのでachapiとnyuminyusupeが担当することに

IとJを交代で実装しているとIの誤読が判明する

Iははじめ尺取りとか言っていたが、Jの実装中に凸包を用いた解法が降りてきたので凸包と叫ぶと肯定的な返事が返ってくる

凸包のライブラリは持ってきたがcross()の中身が書いておらずnyuminyusupeと二人でライブラリを隅から隅まで探すが見つからない

絶望しながらJをAC(2:19)

cross()は気合で捻出してもらうことになりachapiがI担当に

解かれているK,Lを見ると、Kはヤバに見えて実は全探索できる制約であることに気づきnyuminyusupeに投げる

LはARC-Likeな見た目をしているが無理やり良さげな性質をエスパーしDPに落とし込めそうだと考察し私が担当することに

そうこうしている間にIのサンプルが合いAC(3:24)

Lの実装を始めると簡単なDPの組み合わせなのですんなり実装が終わりAC(3:53)

ここでKの実装に入る
時間的にも順位的にもKが解ければいい感じだが念のためachapiにHの考察を進めてもらう
何度かつまずくもののサンプルが合いAC(4:21)

ここでなんとHの考察が終わってるらしくHの実装を進めてもらう

サンプルが合わないようで聞くと解法が破綻していることに気づく

何かいい性質かゴリ押し法を考える必要がありそうだがここで時間終了

結果

順位表

9完 14位 Silver Award

日本チーム中でもbonsaiに次ぐ2位と練習時からは考えられない順位を取ることができた。playoff行きも濃厚らしい？

Iに時間かかってなければワンチャンもう1問あったかもしれない。

夜

他の日本チームに連れられ夜市へ。

まずは宮原眼科で大きなアイスを食べた。とても美味しかったが普段こんなに甘いものを食べないので途中で少し気持ち悪くなってきてしまった。

夜市では大きな唐揚げを食べることができたがビールを扱っている店が無かったのが少し残念。どうも日本ほど飲む文化が無いらしい。臭豆腐は本当に掛川花鳥園の臭いでびっくりした。playoffの時に食べると言い回避。

Day3

三日目は運営主催の観光バスツアーだった。殆どが台湾の歴史に関するもので、疲れもあり正直途中で飽きてしまった。昼は尋常ではない量の料理が提供された。日本のもったいない精神はあっけなく敗北。

最後に

ライブラリはちゃんと準備しよう。せめて読もう。もしplayoff行き確定したらちゃんと準備します。

JAGの夏合宿ではそれはもう散々な結果でどうなることかと思ったが何とか形にすることができました。勝因はコンテスト中のコミュニケーションを大切にしたことですかね。

台湾で色々話しかけてくださった皆さんありがとうございました。

担当した問題について（11/22追記）

J Sliding Tiles

愚直にシミュレーションをするとO(N^2)になるが、同じ値のところはまとめて計算したい。値が変わる可能性のあるのはタイルの上端と壁の上端。ここを次の壁の分割点として用いると、分割される回数はO(N)となって間に合う。区間加算一点取得が必要になるのでBITを用いる。

実装例（本番もほぼ同じコードを書いた）https://codeforces.com/contest/2172/submission/350021754

L Maximum Color Segment

端だけに注目すると添え字\bmod Kで独立に考えれることが分かる。一度の操作でスコアが-2～+2変化し前後の操作に影響するので、dp[i][j][flg]:i番目までで操作回数jでflgがtrueなら直前に操作している場合の最大のスコアでDP(O(\frac{N}{K}M))をK回独立に行う。(操作回数,スコア)のペア(スコアが同じ場合は操作回数のminを取る)が O(\frac{N}{K})個ずつ得られるのでこれでナップサックDPをする。

実装例（高速化のため添え字を入れ替えてます）
https://codeforces.com/contest/2172/submission/350687034

HOJ 1306 - よんかくけい

HOJ 解説

問題URL

問題概要

二次元座標平面上に \ 4 \ つの点 \ a,b,c,d \ がある。
点 \ a \ の座標は \ (0,0) \ 、点 \ b \ の座標は \ (x_b,0) \ 、点 \ c \ の座標は \ (x_c,y_c) \ 、点 \ d \ の座標は \ (x_d,-y_d) \ である。
この \ 4 \ 点を結ぶ四角形の面積を求めよ。なお、四角形の面積は整数となることが保証される。

制約

  • 2 \leq x_b \leq 100
  • 1 \leq x_c,d_x \lt x_b
  • 1 \leq y_c,y_d \leq 100
  • 四角形の面積が整数とならないような入力は与えられない

解説

点 \ a,b \ の \ y \ 座標は共に \ 0 \ なので、 x \ 軸で上下 \ 2 \ つの三角形に分割することができます。 よってそれぞれの面積を求めて足した結果を出力すればよいのですが、計算途中の面積が整数とならない場合があるため除算は最後に行いましょう。

HOJ 1305 - プロになりたい！

HOJ 解説

問題URL

問題概要

文字列 \ S \ がPROであるならば"PRO"を出力し、そうでないならば \ S \ を出力せよ。

制約

  • |S| = 3

解説

S \ がPROであるかはif文で判定すれば良いですが、C言語のように"は文字列の"の区別するために\"と記述する必要がある場合に注意しましょう。

HOJ 1527 - Colorful Tree

HOJ 解説

問題URL

問題概要

N \ 頂点の木があり、頂点 \ i \ は色 \ C_i \ で塗られている。
以下のようなクエリが \ Q \ 回にわたって与えられる。順に処理せよ。

  • 頂点 \ x_i \ の色を \ c_i \ に変更し、頂点 \ x_i \ に直接繋がっている頂点の色の種類数を出力する。

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 5 \times 10^5
  • 1 \leq C_i \leq 10^9
  • 1 \leq x_i \leq N
  • 1 \leq c_i \leq 10^9

解説

まず木を頂点 \ 1 \ を根とした根付き木として見ます。
次に各頂点について、「現在の色」、「親の頂点番号」、「親の色」、「直接つながっている頂点の｛色:個数｝の連想配列」を用意します。このとき、連想配列のサイズが答えるべき色の種類数です。

更新処理をする際、隣接する頂点をすべて見てしまうとTLEになってしまいます。そのため、親に対してのみ更新を行うことにします。

各頂点について、子の頂点の色が更新された場合はその時に更新されるため問題ないです。親の頂点が更新された場合は、自分の知っている親の色と実際の親の色が異なる場合連想配列の値を更新します。
このように更新処理を行うことでクエリ当たり \ O(\log N) \ で処理を行うことができます。

よってこの問題は \ O(Q \log N) \ で解くことができました。

HOJ 1528 - Monochrome Balls

HOJ 解説

問題URL

問題概要

N \ 個のボールが横一列に並んでおり、始めすべてのボールは白く塗られている。
以下のような \ Q \ 個のクエリが与えられる。

  • 左から \ x_i \ 番目のボールを黒く塗る

各クエリ後のボールについて、白く塗られたボールが連続して最大何個並んでいるか求めよ。

制約

  • 1 \leq Q \lt N \leq 3 \times 10^5
  • 1 \leq x_i \leq N
  • x_i \neq x_j

解説

連続した白いボールをUnionFindで管理したくなりますが、UnionFindでは削除するという処理ができません。
そこで、クエリをすべて処理し終えた状態から始め、各クエリを逆に処理していきます。
すべて処理し終えた状態においての答えは簡単に求めることができ、クエリは黒く塗られたボールを白く塗りなおす処理とすることができるのでUnionFindで処理が可能です。
よってこの問題は計算量 \ O(Q \alpha(N)) \ で解くことが出来ました。
※ \ a(N) \ はアッカーマン関数の逆関数

HOJ 1529 - Red Black Balls

HOJ 解説

問題URL

問題概要

N \ 個のボールがあり、i \ 番目のボールには整数 \ A_i \ が書かれている。
これらのボールを青または赤で塗るとき、青いボールの値の総和が赤いボールの値の総和と等しくなる塗り分け方を \ 998244353 \ で割った余りを求めよ。

制約

  • 2 \leq N \leq 200
  • 0 \leq A_i \leq 200

解説

値の総和が等しくなるということは、青の総和 \ = \ 赤の総和 \ = \frac{\sum A_i}{2} \ です。
そのため、全体の総和が奇数の場合答えは \ 0 \ です。そうでない場合、 \mathrm{dp}[i][j]を \ i \ 番目のボールまでを塗り分けたとき、青の総和が \ j \ となるような選び方の総数とした動的計画法で答えを求めることができます。
よってこの問題は計算量 \ O(N \sum A_i) \ で解くことができました。

HOJ 1525 - Counting Squares

HOJ 解説

問題URL

問題概要

二次元座標平面上に \ N \ 個の点があり、 i \ 番目の点の座標は \ (x_i,y_i) \ である。
次の条件を満たす整数 \ i,j \ の組の個数を求めよ。

  • 1 \leq i \lt j \leq N
  • 四角形 \ (x_i,y_i),(x_i,y_j),(x_j,y_j),(x_j,y_i) \ は正方形である。

制約

  • 2 \leq N \leq 3 \times 10^5
  • -10^9 \leq x_i,y_i \leq 10^9
  • (x_i,y_i) \neq (x_j,y_j) \ (i \neq j)

解説

整数 \ i,j \ (i \lt j) \ が条件を満たすとき以下のことが成り立ちます。

  • x_i + y_i = x_j + y_j \ または \ x_i - y_i = x_j - y_j

よって、上記の条件を満たすペアを数え上げればよいです。これは求めた値をソートし連続する同じ値の個数から求める方法や、C++ならばstd::mapを使う方法があります。