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.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だったので発想の勝利.