週末のコンテストの反省をする
ABC151で500台とかいうパフォーマンスを叩き出して割と心が折れたので精進と備忘録ついでに最近解いた問題のまとめを書きます。
第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes（600点）
解法とか方針とかは解説pdfと動画参照。
使うアルゴリズムについて。有限素体 における調和数的なものを計算する必要がありますので、それはつまりある自然数に対してその逆元を計算しなければならないということです。
逆元の計算については詳しくは上の記事に書かれていますが、Fermatの小定理を使うのが理解するのにも手っ取り早くてよいです。
法が であるとき、自然数
の逆元は
なので、愚直に計算すると計算量が
となってしまいますが、これも上の記事に書かれている二分累乗法によって、対数オーダーに落とすことができます。
Submission #9493452 - Dwango Programming Contest 6th
ABC 151 F - Enclose All（600点）
最小包含円というやつです。典型どころか超有名とのこと（すぬけさん談）。
解説できないので下のサイトからソースをコピペして提出しましょう。
Spaghetti Source - 最小包含球 (move-to-front heuristics)
Submission #9489664 - AtCoder Beginner Contest 151
ABC 151 D - Maze Master（400点）
方針については、BFSだろうと秒で分かると思います。
ゴール地点を定めずにBFSすると、各地点までの最短距離が分かるというやつです。
迷路上の全ての点をそれぞれスタート地点に定めて最も遠い距離を記録、そして最後にそれらのmaxを通ればACです。
ちなみに私は本番中に変数名の i と j を間違えてるのに最後まで気づかず400点を逃しました。辛い。
Submission #9489255 - AtCoder Beginner Contest 151
ABC 151 A - Next Alphabet（100点）
わずか3ByteでACを出せると話題の問題です。完全に余談ですね。
Brainf***を使うと、3文字で書けます。
ソースコードは、「,+.」です。
Submission #9489181 - AtCoder Beginner Contest 151
ABC 150 C - Count Order（300点）
C++限定解法ですが、next_permutation()を使うと書くだけでACできます（Pythonでも順列生成する関数はあるらしい）。
上手いことに辞書順で生成してくれるので、カウンタで何番目かだけ記録してあげれば良いです。
Submission #9391152 - AtCoder Beginner Contest 150
反省
・焦りすぎない。問題をちゃんと読むこと。早解きよりも大事。
・コードのツギハギはあんまよろしくない。多分現場猫並にコードはちゃんと確認したほうがいい。
