おはようございます。しほみんです。
競技プログラミングの話すっかり忘れていたので、更新します。この回は完全に戦略をミスって大失敗しました。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約35回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はABの2完でした。順位は5000位にも入れず、パフォも233と灰色、レートも695→652と大幅ダウンです。
原因はいくつかあって
・まずC問題の形式になれてなかった。あとC#特有の問題もあったので解けず。
・D問題が実装でとても厄介だった
・E問題は思ったより簡単だったが、D問題に固執して切り替えられなかった。
まあ、今回はABCEかABEで解答できたら相当いい順位でした。まあ、こんなこともあるんだなあと思うと、やっぱE問題もある程度対応できないとつらいなと感じました。
今日はE問題まで復習して終わりにしようと思います。D問題は解法が分かってもコード実装がつらいのでコードは載せません。
ではここから振り返ります。
A問題
3つの数が与えられます。2つの数が同じで、もう一つが異なる場合はかわいそうとします。かわいそうのときはYes、それ以外はNoで解答します。
A B Cの3つあるので3つのケースを考えます。
・A=B かつA≠C
・A=C かつA≠B
・B=C かつA≠C
これをif文で記述すればよいです
構成例
if(A == B && A !=C)
Console.WriteLine("Yes");
else if(A == C && A !=B)
Console.WriteLine("Yes");
else if(B == C && A !=C)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
B問題
文字列の並ぶ書類が与えられました。
書類に書かれている整数のうち、偶数であるものは全て、 または で割り切れる。
承認するか拒否するか選んでください。
素直にこの条件を書いていけばよいです。ただ、拒否の場合を考えた方が楽なので、偶数のとき3でも5でも割り切れない数があった否定して全通過したらよいです。
構成例
for(int i = 0;i < n;i++)
if(a[i] % 2 == 0)
if(a[i] % 3 != 0 && a[i] % 5 != 0)
Console.WriteLine("DENIED");
Console.WriteLine("APRROVED");
C問題
選挙ですかね。N枚の紙があります。この中で一番投票されたものをアルファベット順に並べてください。
まあDictionary型を使ってKeyとValueの関係で作っていきます。
1.基本的にKey検索して、Keyとしてなければ、追加してValueを1にする。
2.Keyがすでにあれば、Valueを足します。
3.Valueの最大値を取得して、Valueの最大値のKeyを取得します。
4.そのKeyたちで並び替えします。
5. その通り出力します。
ただし、C#では4が注意です。
keyをソートする際に、()内に、StringComparer.OrdinalIgnoreCaseを入れます。
これを入れないとソートの時間がかかりすぎてTLEを食らいます。
競プロやるなら知っておかないとなりません。
具体的な方法はコードを見てください。trycatch文でkeyとValueを取得してます。
D問題
数列A1,A2,....,Anがあります。すべての組み合わせはn(n-1)/2通りです。k番目の文字は何でしょう。
数列は負の数と0があるので、とても厄介です。
まず、負の数と0と正の数を数えて、それぞれ何番目まで、負、0、正か分けます。
そのあとはそれぞれの条件で場合分けをして考えます。
このとき二分探索を使って解きます。考えるのはk個以下の数は何個あるかを見極めて判断します。そして尺取り法を使うと計算が楽になります。
D問題にしては非常に実装が厄介な問題だと思います。これは時間内に説くのは今の自分では厳しかったです。むしろE問題の方が簡単だったので、それをやります。
自分もここは実装できてません。
E問題
Nは10の1000000乗以下の数です。
紙幣が1,10,100,1000,...,10の1000000乗であります。
渡した紙幣と受け取った紙幣の合計枚数の最小を求めます。
例えば、9をやり取りするとき、おつりなしで9枚出すより、10をだして、1返ってきた時の方が枚数が少ないので、その時の枚数を解答します。それは2枚です。
時間制限上、o(1000000)しか使えません。よって、桁ごとに処理しないとならないので、桁DPを使います。
DPを2つ立てると解けます。
1つ目のDPはi桁目を一桁あげた場合に最小の枚数を出す
2つ目のDPはi桁目をあげなかった場合の最小の枚数を出す。
つまり、前者はお釣りを想定したケース、後者はお釣りを想定しないケースです。
あとはこれをDPするだけなのですが、
それぞれの遷移前は、一桁あげるかどうかしかないです。
よって、一桁あげたときをdp_u、上げないときをdp、i桁目の数をtempとすると
dp[i] = Min(dp[i] + temp, dp_i[i]+temp);
dp_u[i] = Min(dp[i] + 11 -temp,dp[i] + 9 - temp);
で求められます。
あとはさいごの数でどっちが小さいかで判定します。
詳しくはコードを見てください。
最後に...
この回は絶望的にできませんでしたが、いい復習になりました。今後できるようにするには復習しかないので頑張っていこうと思います。ではでは。