おはようございます。しほみんです。
実は最近、競技プログラミングの問題解きとファイアーエムブレム風花雪月しかやっていないので、内容がしょぼいですね....
でも、政治もなんか突っ込んでもしょうがないし、経済も一向にいい感じに動くこともなく、会社も自分の存在を捨ててる感じがするのでうーんどうしようかって感じです。
まあ株価は無事ですね。
ただ、昨日に続いてABC167について復習していきます。
今回はDとE問題です。
D問題
町が1からNとN個あります。それぞれテレポートできる装置があり、テレポートは町iからjから移動すると決まっています。
王様は町1からK回テレポートした場合どうなるか知りたいです。
このときの町の位置を求めなさい。
うーん最初は気が付かなかったのですが、テレポートの方法は大きく二つです。
1. 町1からいくつかの街を回って町1に戻る
2.町1からいくつかの街を回って、町iに戻って、町iからその間の街をぐるぐるする。
このどっちかです。
ただ、1は町が1にもどるだけ一般的には2の方法です。
これを素直に実装します。
方法としては、
1. まず町１を入れる。
2. 町1からどんどんワープして記録していく。このとき行った町は記録する
3. ワープしていくと一度言った町に戻ることがある。この時、この町の場所を記録する。
4. 最後にKの回数におうじて、町の位置を考える。
結構書くのが面倒ですが構成例を示します。2はwhileで3になったらbreakする手法です。
（構成例）
int a = new int[n];//ここはどの町がどこに行くか記録する
int town = new int[n]; //ここに訪問したかどうかを記録する（訪問済みを-1にする）
int[] to = new int[n];//ここに訪問した町順を入れる
int back = 0;//戻った時、訪問して何番目の町か記録
1の手順
int townfrom = 0;//最初の町
town[0] = -1;//訪問済みにする
to[0] = 0;
int count = 1;
2の手順
while(true)
townto = a[townfrom];
if(town[townto] == -1)
break;
to[count] = townto;
count++;
townfrom = townto;//これで次の街を見つける
3の手順
for(Int i = 0.i < n;i++)
if(to[i] == townto)
back = i;
break;
4の手順
if(k <=r)
Console.WriteLine(to[K]);
else
Console.WriteLine(to[ back + (K -back) %(count -back)]);
E問題
N個のブロックが一列並んでいます。
・それぞれ色1からMまで塗る。使わない色があってもよい。
・隣同士で同じ色でもよいのはK組以下である。
この時の塗り方の総数を求めなさい。非常に大きい値なので998244353で割った余りで出しなさい。
なんとなく組み合わせの問題な気がします。ということでnCkを考える問題です。
nCkはメモ化でo(1)で求められます。この考え方はテンプレなので覚えておきましょう。
で、肝心の組み合わせですが、
K回重複を許す時を考えますが簡単にK=0とK=1を考えます。
まずは、一番最初はM色です。
そのとなりはM-1色です。ということを繰り返して考えます。
K= 0のとき、重複しないのでM×(M-1のn-1乗数）になります。
ここで重複する場合を考えます。
K=1を考えます。このとき、隣同士は1つです。
そのとき、1か所は1色に限定されます。
よって、M-1色ぬれる場所が1か所減らせます。
M×(M-1のn-2乗数）です。あとはこの重複する場所を考えます。これはn-1か所の中から1か所選べばよいので、n-1C1通りです。
よって、n-1C×M×(M-1のn-2乗数）です。
ここからどんどん考えていくKについて一般化できます。
K回重複を許すときは、n-1Ck×M×(M-1のn-1-k乗数）通りです。
あとはこれを求めていくだけです。メモした二項定理と繰り返し二乗法で求めていきましょう。
詳しくはコードを見てください。
これに気が付いていたのですが、添え字ミスしてACできなかったので今度はちゃんと回答できるように頑張ります。
最後に....
よく考えたらそれぞれのABCの解説って企業側がやってくれているのでとくにいらないのかもしれないですね。今度から簡単に考え方だけにしようかなと思っています。
とはいえ、自分がきちんと説明できることは大事なのでブログに残すのも大切だと思っています。役に立たないかもしれないですが、見守ってくれたら路思います。
ではでは。
