おはようございます。しほみんです。
先週行われたABC152のコンテストについて復習したいと思います。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約30回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はABCまでは14分で早解きしましたが、D問題で大きくつまずいて、終了1分後にACしました。もっと早く気が付くべきだったのと頭の整理ができなかったのが悪いです。
パフォーマンスは早解きのおかげで778で、レートが672に上昇しました。レート以前収束方向なので頑張ってあげたいなと思います。
緑レートには到達できるには
・考えたことを間違いなくきちんと実装すること（今回のD問題）
・アルゴリズム的に効率的に解く方法を身に着ける（今回のE問題）
やっぱD問題が解けないっていうのがつらいので頑張りたいですね...
早速問題に移ります。今回はE問題まで考察して、D問題まで実装してます。
A問題
ACになるかどうかの判定です。N個のテストケースでM個正解した場合を考えます。
これはN=MならACそれ以外はWAなのでそんなif分岐をします。
if( M == N)
Console.WriteLine("Yes");
else
Cosole.WriteLine("No");
B問題
a,bが与えられた場合、aをb回繰り返した文字列と、bをa回繰り返した文字列を考えます。
このとき辞書順に早いものを答えなさい。
例）a = 3,b= 4のとき3333か444のうち辞書順で早いのは3333なので3333です。
辞書順で早いのはaかbのうち小さい方です。よってそれをif文で分岐してあとはfor文で求める文字列を出せばよいです。
これはa = bだとどっちの分岐でもよいです。
if(a <= b)
for(int i = 0;i < b;i++)
Console.Write(a);
else
for(int i = 0;i < a;i++)
Console.Write(b);
C問題
1からNの数からなる数列Pがあります。
以下の条件を求めます。
任意のj(1<j<i)のとき Pi <Pj
まあ、一つずつ頭からそれより前を検討して比較すればよいのですが、それだと結構時間がかかるので厳しいかと思います。
よってちょっと工夫して考えないとならないです。
前条件を少し考えます。
これはあるiが与えられたらそれより前の値(1からi-1まで）は全部その数より大きくないとなりません。
よってi-1個までの中で一番小さい数がi個目の数より大きければ必ず条件を満たします。
その時はカウントをします。そして最小の値を更新します。
よってこんな感じで構成できると思います。
count = 1 //i = 1は絶対満たすのでカウント
min = P[0] //最小値として入れる
for(int i = 1;i < n;i++)
if(min > P[i])
count++;
min = P[i];
Console.WriteLine(count);
D問題
まあ今回のドツボ問題です....。最上位と最下位の桁の数を見てそれがひっくり返っている組み合わせはいくつあるかを見るだけです。
模範解答としては1からNまででそれぞれci,j（最上位の桁の数をi、最下位の桁の数をjとなる数）を求めて、
ci,j×cj,iを求めて和を出すだけです。
とは言えこういう発想がなかったので自分はif文でそれぞれの桁ごとで考えていくことをやりました。forループでiが増えたとき、何個組み合わせが増えるか考えます。
場合分けは以下になります。
最上位の桁の数をi、最下位の桁の数をj、桁数をkとすると
1桁のときは常にi = j なので、数が増えると1個増えます。
2桁のときは、i = j のとき、i < jのとき、i > jのときで場合分けします。
i = jのとき、例えば22ですがこのとき(2,22),(22,2),(22,22)が増えます。よって3つ増えます。
i < jのとき例えば19ですが、91はまだ表れていないので増えません。
i > jのとき例えば91ですが、19はあるので(19,91),(91,19)が増えます。よって2つ増えます。
3桁以上のとき
i = jのとき、これだけちょっと厄介です。例えば、101を考えると11,1との組み合わせなので(101,11),(101,1),(101,101),(1,101),(11,101)の5個です。
次に111を考えると101,11,1が考える組み合わせです。同様に7個です。
121は9個、131は11個となります。
そう考えると結局3けたでは5+(十の位）×2だけ増えます。
同様に考えると4桁では25+(百と十の位の数）×2だけ増えます。
5桁では225+(千と百と十の位の数）×2だけ増えます。
5桁では2225+(万と千と百と十の位の数）×2だけ増えます。
i < jのときですが、2桁のように考えてると、必ずk-1桁以下で満たすときを考えるしかないです。よって、3桁なら2個、4桁なら22個、5桁なら222個、6桁なら2222個です。
i > jのとき、逆にk桁目も含まれます。その組み合わせは2×(10のk-1桁）です。
よって、3桁なら22個、4桁なら222個、5桁なら2222個、6桁なら22222個です。
これをコードで書けばよいです詳しくは実際書いたコードで見てください。
まあこれが最適解ではなくても6分岐程度なので書ききるぐらいの力はあった方がいい気がします。これをまとめられなかった自分は少なくとも反省してます。
E問題
ある数列Aiが与えられている。このとき次の条件を満たすBiを求め、その和の最小値を求めよ。
AiBi = AjBj (iとjは任意）。
結構厄介そうな問題ですが、できるだけ小さい数を選ぶということは、AiBiができるだけ小さいってことです。この数をＫとすると、
B1+B2+…+Bn = K×(1/A1+1/A2+…+1/An)となります。
あとはこのKですが、KはA1からAnまでの最小公倍数であればよいとわかります。
ということは最小公倍数を求めて、その数にAiで割って足していけばいいとわかります。
ただしこの最小公倍数が非常に大きくなるのでこれを工夫して求めないとACは得られないっぽいです。今回は最小公倍数を素因数に分解した形を保持することでそれを防いで求めることができるみたいです。
最後に....
D問題を書ききる力がないのは悔しいですが、E問題も勉強してアルゴリズムに対してより理解を深めたいなって思います。やっぱ問題だけだと成長効率が悪いのでどこかでちゃんと勉強したいですね...。ではでは。
