diverta 2019 Programming Contest 2

開始1時間くらい前に様子が変なので測ったら36.7。なんか「黄色になるなら今回」みたいな気持ちが今回に限って強く、今日はずっと落ち着かなかった。生活の中で色々判断ミスをしていた気がする。そのせいでA問題から全く頭が回ってなかった。C問題を解き始めて少ししたら楽になってきた(汗をかいて体温が下がった)。終了後37.1。たけえなおい。爆死して悲しいというよりは、ともかく普通の生活に戻れてホッとしたという感じ。頭が回ってなかったのは最初の30分くらいだけなのでそれはよかったが、残りのほとんどの時間をCの実装に費やしてしまったのが面白くない。これはどうしようもないのかなあ。

A - Ball Distribution

かなり難しい。全員に配れるだけのボールはあるので、まず全員に配って残りを一人に渡してその渡した人と1個だけの人の差が答え。だと思ったらサンプルが通らない。1人しかいないこともあるのか。今の自分には難しすぎる。

B - Picking Up

めちゃくちゃ難しい。まず問題の趣旨を理解するのに5分くらいかかった。p,qは最初に決めて固定なのね。「p≠0 または q≠0」という条件は最後まで意図がわからず悩んだ(両方0にしてもメリットないんだから答え変わんないよね)(結局無視して解いた)。しばらく紙の上で考えて、移動ベクトルはO(N^2)通りしかないことに気づいた。つまりp,qを全部試せる。180度違うやつが面倒だが、absでいいかと思って実装を始めて、少ししてabsは向きが変わっちゃうからダメと気づいて、pが正になるように(pが0ならqが正になるように)正規化した。思いついたときは全体でO(N^3)かと思っていたが、順番がわからないのでO(N^4)だ。なんかよくわからないので待っても仕方ないってことで提出したがWA。なんも考えてなかったけど全部の辺を検索したらまずかったんじゃ?しかしよく考えると三角形みたいにつながることはない(同じ向きだから)のでこれでよさそうだ。正しそう。正しそうなコードのデバッグが最も難しい。原因はabsの消し忘れだった。同じこと2回書いたからね。まあ頭が回ってなくても解けてるのはよい(さすがにコーディングはきつかったけど)。(tokuminiさんの提出を見て)map使うの頭良すぎか!逆向きのやつも両方mapに入れてしまえばいい。ミスしにくいコードがすごい。

C - Successive Subtraction

3-(1-2)とかカッコを使って紙の上で考える。1つを除き望みの符号にできそうだと気づく。1小さい問題でできていればできるからできるな。引き算なので全部同じ符号にするのは無理。解けた。しかし、実装に5億年かかった。最後のほうになって「なんだ簡単かよ今更すぎる」というのもありがちだが、そういうこともなかった。3通りに場合分けすれば解けるのはわかっているが、それぞれが重い3つを一つもバグらせずに書くのは無理だ。といってまとめる方法も全くわからない。いうて少しは簡単なの思いついて、正の数が2個以上と1個以下に分けた。N=2のケースを常に気に掛ける必要があってしんどかった。出力が独特なのもきつい(意識をそっちに持っていかれる)。0と負の数は扱いが楽で、引いていくだけでいい。正の数が、1個だけならそこから他の数を引いていくだけでいいのだが、2個以上だと面倒になる(だからあの場合分けを思いついた)。これを一発ACした俺の実装力は神懸かってると思った。最初に戻って、符号を決めてやってそれを実現する手順を求めるという方向性はなかったかな。

これを1000人以上が解いてるのは意味がわからない。短時間で解いてるのは魔法かなんかか?ともかく、早々に「解けた」と思ってしまって実装ではまるのは自分にありがちなパターンだ。他の問題に行ければそれもいいが、今回のようなセットだと無理。じゃあ無理か。こういうのは、いい方法を時間をかけて考えたいので、時間に制約がある状況だと単純につまらないんだよね。

D - Squirrel Merchant

22分くらいしかなかったので、いつもとは違う解き方。解法をどんどん決め打ちしていった。1回だけ訪れるBを2回に分解する。Aで金属に換えてBでドングリにする、Bで金属に換えてAでドングリにする。交換の仕方は、有利なものから貪欲に。ドングリは整数個ずつしか使えないので、1種類の金属で済むわけではない。とりあえず提出したがWA。不利な交換はしなくていいのではと気づく。なんにもわかってなくて考えてるのでなんにもわかってない。提出するがこれもWA。そういえば、交換レートが同じでも交換する個数は違っててドングリを捌ききるには順番が大事になることがありそうだと気づく。さすがに2分では無理。今思うと、6通りしかないし全通り試せばよかったか。そして、順番を決めても貪欲に取っていいわけではなさそう。さすがに短時間では無理だった。(解説放送を見て)全部ドングリにするという本質っぽいものを乗り越えたあとに待っているのがDPwwこれは無理ですわw