5完3WA。しょうもないミスを連発・・・。
各問題
A - Heavy Rotation
1日おきに白と黒が入れ替わるので、Nが奇数のとき黒い服、偶数のとき白い服を着ます。
B - Trapezoid Sum
「AからBまでの和」は、「1からBまでの和」引く「1から(A-1)」までの和なので、N回それをして足します。
1からnまでの和は言うまでもなくn * (n + 1) / 2
で求められます。
C - Collinearity
3点をa, b, cとして、それらが同一線上にあるかどうかは、a, bを通る直線の傾きと、b, cを通る直線の傾きが一致するかどうかを確認すればよいです。数弱の私にもそれくらいわかるぜ!!!
そして、Nがたかだか100なので全探索すればよいです。0除算には気をつけましょう。というか除算が出ないように式変形すればよいです。
D - Hachi
Sがひと桁のとき、"8"だけが8の倍数です。
二桁のとき、Sとそれをひっくり返したものが8で割れるか実際に試せばよいです。
あとは三桁以上のときです。大事なこととして、下三桁が8の倍数ならその数字は8の倍数であるという性質を利用します。
まず"8"が3つ以上あれば下三桁を"888"にできるのでYesです。他の3つ並びは8の倍数ではありません。 (444を8の倍数と誤認して1WA・・・)
任意の数字が2つ以上ある場合、他の数字との組み合わせを試します。たかだか3*9通り試せば終わります。もちろん存在しない数字を試してはいけません。
それでも見つからなかったとき、全てバラバラのケースおおよそ1000通り(よりは少ない)を試しましょう。もちろんここでも存在しない数字を試してはいけません。(試してしまい1WA)
ここまで探して見つからなければ、もう8の倍数は作りえないのでNoです。
もうちょっと簡略化できるのかも?
E - Transformable Teacher
Hはソートして、となり同士をペアとするとしてよいです。一人以上飛ばしてペアにしても得しないです。
で、飛ばしても得しないということは、偶数番目の児童を先生と組ませても得しないです。偶数番目の生徒を抜くと、児童同士のペアで一人飛ばしのペアが発生してしまうからです。(多分)
というわけで、奇数番目の児童それぞれについて最適な先生を二分探索などで探して身長差を出し、残りの児童のペアの身長差の和に加えればよいです。ここで、(1,2), (3,4)...(n-2,n-1)のペアの身長差と(2,3), (3,4)...(n-1,n)のペアの身長差を累積和などであらかじめ持っておくと、児童同士のペアの身長差の和は各回O(1)で取り出すことができるので、計算が間に合います。
一箇所NとMを間違えて1WA・・・。
F - Silver Woods
全然わかりませんでした。
まとめ
444を8の倍数と誤認するとか、NとMを間違えてWA出すとか、せっかく5完で稼げる回だったのにもったいないことをしてしまいました。
まあ水パフォなのでよしとしましょう。