https://atcoder.jp/contests/abc162おはようございます。しほみんです。
今回はTLEに苦しめられて時間をめっちゃ食いました。そのせいでちょっとダメージ受けました。なんとか答えられたもののまだまだだなと感じます....
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスを安定的に1000以上とる。
今回は95分でABCDの4完でした。D問題で二重ループからうまく処理することを普通にとちってました。最後なんとかACしましたがよくよく考えたらもっと簡単にできたやんって思います....。パフォーマンスは813となり、Dまで解ければとりあえず緑レートは確保できそうだとわかりました。レーディングも798→800で緑コーダに一応復帰です。
D問題で頭使い尽くしたので....今回はD問題までにします。E,Fはまた今度見直します...。
ここから問題です。
A問題
3桁のNが与えられます。いずれかの桁が7ならYes、それ以外はNoで答えます。
まあNをstring型で読み込み、それぞれの桁が7かどうかを見ればよいです。
string型で1文字取り出す場合はchar型になるのでその区別をする必要があります。
string型はクォーテーションマーク（”）でくくる。
char型はアポストロフィー(')でくくる。
このことに注意して解きます。
（構成例）
string s = Console.ReadLine();
if(s[0] == '7' || s[1] == '7' || s[2] == '7')←char型なので'7'
Console.WriteLIne("Yes");←string型で出力なので"Yes"
else
Console.WriteLine("No");
B問題
FizzBuzz問題をちょっと改変したやつです。
nが3で割り切れたらFizz、nが5で割り切れたらBuzz、nが3でも5でも割り切れたらFizzBuzz、それ以外はnが出力されます。
この時nまでに出力された数字の和を求めなさい。
FizzやBuzz、FizzBuzzは数字じゃないので要するにそれ以外は数えればよいです。
そしてそれ以外の数って要するに3でも5でも割り切れない数です。
ということでその時だけ足していけばよいです。
（構成例）
long sum = 0;
for(int i = 1; i <= n ;i++)
if(i % 3 != 0 && i % 5 != 0)
sum += i;
C問題
k以下の数を任意で3つ取り出します。その3数の最大公約数の和を求めなさい。
問題自体はΣ記号で使われていますが、解釈するとこうなります。
重複が許されるので、全部でkの3乗通りです。
そして今回は「kは200以下」なので、全部数えてもo(10の7乗)で間に合います。
ということで素直に最大公約数を求めて出しましょう。
最大公約数は2つならユークリッドの互除法で求められます（これ自体の計算はlog(max(a,b))でるので、あの計算量を間に合います）。
3つなら、2回すれば計算できます。
詳しくはコードを見てください（ユークリッド互除法は関数化してしまうと計算が楽です）。
D問題
N個のボールが並んでいます。それぞれ色は、赤緑青（RGB）のどれかです。
それぞれの色を取り出します。
ただし、それぞれの場所をi, j, k（i > j > k)とすると、i -j ≠ j -kとなる場所である。
この時取り出し方を求めなさい。
R,G,Bの位置は決まっています。なので、まずはR,G,Bの位置をそれぞれ取り出します。
あとは、それぞれの位置は完全独立なのでそれぞれの位置の組み合わせを考えて、上の不適格なものを省きます。
しかし、これだとR,G,Bの3重ループになってしまいます。
今回はS が4000以下なので、1333の3乗の計算量となってしまい時間が足りません。なので、もう一つ工夫が必要です。
今回二重ループなら解けるので、二重ループにして考えたいです。
上記条件を見直しましょう。例えば、iとjの位置が決まれば、kの位置として不適格な条件はおのずと決まります。
ということはまずは2つの位置の候補を決めてしまえば、あと1つでダメな条件は限られています。その時は省いてしまえばよいです。
また、あと1つの位置ですが、それぞれ候補はiかjかkなので、それぞれの位置において適合するかどうかを決めます。
i - j = j - kを満たすのが、
三つ目の位置が
iのとき、2*j - k
jのとき、(i+k)/2（整数）
kのとき、2*j - i
です。これらのときだけ不適当なのでそれを省きましょう。
となると構成はこうなります。
for(Rの個数）
for（Gの個数）
{
x =（Rの位置）
y = （Gの位置）
count += （Bの個数）
if（2x - y == （Bの位置））
count--;
if（(x+y) /2== （Bの位置））
count--;
if（2y - x == （Bの位置））
count--;
}
あとはそれぞれの使い方です。
基本数がいくつ入るかわからないし、入った数だけ使いたいのでList型が便利です。
ただ、全部List型で使ってしまうと、Bの位置特定する際にContain関数をつかわないとならず、これは計算時間を食います。自分はこれでTLEくらってずっと悩んでいました。（最後は荒業で無理やり解きました）
ただ、冷静に考えたら、最後のBの位置は記録しておけばよいので、普通にArray型で、数が入ったときだけに1を入れておいて、そこにBがあるか判定すればよいです。
よってR, GはList型で位置を記録、BはArray型で位置を記録して上の二重ループをすれば劇的に改善できます。100ms程度でACしました。
あとはコードを参照してください。
こんなふうに計算改善をすぐに考えて実装できるとよいですね。
最後に...
やっぱり計算量の改善は大事ですね。やり方としては単純にやる方法からどこを高速化できるかを考えて、改善するとよいです。いい練習回でした。
ではでは。
