おはようございます。しほみんです。
unratedになってしまったコンテストです。これならそこそこできたので何とも悔しい感じです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスを安定的に1000以上とる。
unratedだったので、時間とか特に気にしません。ただ、割とやりやすい問題をさっさと思いつけたなって印象です。ただ、実装に時間がかかったので順位が悪いですね...
ここから解説です。D問題までにします。（いろいろつらかったので）
A問題
半径Rの円周を求めよ。
まあ素直に2*PI()*Rを出しましょう。（問題的には円周率を3.14にしておけば通ります。）
ちなみにC#ではMath.PIで円周率が使えます。
出力だけなので今回は構成例は省きます。
B問題
夏休みはN日間で、このうちM個の課題があります。
それぞれAi日かかります。ただし、一つの課題を一回始めると終わるまで別の課題には行けません。
課題をしない日数を答えなさい。宿題が終わらないなら-1を出力せよ
まあ要するに、全部足してみてNより小さければその余った日数でそれ以外は-1で出せばよいです。
今回はだめだと分かった時点で出力してそれ以外はおっけーってことで実装しました。そうすることで無駄な計算は一応減らせるってことになります。
あとは例外処理的に処理できるので通常処理と例外処理の違いが分かりやすくなると思います。（returnでどこで終われるか判定できるため。アプリづくりではエラーを出す場所を把握できるので間違いがすぐ見つけられます）
（構成例）
for(int i = 0;i < n;i++)
sum += a[i];
if(sum < n) //例外処理
Console.WriteLine("-1");
return;
Console.WriteLine(n - sum);
C問題
N人いて、社員番号は1からNまで振られています。
社員番号1以外の人は自身の番号より小さい番号の上司が1人います。
それぞれの人が何人部下を抱えているか求めなさい。
これもかなり単純で、それぞれの上司を割り振って入れて、最後に普通に出力するだけです。
ただし、配列は0から始まることだけ注意してください。つまり、1引きます。
（構成例）
入力はa[i]でいれておく
int[] ans = new int[n]; //答えは配列で入れる
for(int i = 0;i < n -1;i++)
ans[a[i] - 1]++;
for(int i = 0;i < n;i++)
Conosole.WriteLine(ans[i]);
D問題
10の100乗から10の100乗+NまでのN+1個の数があります。
この中のK個以上の数を選んでそれぞれの和を求めたときありうる数の組み合わせを求めなさい。
まずは問題考察です。
仮にK個選んだ時を考えましょう。
K個選んだ時の最小値は小さい順に選んだ時です。よって、
K×(10の100乗)+0+1+....+(K-1)です。
一方、最大値は大きい順に選んだ時です。よって、
K×(10の100乗)+N+N -1+....+(N - K + 1)です。
そして、この間の数はすべてできます。（なぜなら、1ずつ増える数をとることが可能なため）
よって、このときの数は（N +(N-1)+....+(N-K+1)) - (0+1+2+...+(K-1)) + 1です。
あとはKとK+1個選んだ時ですが、前に10の100乗の差があるので絶対違う和になります。
よって、上記の数をそれぞれのケースで足せばよいのです。
とはいえ、普通に計算して求めていくとTLEになっちゃうので、ここで工夫します。
いろいろやり方はあると思いますが、
メモ化で数値を記憶して取り出すのがよいと思います。
基本的に知っておくべきなのは、0からPまでの和です。これをsum[P]とします。
そしてK個選んだときは、
(sum[K] - sum[N-K] - sum[K - 1])+1です。
このsumをあらかじめ求めておけば、出すだけなのでo{1}で計算できます。
つまり、それぞれのKで考えても求めることができます。
詳しくはコードを見てください。
最後に....
まあこれぐらいは解きたいところです。最近、伸びが少ないので茶色、緑色のDiffを素早く解けるように埋めているところです。
競技プログラミングを解くだけだと実務と関係ないかもと思われがちですが、実務をやっている身としては競技プログラミングに必要な知識は実務で使います。
ちょっと数学的な要素があるので何とも言えないですが、実装するなら緑は最低ほしいと感じるところです。プログラミングで稼ぎたいならこれぐらいはないと厳しいと思うのですが....
まあ黙って精進していこうかなと思います。
ではでは。