おはようございます。しほみんです。
Judge System Update Test Contest 202004が先週行われました。言語のバージョンの更新が行われたため、その確認のコンテストです。
問題はA-D問題程度でした。問題として面白かったのでそれぞれ解説しようかなと思います（なぜかTwitterしかないのでそこら辺を埋められたら...）
普通にC,D問題はちょっととっつきにくかったです。ただ、計算時間の確認とかできたので良かったです。
あとC#であれば、基本的に.NET Core 3.1.201がよさそうです。
ほかに2つあるんですが、大体みんな使っているのがこれなのでこれでよさそうです。
ということでそれぞれ問題を確認していきます。
A問題
日が当たる座標位置はLからRまでです。最初にSの位置にいます。
日の当たる位置まで移動したいです。このとき、移動後の座標をこたえてください。
例題見るとわかるのですが、最初から日の当たる位置にいれば移動は不要です。よってSになります。
そして、S<Lのいちであれば、Lの位置が最後です。
一方、R<Sであれば、Rの位置が最後です。
それぞれで場合分けして答を得ます。
（構成例）
if(S < L)
Console.WriteLine(L);
else if(R < S)
Console.WriteLine(R);
else
Console.WriteLine(S);
B問題
赤色の玉と青色の玉があります。それぞれに数字が書いてあります。
以下のルールで取り出します。（原文まま）
・袋の中に赤のボールがあるとき、残っている赤のボールのうち最小の整数が書かれたボールを袋から取り出す。そうでないとき、残っている青のボールのうち最小の整数が書かれたボールを袋から取り出す。
このとき、取り出した数字の順を並べなさい。
問題正しく読み取ることが大事です。
要するにまず赤玉の小さい順に取り出して、青玉の数字を小さい順に取り出す。
ってことです。
なので、プログラムとしては
1.読み込んで、赤か青か判定
2. 色に応じてListに入れる
3.Listをソートする
4.赤色のリストを全部取り出す
5.青色のリストを全部取り出す
C#ではリスト型があり、それを使うと配列数を定義しなくてよいので楽だと思います。
（構成例）
Lisr r = new List<int>();
Lisr b = new List<int>();
for(int i = 0;i < n;i++)
string[] s = Console.ReadLine().Split(' ');
if(s[1] == "R")
r.Add(int.Parse(s[0]);
else
b.Add(int.Parse(s[0]));
foreach(var x in r)
Console.WriteLine(x);
foreach(var x in b)
Console.WriteLine(x);
C問題
積み木の問題です。
左からa1,a2,a3で並んでいます。
3>=a1>=a2>=a3>=1です。
このとき、以下の条件を満たします。（原文ママ）
左から 個目の山の下から 個目の積み木に書かれた整数を で表す とき、
この時数字の通り数を求めなさい。
うーんぱっと見わからない問題ですが、これはDFSで解くことが可能です。
あとはパターン数がただ10通りしかないのでそれぞれ数えるのもあります。
今回はDFSで解くことをかんがえます。
とはいえ直感的にDFSとは結びづらいのでどう考えるからかです。
書いてある番号はつまり、積み木の積む順番としてみましょう。
そうするとすんなり考えられます。
このとき、何を再帰にするかですが、それはそれぞれf(a1,a2,a3)で考えるとよいです。
あとのロジックはこうです。
まず、f(1, 0, 0)で考える。
もしf(a1,a2,a3)であれば、それは積み方として成立するので1をカウントする
つまり、このDFSでこういう積み方はちゃんと命題通り積めているよねって考えていきます。
ここまでくればあとは、
・まずa1は自動で積むパターン
・a2はa1より小さいとき積むパターン
・a3はa2より小さいときに積むパターン
でそれぞれ考えてみてどんどん細分化していけばよいのです。
詳しくはコードを確認してください。
D問題
長さNの数列Aがあります。（要素はA1,A2,....,An）
このとき、Q個整数が与えられるのでそれぞれ結果を出力せよ
・整数Xを与えたとき、j = 1,2,3....,nにおいてgcd(X, Aj)をXに置き換えることをかんがえる。もし途中でX=1になれば、その置き換えた回数（要するにj回目）、最後までX=1にならなければ最後のXを出力せよ。
まあ素直に考えたら、それぞれの整数にたいして、毎回gcd（最小公約数）を求めていけばよいですが、NもQも10の5乗個あるので果てしない時間がかかります。
よって計算改善が必要です。
で、まずは問題考察します。
j回作業した後は、(A1からAjの最大公約数）とＸの最大公約数となるのわかります。
（3つの数a,b,cの最大公約数を考えるとき、aとbの最大公約数を考えてから、その数とcの最大公約数を考えるのとaとcの最大公約数を考えてから、その数とbの最大公約数を考えても同じから言える）
つまり、まずgcdnという配列を作ります。
gcdn：(i + 1)番目までの数字までの最大公約数
これは全部のQ個の数に適応するのでわざわざ毎回最大公約数を作らなくてもよくなります。→計算量削減
あとはこの最後尾とXの最大公約数を見てこれが1でなければ、すべての操作をしても終了しないので、それをそのまま答えにします。
で、もし最後がX = 1であるということは必ずどこかで終了しています。それを求めればよいのです。
このとき、また頭から順番になるとo(N)の計算がかかり、o(NQ)の可能性があるので間に合いません。
ここで、二分探索を使います。今回gcdnは必ず単調減少なので使えます。
これで計算時間がo(QlogN)で間に合います。
二分探索の際は、minがX =1であるかどうか担保されていないことに注意して実装します。
詳しくはコードを見てください。
最後に....
正直このコンテスト結構難しいです。自分も普通に戸惑って解けなかったです。ただ、いくつか確認すれば、今までの知識の組み合わせなので、きちんと理解して使っていきたいですね。
あと確認しておいてよかったです。そうじゃないとコンテストでマジで詰んでいた気がします。
ではでは。
