おはようございます。しほみんです。
今日は先週行われたABC158の話をします。今回はE,Fの正答数を見るにかなり難しかったみたいですが、D問題までは標準なので、茶コーダーとしてはいい問題セットだと感じます。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは750程度になりました。緑まであと一歩です。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約37回参加、9か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。パフォーマンスを安定的に1000以上とる。
今回は20分でABCの3完でした。D問題は解けるべきでした。やっぱこういう文字問題はなれていないのでだめです。3完はできるべきなのであんまり伸びませんでした。パフォーマンスも612で、レートも741→729と下がっています。
まあ、この程度のDは解けないとやっぱ緑にはなれないですね....緑上位以上（レート1000以上）は明らかにアルゴリズムやプログラミングの知識に穴があると達成できないのでコツコツ参加して穴をなくしていこうと思います。
今日はD問題まで復習して終わりにします。
ここから問題です。
A問題
3つの駅ああります。それぞれの駅の管轄は路線AかBです。
今後このバスでこのA路線とB路線をつなごうと思います。つなげるかどうか判定してください。
なんかざっと見わかりづらいですが、例題見るとわかります。
ABAとなると2つの駅がA路線所属、1つの駅がB路線所属です。よってこの3つの駅では路線AとBがバスでつなげるのでYesです。
一方、BBBとなるとすべて駅が路線B所属なのでこの駅たちではバスでつなげないのでNoです。
と考えるとAAAとBBB以外はYes、それ以外はNoです。
実際よくわからなくても直感的に全部同じ記号かどうか判定するとかを瞬時に判定して書きたいです。（緑コーダーならそれぐらいすんなり気が付きたいです）
（構成例）
if( s == "AAA" || s =="BBB")
Console.WriteLine("No");
else
Console.WriteLine("Yes");
（実際書いたコードはもっと汎用性が高く、すべての文字が同じと区分しています）
B問題
赤と青のボールがあります。
10の100乗回以下のことを繰り返します。
青をA個並べる、赤をB個並べる。
このとき、前からN個の青の数を数えてください。
まあ、普通にA+B個並ぶを実質無限回繰り返すので、その繰り返し回数を数えて、あとはあまりの数に応じて青の数を足します。
1. count = N/(A+B) で繰り返す数を出す。
2. res = N - count *(A+B)で余りを出す。
3. answer = count*Aで繰り返し数分の数を足す。
4. res > Aのときは青全部なのでAを足す。それ以外はresを足す。
よって
answer = count*A + A (res >A)
answer = count*A+ res (res <=A)
地味に数が多いのでlong型で処理することを忘れないようにしましょう。
（構成例）
long count = N /(A+B);
long res = N - count*(A+B);
if(res >A)
Console.WriteLine(count*A + A);
else
Console.WriteLine(count*A + res);
C問題
消費税8%のときはA円、消費税10%のときはB円です。
これを満たす最小の数を求めなさい。
自分は二分探索で出したのですが、普通にA,Bの制約上限が100なので、最大でも100/0.08=1250円までしかありえません。だったら、普通に1円から全探索して答えが見つかった時点で答えを出して、ない場合は-1を出せばよいです。
（構成例）
for(int i = 1; i <=1250;i++)
int com8 = i * 1.08;
int com10 = i * 1.10;
if(com8 == i + a && com10 == i + b)
Console.WriteLine(i);
return;
Console.WriteLine("-1");
（コードの方は二分探索の例です）
D問題
クエリの問題です。初期文字列sが与えられます。
クエリは以下の2つです。
クエリ1: 文字列を反転する
クエリ2: 一番前か一番後ろに文字を新たに入れる。
最終的にできた文字列を出力してください。
まあ素直に実装したらTLEになります。ということで工夫します。（工夫ミスってできませんでした）
クエリ1は反転をいちいちしていると時間がかかります。よって、反転しているかどうかを記録しておくことで処理を軽くします。
クエリ2もただ文字を追加すると時間を食うので、まずはStringBuilderを使って、Appendすると高速処理します。ただし、System.Textが必要です。
一番後ろはただ追加すればよいですが、問題は前です。
前の文字は前にどんどん足していくことをかんがえると、追加して最後にその追加した文字列だけを反転したらおっけーです。
ということで結果としては、（前に追加して文字列を反転させた文字列）と（最初の文字列）と（後ろに追加した文字列）を足します。
あとはクエリ1で最後判定しているかどうかを見て出力します。
これだと0.3秒で処理できます。やっぱり工夫して処理することはたいせつですね。ここら辺はきちんと業務で生かしていきたいところです。
詳しくはコードを参照してください。
最後に...
計算改善といい、アルゴリズムの知識といい、パフォ1000以上を常に出すには知識の深さが必要ですね。もっともっとうまくなりたいです。ではでは。
