ABC181

結果的に5完早解き勝負となったが、相性はやや悪かったけど自分のスピードを出せた。Fで難しいほうへ行ってしまい気づいたときには手遅れだったのが心残り。

A - Heavy Rotation

Yes/Noじゃないから実装時間がかかってしまう。内容自体は簡単で、N%2を使う。

B - Trapezoid Sum

平均(A+B)/2のものをB-A+1個足すと考えればいい(当然整数になるが一応確認する)。

C - Collinearity

全探索。直線上にあるかの判定は、外積を使う(90度回転させて使い慣れた内積を使うことも考えたがまあ同じ式になる)。

D - Hachi

好きに並べ替えることができるので、1から9までの各数が何個あるかという情報だけを使う。8の倍数かどうかは、下3桁が8の倍数かでわかる。よって、125個ある1000未満の8の倍数それぞれについて作れるか判定すればよい(こっちも個数カウントして比較、1個でも足りなければ作れない)。が、サンプル3が合わない。3桁未満のケースのことをわかってなかった。ちょっと悩んだけど1桁なら並べ替えの余地はなく、2桁ならswapするかしないかだけ。3桁以上の場合ももう一度確認。ここまで調子よく解けていただけに、この実装はきつかった。

E - Transformable Teacher

ソートして隣同士で組むのが最善に見えるが、けっこう簡単に証明できた(間に誰かいたらその人が誰と組んでいてもその4人で組み直すことで改善される)。すると、先生がどこに入ってもその左側と右側は同じ形になる。右側からを累積和として計算しておけば、あとは左側から見ていくだけ。しかし実装がしゃくとりになりそうで大変そう。頑張っていつも通り書いたら意外ときれいに書けた。2個ずつずらしていって、常に1人だけ余るので先生と組む(どっちの身長が高いかはわからないのでabsとる)。念のため児童(なんか園児だと思ってた)が1人しかいないケースを手で作って確認してから提出。

ここまで、DEの実装は重かったものの、特に詰まることなく解き進めてきた。

F - Silver Woods

なんか三角形を描いてその領域に入れるかどうかでグラフを作って連結判定みたいなのが浮かぶ。円を動かすとき、x座標が減る方向へ動く必要があるケースも構成できたので、かなり難しそう。21:55に「ボロノイ図」でググり、三角形じゃないなー違うなーとか言ってて「ドロネー図」に辿り着いたのが22:11。双対だよ。まともな厚みの知識を持っていない。いやこれをABCの時間内に実装するのは無理でしょとなったが、楽する方法も思いつかない。ただ時間が過ぎて、残り15分くらいになって順位表を見てかなり解かれているので楽な方法があるんじゃないかと考えて、通れない2点の間を線分でつなげて壁にしてしまっても結果に影響しないのではと思いつく(今考えると、直線的な壁にしたらそのせいで通れなくなることがありえる)。半径決め打ちで二分探索とか、通路の壁に垂線下ろした場所にも釘を置くとかは、ドロネー図のころから考えてあった。通路の上と下が連結になったら通れないのは確定。残り時間が少ないので、実装できるかどうかのスリルを味わうこともできなかった。