おはようございます。しほみんです。
今日は先週行われたABC158の話をします。E問題がうまく実装できないまま日が経ってしまいそうなので一度復習します。標準的な難易度と感じました。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは750程度になりました。緑まであと一歩です。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約40回参加、10か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。パフォーマンスを安定的に1000以上とる。
今回は40分でABCDの4完でした。BとDで勘違いしたので4WAを出しています。4WA出さなければそんなに悪くないと思いました。でも、パフォーマンスも827でなんとか踏ん張り切れました。レートは785→789で微増です。
今回で緑になれるかと思ったらなれませんでした。というかなれると思って緊張した成果余計に焦ってミスったのが痛いです。
今日はD問題まで復習して終わりにします。E問題は冒頭にあるように発想はあったものの実装できなので、発想だけ話します。
ここから問題です。
A問題
N個のボールは偶数、M個のボールは奇数です。
2つのボールを取り出した場合、偶数であるのは何通りですか？
偶数は偶数を2個とるか、奇数を2個とるかしかないです。
よって、nC2+mC2です。
（構成例）
Console.WriteLine(m*(m-1)/2 +n*(n-1)/2);
B問題
強い回文かどうか判定してください。
強い回文の条件
・Sは回文である。
・Sの1文字目から(n-1)/2文字目までは回文である
・Sの(n+3)/2文字目からn文字目までは回文である
素直に上の条件を実装すればよいです。実は2つ目と3つ目の条件はどちらかを比べればよいです。1つ目の条件で2と3番目は対象であるからです。
1つ目の条件は、
1文字目とn文字目、2文字目とn-1文字目、...をみてどこか違えばNoを出力します。
2つ目の条件は
1文字目と(n-1)/2文字目、2文字目と(n-3)/2文字目、...をみてどこか違えばNoを出力します。
文字の数え方は0番目から始まることだけに注意しましょう。
（構成例）
for(int i = 0;i < n;i++)
{
if(s[i] != s[n-1-i])
Console.WriteLine("No");
return;
if(s[i] != s[(n-1)/2 -1 - i])
Console.WriteLine("No");
return;
}
Console.WriteLine("Yes");
C問題
三辺の和がlです。この時の体積の最大値を求めなさい。
感を働かせると、3辺とも同じつまり、l/3のときが最大です。
よって答えは（lの3乗）/27です。
こういう問題は証明とかとにかくおいておいて直感的にコードを書くしかないと思います。なれの問題だと思います。
（相加相乗平均を使えば、証明は容易にできます）
実装は簡単なので割愛します。
D問題
ボールがN個あります。それぞれ頭から番号が書かれています。
この数列からk番目を除いたとき、同じ数が書かれているボールを2つ取り出す方法をk番目の答えとします。
1からn番目までの答えを求めてください。
素直に1個省いて数えていくとTLEします。よって、計算量を減らす工夫をします。
1からn番目までしないとならないのですが、それぞれ高々1個しかボールが変化しないことに注目します。
ということは大体全部同じような答えです。
そこから、まずは1からN個全部あるときすべての通り数を求めておいて、k番目のボールをなくすと何通り減るか考えればよいとわかります。
またn個の玉から2個取り出す方法はA問題と同様にnC2です。
方法としては
1. まず数列を頭から読んで、それぞれ何の数が何個あるか数える。
2. 上の情報をもとにしてすべての通り数を計算する。（sumとする）
3. 1番頭からよんで、その数字を確認。その数字の数をx個とするとsum - (x-1)が答えとなる。
最後の減らす数ですが、x個から2個取り出す行為をx-1個から2個取り出す行為に変更するので、xC2-(x-1)C2からx-1と求められます。
詳しくはコードを参照してください。
ここでミスったのはlong型にしなかったというしょうもないミスです...
E問題
板チョコがあります。いくつかはホワイトチョコレートです。分割したとき、ホワイトチョコレート部分をk個以下にしたいです。
そのために切る最小の回数を求めなさい。
チョコレートの大きさはH×Wです。1<=H<=10,1<=W<=1000です。
ここではHの小ささに注目します。Hが小さいので、それぞれの切れ目を切るか切らないかを試せます。o（2の(H-1)乗）です。
横の切り方が決まったので、あとは縦の切り方を考えるだけです。
ここでは貪欲法を使えば、求まります。
よって、ビット全探索で横の切り方を決めて、貪欲法で縦の切り方を決めます。
ということまでは気が付けましたが、実装が無理でした...なん切り方の記録の仕方が若干おかしい気がしていますがまだまだなんですね...
最後に...
ミスせず確実に理解して早く解くことがD問題までは大事ですね。もうD問題は落としたくはないです。どんどん磨いていきたいと思います。
ではでは。
