某Coder に初めて参加して見る

昼まで寝てて,そのあとぼちぼち起きて研究室の机の片付けなどをする.家の冷蔵庫を引き取ってもらうのに,リサイクル業者に電話するも「今日は休みなので明日にしてくれ」と言われるので明日掛け直す.

んで,夜は某Coder のコンテストに初めて参加してみた.Beginner と Regular があるんだけど,まあまずは手始めにと言うことで Beginer から.100 分で 4 問という問題セットらしい.

A問題

なぜか問題文を理解するのにちょっと時間がかかったけど,わかったら瞬殺.

B問題

これも瞬殺,といきたかったところだけれども,原因不明のエラーに苦しむ.んで,printf デバックしてみたら,入力と変数宣言の順番をビミョーに間違えていることに気づく.ぐぬぬ.ちょっと時間がかかってしまったけど,まあ,問題ない.

C問題

問題文通りに,i = 1, ... , N をそれぞれ for 文で計算していると TLE を食らう (実際まず自分も食らった).そこで,ちょっと頭を使う必要があると判断.まず当初の計画通り旅行したときにかかる移動時間を求めてから,それから i 番目のスポットを訪れるのにかかる時間を引くという方針で.すると,

  • A -> B -> C と訪れるときにかかる時間は,|AB| + |BC|
  • A -> C と訪れるときにかかる時間は |AC|

なわけだから,A -> B -> C と訪れる予定だったのに急遽 B を訪れない,つまり A -> C と移動するように変更するんだったら,当初の予定から |AB| + |BC| を引いて |AC| を足したぶんの時間がかかるよね,というだけの話.これを使えば, 1 重 for 文を 2 回回せば済む.

D問題

最初,なんだこれむずくね,と思ったが,冷静に考えると,盤面は 100 x 100 までいいんだから,これをフルに使えば簡単だなということがわかる.要するに,まず最初左半分を白,右半分を黒に塗って,あとは必要なだけ

.#....#.####
##......####
.#....#.####
##......####
.#....#.####
##......####
......#.####
........####
......######

のような感じで無理やり各色の独立成分を作っていけば良い.これがわかってしまえばあとはやるだけ.ただし,(A, B) = (1, 1) の場合とか B = 1 の場合とかはちょっと注意が必要だった.

ということで,全完できました.時間は10分ぐらい残し.ただし,しょうもないミスで 5 回 WA を食らったのがかなC.次から Regular コンテストでいっかな,とか思ったが,まあ完璧というわけではなくミスも多かったことだし,もう一回ぐらい Beginer やってみましょうかね.適正レートとかもよくわからんので,まあしばらくはお試し気分で.