おはようございます。しほみんです。
1週間ぶりに競技プログラミングが行われたのでその話をします。この前あったABC154についてです。問題セットとしては通常のABCのセットのように感じます。
競技プログラミングでやっていること地味に業務で役立っているので大助かりですね。緑までいければ、仕事としてのエンジニアは結構やっていけるのはあながち間違いないと思います。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約35回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回は30分でABCDの4完でした（C問題で2回ミス）。パフォーマンスも878で久々の緑で、レートも672→695とようやく700まで到達できそうな感じです。とはいえ正直この程度なら20分でできたのでちょっと辛い感じでした。話は分かっても実装力の足りなさを身に染みたセットでした。
それでも、D問題は比較的簡単に突破できましたし、C問題のしょうもないミスさえなければよかったかなあと思います。E問題も考え方自体はなんとかできたのですが、うまくまとめられなかったです。あれも典型問題みたいだったのでもっとできるようにはしたいところです。
今日はE問題まで復習して終わりにしようと思います。E問題は工夫してごり押しで復習して解きました。
ではここから振り返ります。
A問題
文字列Ｓと書いたボールがA個、文字列Tと書いたボールがB個あります。
文字列Ｕ（SかT）が与えられるので、その時書かれていた文字列のボールを1個捨てます。
それぞれS,Tのボールの数を求めなさい。
基本の入出力ができるかどうかの問題です。
UがSのときはSがA-1個、TがB個
UがTのときはSがA個、TがB-1個です。
これを素直に出力します。
構成例
（入力は割愛します）
if(U == S)
Console.WriteLine(A-1 + " "+B);
else
Console.WriteLine(A + " "+B-1);
B問題
文字列Sが与えられます。すべてを"x"に置き換えてください。
問題の通りなのですが、プログラムでやるなら
1.Sの文字数を数える。
2.forループで文字数だけ繰り返し"x"を出す。
です。
（構成例）
string S = Console.ReadLine();
int s_num = S.Length;
for(int i = 0;i < s_num;i++)
Console.Write("x"); (Writeにすると改行しないです）
C問題
整数列A1,A2,...,Anがあります。すべて数が異なるならYES、そうでないならNOと出力します。
まあ普通にやると計算量がNの2乗で間に合わないです。そしたら、隣同士で比較できないか考えます。
ソートをしたとき、全部違うなら隣同士の数は必ず異なります。これを使えばよいです。
方法として
1. ソートする
2. 一番前からひとつ隣の数を比べて同じ場合はNOを出力して終わり。
3. 全部無事とおればYESで出力。
（構成例）
（入力は省きます。数列はa[i]で示します。）
Array.Sort(a);
for(int i = 0; i < n-1;i++)
if(a[i] == a[i+1])
Console.WriteLine("YES");
return;
Console.WriteLIne("NO");
まそもそもYES,NOの出力を普通にYes,Noと間違えたり、forの条件ミスだったりしょうもないことしたので要反省です。（ミス一回に5分のペナルティなので致命的です）
D問題
Nこのさいころが1列に並んでいます。それぞれのさいころは1からpiまでの目を持ちそれぞれの出す確率は1/piです。隣り合ったＫ個のさいころで期待値が最大のときを求めなさい。
まず、それぞれのさいころの期待値を考えます。この条件のさいころの期待値は
1+(pi-1)×0.5です。具体的にpi =2, 3, 4, 5ってやっていくとわかります。
あとは単純にすべてのありうる期待値を求めます。ただ、効率よく求めるにはちょっと工夫して解きます。
まず、前からK個の期待値の和を求めます。
次は1番前のさいころの期待値を引いて、K+1個目のさいころの期待値を足します。
するとひとつ隣の状の期待値が出ます。これを繰り返して求めます。
（構成例）
(入力は省きます。数列p[i]とします。）
double sum = 0;
double ans = 0;
for(int i = 0; i < k;i++)
sum += 1.0 +(p[i] -1)*0.5;
for(int i = k;i < n;i++)
sum -= 1.0 +(p[i -k] -1)*0.5;
sum += 1.0 +(p[i] -1)*0.5;
if(sum > ans)
ans = sum;
Console.WriteLine(ans);
E問題
1以上N以下の数で10進法で表したとき0以外がk個あるモノを求めなさい。
結果を言えば、桁DPを使えば解けるみたいです。
実際は使わないで解いたので、一応考えた過程を話します。
最初見たときちょっと厳しいなと思いました。
なので制約条件をまず見ました。
1 <= N <= 10の300乗、Kは1,2,3
ここから
・Nがこんなに大きい数の時点で桁でforループしかできない
→1桁の数、2桁の数でそれぞれ条件を考えたらできそう
・Kの数の少ない
→Kで場合分けしたら解ける
ということで考えました。
K = 1のとき
0以外が1個しかないってことはn桁の数のときは最高位の数が1から9しかとりえないです。
よって、単純に最高位の桁の数で決まってしまいます。
例えば、100であれば、1-9,10,20,30,40,50,60,70,80,90,100で19個です。
これは(桁数-1)*9+1で出ます。
よって(最高位の数)＋(桁数-1)*9です。
forループでやるなら、頭の桁のときはその数を足して、それ以外は単純に9足していけばよいです。
K = 2のとき
まあ同様なのですがn桁の数を考えます。
最高位の数は必ず0ではないので、1-9であり得ます。
それ以外の数は1つのどこかの桁を選んで任意の1-9を代入できます。
ということは(最高位の桁-1)*9*(桁数-1)です。
それ以下の場合は最高位が9として考えればいいので、9*9*(桁数-1)です。
ただ、与えられたNを頭から読むと1文字目は最高位なので、上の方法だと最高位と0が桁数だけ続いた数だけしか判定しないです。
例えば、314159だったら300000以下の数しか判定してないです。例えば301000とかは数えられていないです。
それを数えるために、次の桁も注目します。これが0なら結局、数えるべき数は更新されないので、スルー出来ます。0以外なら、数えられるので数えます。
314159なら、3の次1を数えると300000から310000のなかで満たす条件を考えます。このとき、あり得るのは310000か3桁目以降が1-9のどれかをとるときなので、1+4*9=37個です。これも足します。
K=3のとき
K=2と同様に考えます。n桁を考えると（最高位の数）以外に2つのどこか1から9を取ればよいとわかります。
よって
（最高位の数-1)*9*9*(桁数-1)*(桁数-2)/2
です。
それ以下の数は9*9*9*(桁数-1)*(桁数-2)/2です。
例外処理も同様に考えて、0以外の数が2回目のときと3回目のときでそれぞれ桁の選び方だけ考えて足せばよいです。（すいません力尽きました....）
足し方はコードを見てください。一応DP的ではある気がします…
最後に...
E問題は知らなくても解けるんだななあと思いました。ただ、DPもあんまり使いこなせていないので、それも併せて復習しておこうとは思います。ではでは。
