おはようございます。しほみんです。
最近、競技プログラミングも徐々に参加してきたのでまた再開します。珍しくちゃんと解けました。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCDE、90分2WAでした。A問題で主力の綴りミス、D問題のelse ifをifで間違えて書いてWAはもったいなかったです。今回はEまで解けたので良かったです。Fは何となく手掛かりはつかめたけどコードでどう起こすかはわからなかったです。パフォーマンスは1295で、レートは977→1013で1000をまた戻ってきました。
今回はA,B,C,D,E問題を解説します。
ここから問題です。問題は簡潔に書いています。
問題A
高橋君は、白い服を今日着ています。
白、黒、白、黒と着ていきます。
N日後にきている服の色を求めなさい。
まあ、奇数日後は黒、偶数日後は白なので、if文で2で割り切れているかどうかを見ればよいです。
問題B
以下の動作をN回繰り返します。
AiからBiの数字1つずつを黒板に書く。
この時、N回後の黒板に書かれた文字の総和はいくつでしょうか
まあ普通に、AiからBiを足してしまうと、最悪o(Nの2乗)になるので少し工夫します。
AiからBiまでの和は（Ai+Bi）*(Bi-Ai+1)/2なので、それを求めて足します。これでo(N)で求められます。
問題C
点がN個与えられます。
この点の中で3点選んだ時、直線になるものがありますか？
3点が直線になる条件は、
A,B,Cの点があるとき、
(ABの長さ）＋(BCの長さ）＝（ACの長さ）
(BCの長さ）＋(CAの長さ）＝（BAの長さ）
(BAの長さ）＋(ACの長さ）＝（BCの長さ）
なので、これを求めるだけです。
N=100までなので、o(Nの3乗)で全探索しても十分に間に合います。
ただし、sqrtをつかうので、小数型になります。double型だと丸め込み誤差があるので、等号だけをとるとWAになるような気がします。よって、誤差許容を10の-8乗までにして出します。
誤差はちゃんと見積もらないとWAになることはありますが、まあこれぐらいでよいのかなって思います。
問題D
'1'から'9'までの文字で構成されている文字列Sがあります。
このSを適当に並び替えた場合、8の倍数で割り切れる数がありますか？
すべての並び替えとか考えても、sが200000文字あるので、そもそもulong型も適応できず考えられません。
ここでは全検討とかせずに、8の倍数の条件を考えてみましょう。
1000は8で割り切れます。つまり、下4桁より大きい数はそもそも8の倍数に影響しません。よって、下3桁が8の倍数かどうかが大事です。
よって、下三桁の候補は104,112,....,992の108個（多分）が作れるかどうかなのでそれを検討していきます。下二桁では096とか必ず0が付くので今回は省けます。
あと、この方法だと100以下は検討できないので、例外条件として処理します。
具体的には、
2. 文字列が1つか2つの場合、例外処理する。（1つの場合8かどうか、2つの場合は、その数か、反転するかどうかを見比べます）
1,まず文字列を全部調べて、1-9の数がいくつあるか調べる。
2.112から992までそれぞれ、必要な文字数を出して、それを満たすか見る。一つでも満たせばYesを出して終わり。
3.全部条件を満たさなかった場合、Noを出す。
E問題
N人の生徒がいます(Nは奇数)。また、あなたは先生です。
先生はM種類の身長を持ちます。
このとき、生徒と先生でペアを組みます。このペアの身長差は最小にしたいです。
この時の最小値を求めなさい。
身長差を最小にするのは、身長小さい順にペアを組んでいけばよいです。
ただし、ここで厄介なのは、先生の身長がM種類あることです。
ということで、M種類検討して、身長差を求めていると、o(MN)で時間オーバーです。
なので別戦略を考えます。
まあ、まず、M種類の身長がどこにあるかは、二分探索をすれば、o(MlogN)で求められます。
となると、身長を求めた後の計算時間をどう削減するかです。
o(1)で求めないとならないので、それをするには累積和の手法があります。
あらかじめ、生徒の身長さをそれぞれ求めておきます。
このとき、身長差が奇数番目と偶数番目で累積和を取ります。
先生の身長の位置より小さい先生は、身長差が奇数番目のところをとり、それより高い生徒は身長差が偶数番目のところを求めればよいです。
まあいろいろバグりそうですが、バグらない工夫としては、
1.二分探索のインデックスをmin=-1とmax=Nとると、-1からN-1でとるので、N箇所が確実にわかる。
2. 累積和は初項をゼロにして一つも選んでいなかった場合のケースを入れる。
3.先生と生徒の身長差は、先生の偶奇の位置で求める。
って感じです。
最後に....
まあ簡単に考え方とバグらないコツを載せました。
コードも併せて乗っけておくので参考にしてください。
ここまで、流れとバグらない点を留意しておけば、間違いは減るなあと思いました。
ではでは。
