おはようございます。しほみんです。
2週間前なのですが、パナソニックプログラミングコンテストを復習しようと思います。この回は罠が多く、ちゃんと気を使って問題を解くのも大事だなと思ったセットです。（最近暗い話ばっかなので...）
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは750程度になりました。緑まであと一歩です。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。パフォーマンスを安定的に1000以上とる。
今回は20分でABCの3完でした。ただし、細かいことに気を使えず、4回WAを繰り出したので、結構時間としては悪いです。D問題は気が付いてみれば使えるので、今回で学習しました。ただ、みんな罠に引っかかって余計に時間がかかる人が多く、パフォーマンスも1007で、レートも729→757とあがっています。
今回、パフォーマンス1000超えたのは正直意外でした。というのもちょっとした罠しかなく、プログラムとしてはかなり標準的な気がしたからです。やっぱ緑はそこまでレベルが高くないのかもしれないなとは感じています。
今回はD問題まで復習して終わります。
以下、問題です。
A問題
ある数列が与えられます。その数列のk番目を出力してください。
おとなしく数列を代入し排出すればいいです。
一般的な列の読み方はC#では、
int a = {1,1,....};で読み込めます。
ただし、最初は0番目であることに注意します。1引いてあげます。
（構成例）
int a = {1,1,....};
Console.WriteLine(a[k -1]);
B問題
ビショップは斜めに好きなように動けます。左上からスタートした場合、動けるマスの数を求めます。
マス数はW×Hなので、WかHが偶数だと、ちょうど半分。両方奇数だと半分+1となります。
ただし、これ一つだけ罠があって、WかHが1のときビショップは動けません。なので、このときは例外処理をします。
例外処理の場合、if文で書くとよいです。最後にreturnで返せば、そこで終わるので、便利です。
（構成例）
if(W == 1 || H == 1)
Console.WriteLine("1");
return;
if(W % 2 == 1 && H % 2 == 1)
Console.WriteLine(W * H/2 + 1);
else
Console.WriteLine(W * H /2);
C問題
√a + √b <√c を満たすか示せ。
まあ素直に書けばいいと思うでしょう。ルートはsqrtで取れます。
ただ、これを書くとWAになってしまいます。
なぜならdouble型だと桁の精度が足りず、一部で満たさなくても満たすような答えを得てしまいます。
解決方法は2通りあります。
1. long double型を用いる
2. 式変形で求める。
1のほうが単純です。doubleの倍のけた精度があるのでそれが良いです。
2は少し複雑ですが、すべて整数型で処理できるのでこういう桁の問題はないです。
式変形ですが、左辺も右辺も両方正なので二乗をとってその差を見ても問題ないです。
つまり、この条件下で
√c - (√a + √b)が正であることは、(√c )^2 - (√a + √b )^2 が正であることは同値です。
なので後者が正であれば、条件を満たします。
さらに式変形すると
(c - a -b) - 2√ab になります。
でまた、c - a - b >0、√ab > 0であれば、(c - a - b)^2 - 4ab が正も同値です。
これで整数型しかないので、計算が容易に可能です。
c- a - b< 0のときは、(c - a -b) - 2√abが常に負になるので満たしません。これを省きます。
そうすると、あとは(c - a - b)^2 - 4ab が正かどうかで判定します。
詳しくはコードを見てください。
計算科学の弱点である精度問題の裏を突いたこういう問題は面白いと思います。解決するには自分の頭で整数型に持っていけるとか、もっと精度良くするとかいろいろあって面白いです。
D問題
長さNの標準形を並べてください。
標準形とは、文字列の同型の中で辞書順で一番頭の形です。
同型とは同じ並びを意味します。文字は関係なくです。
例えば、ababcとxyxyzは同型です。
（1, 3文字目に第一の文字、2,4文字目に第二の文字、5文字目に第三の文字という共通項がある）
まあぱっと見問題何言っているかわからないのですが、要するに、
辞書順で、文字の並びと組み合わせを考えて並べろってことです
こういうときは深さ優先検索が有効です。
深さ優先検索をすることで基本的に辞書順に並べることができます。
イメージは以下の図です。
詳しくはアルゴリズムを見てほしいのですが、再帰法で、頭から素直に読んでいく方法です。n文字の列なら、
1番目の文字列
1文字目はとりあえずaを読む。
2文字目はaを読む。
・・・n文字目もaと読む。
→これを出力する
次はn文字目だけbを読むので、って繰り返します。
つまり、
for文の中にfor文をどんどんマトリョーシカのように入れていくことででるので再帰です。
あとは、上の条件下を満たすような再帰を考えます。
とはいえ単純には難しいので、具体的に書いて考えてみようと思います。
1,2,3文字の時を書きます。
ここでわかることは
1. 標準形はaから始まる（bから始めたら必ず負ける）
2. 1つ下の文字はその文字の一つ下までを読みこめばいい。
となります。あとはそれを実装するだけです。
詳しくはコードを見てほしいのですが、メインであるのはfor文として一つ下の分がどこまでやるのかまでを関数で引き継いで考えます。
つまり、bfs(文字列,for文のなかでその一つ下の階層はどこまで繰り返すか,全文字数）で並びます。
最後に....
D問題って結構難しいと感じます。ただ、再帰の考え方を理解して、何をやっているか考えれば、おのずとわかるので、丁寧に処理を追いかけてみるとよいと思います。自分も追いかけまくってはいます....
ではでは。
