Nim で yukicoder の最短時間を取って遊ぶ その2

やっていきで現在425問といて58問最短になった. ☆3からはみんな最短取るやる気を出してきたので最短が難しくなってた.... getchar_unlocked()の力だけで倒せる問題は置いておくとしてその他の問題を備忘録.

No.697 池の数はいくつか

https://yukicoder.me/submissions/312381

愚直に地図中の池の数を数えるだけ. queueや再帰を使ったりして何周もするように書いてしまうと遅いので, 最低限のunionfindを使って一回で実行・計測すると最短を取れる.

No.634 硬貨の枚数1

https://yukicoder.me/submissions/312348

この問題は予めある程度結果を計算できる. Nimでは const C = (proc():seq[int] = ... )() と書けばコンパイル時定数代入として 150万回まで計算できるので最短を取るのは容易.

No.554 もconstが使えて楽.

No.523 はconstにすると150万回を超えたので渋々埋め込み. No.502 も. No.027 も.

No.537 ユーザーID

https://yukicoder.me/submissions/310597

SFFやミラーラビンで殴ると最短が取れる.

No.414 も. No.376 も. No.312

No.342 一番ワロタww

https://yukicoder.me/submissions/311076

unicodeの文字列処理.Nimで何も考えずに書くだけで意外にも最短を取れた.

No.304 鍵

https://yukicoder.me/submissions/304950

ランダムに鍵を試すだけのコードだが,何となく乱数のシードを 61725 にすると最短を取れた.

No.233 めぐるはめぐる (3)

https://yukicoder.me/submissions/313061

二つの順列を組み合わせて無駄な名前を作らないようにするのがまず第一条件. その上でstringを経由している暇はないため,全て char* で管理して unordered_set<size_t> に喰わせるときには hash<string>() にして喰わせると string 的な気持ちで書いたまま最短が取れる.

No.120 傾向と対策:門松列(その1)

https://yukicoder.me/submissions/312133

sort も priority_queue も必要で,Nimの標準ライブラリのそれではとてもじゃないが速度が足りない. なんと Nim のソートは マージソートなのだ! 素直にC++で書いて最短.

No.50 おもちゃ箱

https://yukicoder.me/submissions/313570

BitDP. 最初は関数を作って再帰的に書いていたが, 実はn個の(O(n*2n)の)bitDPは for i in 0..<(1 shl n) って外側に書いて回すといい感じに回ってくれる.簡潔に書けて速くて便利.

No.009 モンスターのレベル上げ

https://yukicoder.me/submissions/313351

Nimの雑に書いた自作PriorityQueueではC++のそれには勝てなかったが, この問題の性質上,ある程度探索すると答えは早めに出るので打ち切っていいハズなので 現状の最短より10msくらい早い時間で打ち切るようにしたらACだったので発想の勝利.