なにこれ？
解説記事というよりはどういうことを考えて解いたかの感想みたいな記事
GTXC-GS って何？
去る2023-12-28日にMojacoderで行われた競技プログラミングの有志コンテストです。
開催者はまっちゃラテ(@matcharate_12)という方らしいです。
良かったらTwitterのフォローをお願いします(?)
問題構成
問題名を押すとMojacoderに飛びます
A - Swap to Right
B - Footprint 2
C - Graph Palindrome
D - Prevented to Carry Snowman
E - Jingle, Jingle, Presents!!
F - Walnuts in Xmas Lease
G? - From matcharate12
Ex - Prevented to Carry Snowman REVENGE
感想
A - Swap to Right
1 発で通せませんでした。
同じ長さの 2 つの文字列 S, T が与えられていて S のどこかの文字が右にズレると T になるみたいです。制約に "答えは一意に定まる" とあるので S="aaaaaaab" で 1 文字目の a を 2 回シフトするみたいな入力はなさそうです。なのでなんとなくズレた場所ははっきり分かる → S と T で文字が違う範囲はシフトしていると分かりそうみたいな推測を立てました。
ここから、S[i] ≠ T[i] となるような一番小さい i, 一番大きい i を見つけてその差がシフト回数としたら通りました。
B - Footprint 2
シミュレーション問題です。長さ K の文字列 S が与えられ、rate 君は S に従って座標を移動していきなんとやらという問題です。S の 1 文字ごとに対応する処理を書けば良いです。
このとき、
if(S[i] == 'L')
{
// L の時の処理
}みたいなのを 4 つ書いてもいいですが
pair<int, int> now; //今いる座標を管理
const string direct = "LRUD";
const array<int, 4> dx = {-1, 1, 0, 0};
const array<int, 4> dy = {0, 0, 1, -1};
for(int j=0; j<direct.size(); ++j)
{
if(S[i] != dict[j])
contiue;
now.first += dx;
now.second += dy;
}みたいに書くと楽です。
雪玉を大きくするゲームというと(正確には違いますが)ニンテンドーDSのNew スーパーマリオブラザーズのミニゲームの雪玉を転がすやつを思い出します。
C - Graph Palindrome
与えられた無向グラフが回文グラフであるかを判定する問題です。
無向グラフの任意の２頂点間に道が存在するかを判定できれば良いので UnionFind というデータ構造を使うと楽に解けます。
D - Prevented to Carry Snowman
持っている雪だるまの大きさが U_i (1 ≦ i ≦ K)のときにそれぞれ最大で何回移動できるかを答えるという問題です。グラフ問題です。入出力例 1 のグラフはこんな感じです。(有向グラフになってるけど)
頂点数が N で辺の数が N-1 ですので同じ頂点に複数回行かないように BFS(幅優先探索) を適切に実装すれば、各 U_i について O(N) で探索を行うことが出来ます。なので K 個の U_i 合わせると O(K×N) で、制約からこれは間に合います。
E - Jingle, Jingle, Presents!!
シンプルな問題文です。条件を満たす区間の個数を答える問題です。
ちなみに自分は l < r なことに気づかずに時間を溶かしました。
この問題の解法を思いつくには少し慣れ/経験が必要なように思います。
まず愚直に考えると、左端 l (1 ≦ l ≦ N-1) を決めて後は右端 r を可能な限り伸ばすという O(N^2) 解法が思いつきます。しかし、この方法では TLE しそうです。
思うに今回気づくべきは「ある整数の組 (l, r) が条件を満たすときには、この区間内に含まれる区間は全て条件を満たす」という性質です。ある (l, r) が条件を満たす場合は (l, r), (l-1, r), ..., (r-1, r) は全て条件を満たします。
ここから、全ての r について、条件を満たすような最大の l を探すことだけに集中すれば良いです。ある r において条件を満たす最小の l が分かればその l で条件を満たす (l, r) の個数も簡単に数えられます。r-l です。
これはしゃくとり法によって O(N) で行うことが出来ます。
F - Walnuts in Xmas Lease
複数個ある鈴の中に入っている最大のクルミの個数と最小のクルミの個数の差を少なくするという問題です。鈴を指定してそこにクルミを足すという操作を W 回までできます。この問題では差を小さくしていきたいので、操作をする時点でクルミの個数が最小の鈴に入れていけば良さそうな感じがします。で、ここからは実験的に考察を行いました。
3 2
1 1 3のような入力例のときには操作後のクルミが
1 3 3ではなく、
2 2 3となるのが最適です。なので個数が最小のクルミが複数あるときはその全てに同じ数を足すのが良さそうな感じです。また、最小値をなるべく大きくしていきたいことから、個数が最小の値には２番目に小さい値になる、もしくは近づくようにクルミを足していけば最小値を常に大きくしていけそうという感覚になります。
これは map などでシミュレーションすれば良さそうです。
G? - From matcharate12
超難問です。クソ難しい。ARCかこれ？公式解説を見たほうが良いです。こんな感じでなんとか解きました。
(1) 1 回の交換で好きなところに 1 つ数字を配置できて、最後の 1 つは自動的に配置できるので N-1 ≦ K なら目標は達成できる。
(2) ありえる順列を頂点の状態に見立ててBFS?→頂点数 N! なので無理
(3) 状態をグラフにするのではなく、操作をグラフにできないか試す
→ 本来配置してあるべきところと交換しなければならないのでその位置との辺を引く
(4) N=4 で 2 1 4 3 や N=5, 3 1 2 5 4 の例を試して、なんか行けそうな気配を感じ取る。そして (1) の考え方の「最後の 1 つを自動的に配置できる」ようなまとまりに分けるのがポイントだと気づく。3 1 2 / 5 4 みたいな。
(5)まとまりの個数-1の和が順列にする回数なので UnionFind で連結成分の個数を求めて、やる。
(6)なんか解けた
Ex - Prevented to Carry Snowman REVENGE
グラフ問題です。とりあえず適当に K を固定して考えてみます。
与えられた有向グラフは標高が高い街から低い街にしか移動しないため DAG (閉路がないグラフ) です。仮に DAG じゃなくすると閉路をひたすら移動することで雪だるまを無限に大きくできる場合があるからかも？ベルマンフォード法ならこれでも解ける？
まず、問題内容から見て greentea 君はできるだけ大きい雪だるまを持って移動した方が良さそうです。なので、変数/状態として dp[i]:=「街 i にいるときに持てる最大の雪だるまの大きさ」があれば良さそうです。
次に dp[i] をどのように求めるかを考えます。ある街に行くための経路は１つに定まるわけではないため、単純な BFS だと↓のような街 i (1 ≦ i ≦ N-1) から 街 j ( i+1 ≦ j ≦ N) に辺がある完全グラフみたいな形の場合に TLE しそうです。
で、今回は DAG なのでトポロジカルソートして DP (動的計画法) という方法が使えそうです。が、自分はダイクストラ法で通しました。
情報として (持っている雪だるまの大きさ, 今いる街の番号) を持てば出来ます。
持っている雪だるまが小さい順に行動していって無駄な動きが出ないようにすればダイクストラ法になる。説明がうまく出来ないのでコードを見てください。
次に K の値の探索ですが、K には単調性がありそうです。つまり、ある K の値で街 N にたどり着けないならそれより大きい K でもたどり着けなさそうです。なので、これは二分探索をすればたどり着ける K / たどり着けない K のしきい値を見つけられそうです。(決め打ち二分探索)
最後に
誰もが灯台下暗し