おはようございます。しほみんです。
2週間前の復習です。ここから最近調子よく解けているので、ようやく軌道に乗ってきたかなあって感じです。もっと早く解きたいのが悩みです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。PAST58点の初級レベル。
・基本的に時間がないのでぶっつけ本番でやっている。現在48回参加、もうすぐ一年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回は、ABCDで30分、1WAでした。まあ、そこそこですが、みんな簡単に解けていたのでレートは低めでした。でも、パフォーマンス1010と744→774で復活してきました。
今回みたいなE問題は結構定番みたいだったのできちんと解きたいところです。A-D問題は速度的に悪くはなかったです。BとCは似た問題だったので、丁寧に解けたのはまあよかったかなと。
今回はE問題まで振り返って終わります。
ここから問題です。
A問題
ABCかARCが与えられます。ABCとARCは交互に開催されます。
次はどっちか出力しなさい。
これはifで分岐するだけです。
（構成例）
if(s == "ARC")
Console.WriteLine("ABC");
else
Console.WriteLine("ARC");
B問題
N人の人がいます。（N1,N2,N3,...,Nnとする）
K種類のお菓子があり、それぞれNiの人がそのお菓子を持っています。
お菓子を持っていない人にはいたずらをします。
いたずらをする人数を求めなさい。
これもそれぞれ条件をすべて読んで、お菓子を持っている人にフラグを立てます。
そして、そのフラグが立っていない人はお菓子を持っていないので、それを数えればよいです。
（構成例）
for(int i = 0; i < n; i++)
{
int d = int.Parse(Console.ReadLine());
string s = Console.ReadLine().Split(' ');
for(int j = 0; j < d; j++)
ans[int.Parse(s[j]) -1]++;
}
for(int i = 0;i <n;i++)
if(ans[i] == 0)
count++;
Console.WriteLine(count);
C問題
Nこの展望台があります。i番目の展望台の高さはHiです。また、異なるM個の道があって、それぞれ展望台iと展望台jがつながっています。
いい展望台はどのつながっている展望台よりも大きい必要があります。
このときいい展望台の数を数えてください。
うーんパッと見た感じ結構まとめるのが面倒な感じです。
でもよくよく考えたら条件を丁寧に追っていくだけです。
自分はまず全部いい展望台だとして、それぞれ条件を調べていくと満たさないものがあるのでその時は省いていくってことをしました。
最後に残った展望台をカウントして足していくだけです。
ただ、どっちも同じ場合は両方可能性がなくなることに注意です。
（構成例）
long H = new long[n];（ここにそれぞれの高さを入れる）
for(int i = 0; i < m;i++)
string[] s = Console.ReadLine().Split(' ');
if( H[int.Parse(s[0])] > H[int.Parse(s[1])])
ans[int.Parse(s[1])]) = 0;
else if( H[int.Parse(s[0])] < H[int.Parse(s[1])])
ans[int.Parse(s[0])]) = 0;
else//両方同じとき
ans[int.Parse(s[0])]) = 0;
ans[int.Parse(s[1])]) = 0;
for(Int i = 0;i <n;i++)
sum += ans[i];
Console.WriteLine(sum);
D問題
(aの5乗）-（bの5乗）= Nを満たす(a,b)を求めよ。
ただし、Nは存在するa,bの時の数しかない。
Nの制限条件を見ます。Nは10の9乗までです。
だとするとa,bは1000から-1000もとれば、a、bは10の15乗から-10の15乗をとるので、
なんかもとめるNは出てきそうです。
ということで、全探索します。
aもbも負であることと、aもbも正であることと反転の関係になるので、
aは0から1000、bは-1000から1000までで調べれば十分です。
（構成例）
for(int a = 0; a <= 1000; a++)
for(int b = -1000; b <= 1000;b++)
{
if(a*a*a*a*a - b*b*b*b*b == 1)
Console.WriteLine(a + " "+ b);
return;
}
E問題
N人の参加者がいて、i番の人の身長はAiです。
そして、極秘取引する人は以下の条件です。
・2人の番号の絶対値の差は身長の和に等しい。
この満たすペアの数を求めなさい。
うーんこのまま考えてしまうとどうあがいてもN(N-1)/2通りを全部求めないとならないので、厳しいです。自分はここで詰まって終わりました。
ここでは式変形を考えてみます。
2人の番号をiとj（i < j）とします。すると上記条件は以下のようにあらわせます。
j -i = Ai + Aj
これを変数分離で分けます。
Ai + i = j - Aj
Xi = Ai+i, Yj = j- Ajはあらかじめ求めておけます。
あとはどうやって比較するかですが、i < jの条件をうまく使っていきます。
forループで実はできます。0からN - 1まで考えます。変数をxとします。
1. j = xのYiを求めます。そしてsum[Yi]の数求めます。
2. 最初にi = x -1の時のXiの数値を記録しておきます。(sum[Xi]とかで配列を作ります）
あとはこれを繰り返します。
こうすることで2のときsumの配列にはi<jの条件のものがすべて入っています。
そして次の1に戻って追加するとi+1のものがはいるので、次の2はj+1でi +1 < j +1で成立したまま考えられます。
そこのループはこんな感じです。
for(int x = 0; x < n;x++)
ans += sum[Yi];
sum[X(i-1)]++;
ただし、sumのとる数は限られるので境界条件だけは気を付けてください。
詳しくはコードを見てください。
最後に....
E問題は変数分離さえできればなんとかできた気がしますね。また一歩強くなりたいものです。ではでは。
