HHKB プログラミングコンテスト 2020 D - Squares

2年前の問題になりますが HHKB プログラミングコンテスト 2020のD - Squaresについてです。 atcoder.jp問題としては1辺Nの正方形のグリッド中にA(1辺a),B(1辺b)の2つの正方形を重ならないような配置の総数を求めるというもの。解説だと余事象から求めている…

Microsoft Certified: Azure Fundamentals 取得した

5/12,13で予定していた Azure Virtual Training の 2日目 がキャンセルとなり、丸1日分無駄になるというアクシデントもありましたが、AZ-900 の認定試験に合格し、Azure Fundamentals 取得しました。www.credly.comFoundamental なので初級者向けですが、開…

ABC 246 E - Bishop 2

atcoder.jp 解説では拡張ダイクストラや01BFSだけど、ずっとTLEで通すまで時間がかかったので忘れないようメモ。 右上がりのラインと左上がりのラインで到達できる範囲を頂点と考える。 すると各マスの右上がりラインと左上がりラインに辺を貼ることで、曲が…

AtCoder ABC 167 F Bracket Sequencing

ABC 167は5完 Eの実装で時間を溶かしてしまってFが解けなかった。atcoder.jp問題としては( と )だけの文字列が複数与えられるので、好きな順番で連結して、括弧の対応が取れた文字列にできるかどうかの判定それぞれの文字に対し対応する括弧を潰すと、))(((…

簡易 PQueue

バイナリヒープの優先度付きキュー使い方 pq = PQueue.new %w/1 12 123 abcd abc/.each do |w| pq.enq(w,w.size) # 優先度を指定して追加する。#enq(value, priority) end puts pq.deq until pq.empty? # #deqでpriorityの小さいもの取り出せる 1 12 abc 123…

ABC-147 E

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

ABC146-F

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

ABC 144 F - Fork in the Road

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

ABC142 F - Pure

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

ABC137 D - Summer Vacation

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

gradle-swagger-generator-pluginにOpenAPI Generator対応のPRがマージされた

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

グラフの密度

k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。超訳 Abstract最新のグラフマイニングツールでは、k-core分析によりグラフを階層構造に分解するのは標準的な操作です。k-core分解は…

Git LFSは別にリポジトリサーバー側で対応が必要なわけではなくて、LFSサーバーが必要なだけ

GitHubやbitbucketのLFS対応もなんかストレージの料金がすごい高いなぁとおもっていて、リポジトリをホストするサーバーで対応が必要とおもっていたのですが、調べてみるとどうやら違うようでした。ydkk.hateblo.jpLFSサーバーをAWS Lambdaに構築して、S3を…

TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。 https://nekop.hatenablog.com/entry/20131220/1387524669 EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で…

俺のFPTの理解

FPTにおいては幅とパラメータが存在する。たとえば幅をk-coreとすることができるというのが、最大クリーク問題つづき - 高温処理済みコースケの話。 k-クリーク判定では幅に対しての組み合わせになるので二項定理からなので、を用いてのオーダーで上限を決め…

なんとなく

最大クリーク問題のの中身を分解して、の多項式になっていることを証明しないとダメな気がしてきた。わかった。ZPP=EXPTIMEでP≠NPのほうだ

最大クリーク問題つづき

グラフのDegeneracyをkとすると前処理後、おおまかで最大クリークが求まるな。Degeneracyのページにしたがって、最大出次数を最小化するように、無向グラフを順序付け、辺を向き付けし、有向グラフに変換する。これは多項式時間でできる。最大出次数をとする…

K4の対辺をつなぐ話(2)

前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、 kousuke.hatenablog.comそれって式にするとこういうことになるのかな? fはの辺を頂点にして、がの時に辺とするような変換。 完全グラフについては証明できそうだけど…

保育士は「誰でもできる仕事」か?について

news.yahoo.co.jpでこの記事に対して、下記のようなブクマコメントをしたのだけれど、1つではあるけれど、スターがついてしまったのでメモ代わりに書いておこうとおもう。保育士は「誰でもできる仕事」か(駒崎弘樹) - 個人 - Yahoo!ニュースホリエモンは保育…

選挙とか

興味はもつのだけれども、投票したい政党とかがないなぁ。 二大政党制とか目指すのやめたほうがいいんじゃないの?とおもってきた。 STOP安倍政権のスローガンとかみていると、そもそも単独政党による過半数とかできるルールが悪いんじゃないかとおもってきた…

K4の対辺を繋ぐグラフにしてみる

の各辺を頂点にして、その完全マッチングの対に辺を引くという変換をおもいついて、やってみたら面白かった。 → 1頂点 → 3頂点、辺無し → 6頂点、3本の辺 → petersenグラフ → 正則グラフ → 正則グラフ Rの右肩が次数、右膝が頂点数。たぶんあってるとおもう…

計画性

自分はすごく計画性がないなとおもっているんだけど、最近すこしづつ計画性がついてきたとおもっていて、それでも人から期待される程度の1割以下だとおもっているので、自分の成長を自分でほめて、且つ、人には申し訳ない感じなので、大変こころがつらい。

ヒューリスティックな彩色

k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続…

最大出次数を最小にする順序/Rubyのpriority queue

kousuke.hatenablog.com以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。Degeneracy (graph theory) - Wikipediaアルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。…

最大クリーク問題(改)

最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。補グラフをk彩色できたら、…

P≠NP予想が嫌い

P≠NP予想 - Wikipedia 多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。 別にP=NPでもP≠NPでもどっ…

続(4) - 最大クリーク問題

多分4じゃないかと思う。ナンバリングは適当 グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ 補グラフが非連結も同様 すげぇコンパクトになるんですけどって感じだ。これが…

巡回セールスマン問題

最大クリーク問題は改善があって、これでいいってところまで来たので一旦終わり。 巡回セールスマン問題でなんとなくアイデアが湧いて、葉指定 + k-best最小全域木問題に帰着できないかな?とおもっている。 ハミルトン閉路から一本辺取り除いたら道だけど、…

最大クリーク問題の現在

Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースでがはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあっ…

最大クリーク問題で面白いなとおもったこと

いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。 ある無向グラフGについてを最大クリークサイズを返す関数とする。f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフをとすると g(m) : グラフが非…