Joeの精進記録

旧:競プロ練習記録

2019-11-01から1ヶ月間の記事一覧

On the existence of optimal solutions to integer and mixed-integer programming problems

link.springer.com 線形計画問題は Unbounded Infeasible has an optimal solution の3通りしかないけど整数計画問題はそうとは限らなく、 いくらでもいい結果が存在する というパターンがある。 たとえば、 maximize subject to , is positive integer など…

A linear-time algorithm for drawing a planar graph on a grid

www.sciencedirect.com 自分の問題の解決になるかなあと思って読んだけど特にならなかった。 https://xuzijian629.hatenadiary.jp/entry/2019/11/28/133732 こちらの記事とはかなりやり方が違う。 初めにtriangulateするところは同じだけど、かなり幾何的に…

Embedding Planar Graphs on the Grid

www.semanticscholar.org 無料PDFが見つからなかったのでスライドを読んだ。 https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf?_ga=2.178289380.1937718360.1574912307-1595927464.1574667430 アルゴリズムは3ステップに別…

Subgraph Isomorphism in Planar Graphs and Related Problems

https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf をざっと見た。 平面グラフのsubgraph isomorphismで、のサイズを定数をすると、時間で解ける、という論文。 とくに、の木幅をとすると、時間で判定できるっぽい。 細かくは読んでいない。

TSP in Solid Grid Graphs

cs.smith.edu Grid Graph がsolidであるとは、格子点におけるの補グラフの連結であるということである。 グリッドグラフ上でのハミルトンパス(もしくはサイクル)問題は、solidなグリッドグラフ(穴を含まない)なら多項式時間で解くことができるが、一般の…

DPC広島に参加しました

優勝しました! これでやっと競プロのコンテスト優勝者を名乗れる… 申し込み ICPCとかぶっているということで、賞金チャンスがかなり高まったのでモチベがあがります。 Girigiriは仲がいいのでこういう情報はちゃんと隠されずにシェアされてうれしいですね〜…

平面グラフの平面直線埋め込み

https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf この資料が秀逸だった。

Convolutional Rectifier Network as Generalized Tensor Decomposition

http://proceedings.mlr.press/v48/cohenb16.pdf を読んだ。 概要 ConvNetの理論解析をテンソル分解で行っている。 結果として、ReLU + max-poolでのuniversality, ReLU + ave-poolでのnon-universality, depth efficiencyなどを解析している。 Related Work…

平面グラフ判定&描画アルゴリズム

元論文はhttp://hinkali.com/Education/PlanarityTesting.pdf ここが日本語で説明してくれている http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html アルゴリズム グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えてお…

Stability and Generalization of Graph Convolutional Neural Networks

https://arxiv.org/pdf/1905.01004.pdf を読んだ。 問題設定 データセットと学習アルゴリズムを固定したときに、入力に対する予測の誤差の期待値を抑えるのではなく、その期待値と、有限個の入力での誤差の平均の差(Generalization Error)を抑える。 →何個ぐ…

隣接行列とグラフラプラシアンの固有値について

頻繁に忘れるのでメモしておく 隣接行列 固有値の和は0 . ただしは異なる固有値の個数 最大固有値は平均次数以上最大次数以下 Gが2部グラフであることと、固有値が0について対称に現れることは同値 http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/conten…

タイ旅行の知見

LINE Pay(厳密にはRabbit LINE Pay)が使える。準備していったら普通に便利そう。 【キャッシュレス決済】タイで現地のLINE Payを使ってみた。BTSラビットカードと紐付けてチャージ不要で電車に乗ったり、お店でスマホを使った買物ができたりする Grab(東…

ICPC Bangkok Regional参加記(コンテスト以外編)

コンテスト編はこちら xuzijian629.hatenablog.com レジ編 9月下旬ぐらいにレジります。The ICPC International Collegiate Programming Contestから参加したい大会を選び、あとは国内予選と同じです。思ったよりハードルが低かったです。普通はコーチが必要…

ICPC Bangkok Regional参加記(コンテスト編)

コンテスト編以外は後日書きます。 コンテスト ぼくが環境を構築する。ctrl:nocapsにする。設定から画面スプリットのショートカットを変更、マウススクロールの方向を変更、.vimrcの作成、.bashrcにg++のエイリアスを追記、geditのタブ幅等の変更、テンプレ…