Repovive Starter Round 4 参加記

私です。

Repovive Starter Round 4 に参加しました。3完でした。

C問題がなかなか面白かったです。やっぱり海外コンテストはこういう考察問題が多いイメージで楽しいですね。

A問題 Different Parity

要約すると、整数区間 $[l,r]$ に奇数と偶数の両方が含まれるかを判定する問題です。

$l\ne r$ なら区間内に連続する2つの整数が存在するため、奇数と偶数の両方が必ず含まれます。

B問題 Balanced Trio

Yes/No は、(a + b + c) % 2 == 0 を満たすかどうかで判定できます。ただ、解の構築に時間をかけてしまいました。

ややこしいことを考えず、次の手順で構築できます。

1. それぞれのグループが目標とする合計値を $T$ とする。

   $$T=\frac{a+b+c}{2}$$

2. $a_1,b_1,c_1$ を管理する配列 $V_1$ と、$a_2,b_2,c_2$ を管理する配列 $V_2$ を用意する。

3. $a,b,c$ の順に見ていき、$V_1$ の合計が $T$ に達するまでは $V_1$ に、達したあとは $V_2$ に入れる。

1つの値を加える途中で合計が $T$ を超える場合だけ、その値を $V_1$ と $V_2$ に分割する点に気をつければよいです。

C問題 Corner Meeting

要約すると、一辺が $n+1$ マスのグリッドがあり、駒 $A,B$ がそれぞれ $(0,0),(n,n)$ にいます。

• 駒 $A$：上下左右への移動、または待機
• 駒 $B$：斜め4方向への移動、または待機

両方の駒が同じマスに到達するまでの最小手数を求める問題です。

$n=8$ 程度まで実験すると、グリッドの対角線上で合流するのが最適になりそうだと分かりました。

合流地点を $(i,i)$ とします。そこへ移動するために必要な最小手数を、駒 $A$ は $M_A$、駒 $B$ は $M_B$ とすると、

となります。

したがって、$M_A\le M_B$ を満たす最大の $i$ を二分探索すればよいです。

D問題 Distant Transfers

よく分かりませんでした。とりあえず累積和を取り、途中に負の値が出るかどうかで解が存在するか否かは判定できると思いますが、正直ちんぷんかんぷんです。

Repoviveはコンテスト参加人数がまだ3桁程度の小規模な競プロサイトだと思いますが、面白い問題がちょこちょこあります。

ぜひ、コンテスト狂人の方、いかがでしょうか？

では、また。