おはようございます。しほみんです。
今回は、実際にやることと理解していることの違いが分かった回でした....。それにしてもひどいですね。でも振り返らないと前に進めないので....
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約45回参加、もうすぐ一年！
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスを安定的に1000以上とる。
今回は、ABの2完、10分ですね。今回C問題は割と開放自体は単純でしたが些細な勘違いで組めませんでした。今回はパフォーマンス414で、パフォーマンスも776→744まで戻ってしまいました。
今回D問題が解ければまだよかったのかもしれませんが、そもそもC問題ができないこと自体問題なので、きちんと振り返りたいと思います。
ここから問題です。
A問題
ゴルフの飛距離を伸ばしたいです。
目標は飛距離のKの倍数なのですが、自分が出せる飛距離はA以上、B以下です。
このとき、目標を達成できるか判定してください。
素直にAからBの間にKの倍数があるか探しましょう。あったら、Yes、なければNoです。
（構成例）
for(int i = A;i <= B;i++)
if( i % K == 0)
Console.WriteLine("Yes");
return;
Console.WriteLine("No");
B問題
atcoder銀行に100円預けています。年利1%です。
X円以上になるのは何年後でしょうか？
毎年の金利は
元本の1%です。（切りすて）
よって、毎年、元本の1%を足していき、この額がxを超えていったときが答えです。
こういうときはwhile文でずっと回して、最後目標値段が達したかどうかを見ればよいと思います。元金をどんどん足すイメージです。
つまり、元金/100を足していきます。
整数型なので自動で切り捨てられます。
元本に1.01倍していってもよいのですが、毎回きちんと切り捨てて整数に丸めましょう。そうじゃないと誤差でWAになります。
（構成例）
int moto = 100;
int count = 0;
while( moto < x)
moto += moto/100;
count++;
Console.WriteLine(count);
C問題
正の整数N,M,Qと、4つの整数の組（ai,bi,ci,di)がQ個与えられます
数列Aの条件は以下です。
・Aの中の数は全部整数
・Aの中の数はiが小さい順から単調増加
4つの整数では、以下の条件があります。
Abi - Aai = Ciのときdiの点数が与えられる。
このとき、最大の点数を求めなさい。
まあなんとも取り掛かりにくいですね....
ただ、Nが10以下ということは、条件Aの数列の数は数多くはないです。
重複を許して、10か所から10個取り出せばよいので、
最大で、10H10=19C10 = 19C9です。
そして、Qの条件も50個程度なので、計算量はo(Q×19C9)が最大
なので、全部調べても間に合います。
こういうときはDFS（深さ優先検索）が有利です。
再帰で何回も潜っていって、数列を適宜作っていき評価します。
再帰はちょっと考えにくいですが、
基本構図は決まっています。
(メイン関数）
・初期条件を全部入れておく
・DFSという関数を作る
（DFS内の関数）
・判定（もし数列が完成したら処理する）
・それ以外は、DFSで潜る
具体的にはこうなります。
static void Main()
{
（初期条件）
DFS（1, 0);
(答え出力)
}
DFS(int f,int j)//fが入るべき数、jは何番目か
{
if( j == N -1)
Q個の条件を調べる（ここで作った数列の結果を出す）
else
for(int i = f; i < N;i++)
(j番目の位置の数を入れる）
DFS(i, j+ 1);//次の数はi以上である
}
今回だとelseだけに注目して考えてみれば、ただ、for文がN重で続いているだけです。
で、もしifでN個並んだ時に計算して終わるだけです。
まあ、あとはC#の書き方の問題ですが、関数間で答えを返すのが結構厄介なので、リストで答えをとりあえず入れちゃって答えを出すようなことをしました。
リストはclass内で共通変数をとれるものをやっています。
詳しくはコードを見てください。
自分は普通に昇順であるルールを無視してました。こんなあほなことしてたら答えられないですわ....反省です。
D問題
整数A,B, Nがあります。
N以下のfloor(Ax/B) - A×floor(x/B)最大値を求めなさい。
ただし、floor(x)はxを超えない最大の整数です。
xとx+Bを考えます。(xはBを超えない数）
floor(A(x+B)/B) - A×floor((x+B)/B)
= floor(Ax/B) + A - A×floor(x/B)+ A
= floor(Ax/B) - A×floor(x/B)
なので、一致します。
つまり、0 <= x< Bで考えれば十分で、最大はB -1です。
ただし、B-1よりNが小さければ、最大はNです。
ということで答えは、x = Math.Min(B -1, N)です
（構成例）
long t = Math.Min(B -1, N);
Console.WriteLine( A* Math.Min(B -1, N)/B- A * t);
最後に....
まあ、Cは普通に単純なDFSだったので解きたかったですね....日々精進です。
ではでは。
