解説通りのO(HW(H + W)M) をRubyで書くとTLEした(コンテストは不参加)のでbetrue12さんのを参考に読み解いてみたら、震えた。atcoder.jp取りうる差分をビットで表して、右ビットシフト、左ビットシフトでORを取るDPしてた。すげぇ。下記は理解後、自分で書い…

時間内にたどり着けなかったけど、たぶん後ろから貪欲にとれば、辞書順最小だな。j回でたどり着けるとして、j回目の出目をとすると、なので、辞書順最小は後ろからとれるだけとるのが最適なはず。 一度、後ろから累積minを取ってやると楽ちん。 def max(a,b)…

解説を読みつつRubyだとTLEなのかな。とおもいつつclimpetさんがACしていて、コードゴルフじゃないC++のコードがあったので、そちらから読み解いてみた。参考 : atcoder.jp各頂点毎に辺を一つ潰したときと一つも潰さないときの1 -> Nへの期待パス長への差分…

atcoder.jp誘導部分グラフが閉路になっているような頂点集合を求める問題、解説通りに実装してみた。コンテスト中は閉路からより小さい閉路ってどうやんの？だけど、解説見るとなるほど!だった。閉路を検出して、その誘導部分グラフ内の閉路として使われてい…

D - Summer Vacation解説(別解のマトロイドのほう)を読みながら、UnionFind木の構造を少し変えると、うまく解けそうとおもったら解けたので記念に貼っておく。解説では以下のようにセグメント木を使う説明だったけど、セグメント木とかつかわず、もうすこし…

OpenAPI / Swagger関連の勉強をしていて、gradle-swagger-generator-pluginを見つけました。gradle-swagger-generator-pluginはOpenAPI文書から、Swagger UI, ReDocなどのHTMLやコード生成を行ってくれます。コード生成の有名どころだとswagger-code-genとop…