おはようございます。しほみんです。
ABC161に参加したのでその復習をします。D問題解けなかったのですが、解説を見てスゲーと思ってしまいました。もっと勉強が必要ですねえ....。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。パフォーマンスを安定的に1000以上とる。
今回は30分でABCの4完でした。D問題普通に解けませんでした。動的計画で考えたのですが、どう考えても数を出すのはうまくいかなさそう....ということで躓きました。仮説を見たらもう納得したのでまた勉強していきます。パフォーマンスは703でまあC問題がちゃんと解ける感じのレートです。レーディングも808→798となってまた茶コーダーに戻ってしまいました。
D問題は普通に勉強になったのでそこまで話そうかなと思います。やっぱまずはどのD問題も解けるようにすることから始めていくべきなんだなあと感じています。
E,F問題よりまずは基本的なアルゴリズムを問題に適切に使う練習をしていきます。
ここから問題です。
A問題
箱A, B, Cが入っています。それぞれX, Y, Zが入っています。
箱AとBを入れ替える。
そのあと、箱AとCを入れ替える。
それぞれの箱に入っている数を出力してください。
冷静に数を追っていきましょう。
AとBを入れ替えれば、箱A, B, Cは順にY, X, Zとなります。
その後、AとCを入れ替えれば、順にZ, X, Y です。
よって、Z, X, Yを出力します。
（構成例）
Console.WriteLine(Z + " " + X + " "+ Y);
B問題
N種類の製品があります。それぞれAiの得票数があります。
人気商品をM個選びます。Aiが総得票数の1/4Mの投票未満の商品は選べません。
M個選べるかどうか判定してください。
まずは総得票数を出します。（sumとする）
あとはそれぞれの商品に対して、sum/ 4M未満かどうかを判定します。
満たす数がM個以上であればYes,それ以外はNoです。
念のためdouble型で判定するといい気がします。
（構成例）
for(int i = 0;i < n;i++)
sum += a[i];
for(int i = 0;i < n;i++)
if(a[i] >= (double)sum/4.0/(double)m)
count++;
if(count >= m)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
C問題
任意のxについて以下の操作をします。
操作：xを|x-k|で置き換える。
この操作は0回以上できます。このとき出される最小の数を求めなさい。
うーんまあざっとみ考えにくいですが,
x > kのとき
x = x - kで出てきます。
ということは x > kのときが続く限り、xは数がどんどん減り続けることを意味します。そしてそれはx - k * nだけ減っていきます。
つまり、まずはx < kのときの状況を持っていくのがこの操作です。
x < kのとき
x = k -x で出てきます。
これをもう一度繰り返すと
x = (k-x)-k| = x で元に戻ります。
つまり、このケースだとxかk-xかどちらかの場合しかないです。
で、x > kのときは x<kになるまで、kずつ引いていくことを意味します。
ということはx < kになるとき、xはxをkで割ったあまりになります。
つまり、この問題は、xをkで割ったあまりをamariとすれば、
amariとk -amariのどっちが小さいか出せばよいことになります。
パッと見何言ってるかわかりにくいですが冷静に突き詰めるとわかるのであきらめずじっくり考えてみましょう。
（構成例）
n %= k; //n自体をnをkで割ったあまりにする
Console.WriteLine(Math.Min(k -n, n));
D問題
ルンルン数のk番目を求めてください。
ルンルン数とは
i-1桁目とi桁目の絶対値の差が1以下である。
まあルンルン数自体はいくつか出すことができます。ただ、どうやって出せばそのk番目が出るかとっつきにくいです（というかわからなかった）。
ただ、ルンルン数には特徴があります。
例えば、n桁までの数のうちのルンルン数なら、n+1桁のルンルン数は一番下の桁の数を見て、その-1,0,1を足した数を出せばよいのです。
例えば、21はルンルン数ですが、この派生から考える3桁のルンルン数は210,211,212が
あります。
そして、このルンルン数は小さい順に考えたとき、その取り出した数から派生するルンルン数は必ず、大きくなって後ろに並びます。つまり、小さい順に並べることが可能です。
例えば、1,2,3はルンルン数ですが、
それぞれ10, 11, 12と21, 22, 23と 32, 33, 34と出てきて、順番に並びます。
ここからキューというデータ構造を使えばよいことが分かります。
キューとは....
数を一方的に入れることができる。ただし取り出すときは、最初に入れた数が出てくる。
ということで、以上を考えると
1. 1-9をキューに入れる。（1の派生から10が出るため、その整合性をとる）
2. キューを取り出す。
3. 取り出した数の一番下の数を考える。
0のときは10倍し、エンキュー、10倍+1をエンキュー
1-8のときは10倍+（下一桁-1）をエンキュー、10倍+（下一桁）をエンキュー、10倍+（下一桁+1）をエンキュー
9のときは10倍+8をエンキュー、10倍+9をエンキュー
これをずっと繰り返していく。
k番目に取り出した数はそのまま、答えとなります。
まキューの使い方って今までいまいち理解できませんでしたが、これで李買いが進みました。取り出した数をもとに次のスタンバイする数を考えていくみたいな発送ですね
便利なので、キューについては是非覚えておきましょう。
C#でキューを使うにはusing System.Collections.Generic;が必要です。
詳しくはコードを見てください。
最後に....
今回のD問題はかなり勉強になりました。実践でも使えそうなので是非覚えておきたいです。データ構造は実用性のイメージがわきにくく考えにくいので、ぜひ問題を通じて勉強したいです。
ではでは。
