https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf LP緩和の解はシンプレックスの端点であり、シンプレックスの端点は、「異なる2つの実行可能解の合成でかけないこと」と同値。 non-halfintがあったとすると、その解をεだけ上下にずらした…
https://hochbaum.ieor.berkeley.edu/html/pub/EJOR-3var.pdf IPの制約がMonotoneのときは、minCutに帰着して多項式時間でhalfintegral解が求まるっぽい。目的関数は非線形でもいいらしい。 あとで読む。
writeupです。 ++age;今日誕生日なので, 1日限定でCTFを開催してみました。https://t.co/U02CnUnGge問題はあまり難しくないかもしれませんが, 息抜きにでも参加してみてください！— Tasker (@task4233) December 4, 2019 深夜にツイッターを見ていたら面白そ…
www.crcpress.com この本がすごい。というかほしい。
link.springer.com 線形計画問題は Unbounded Infeasible has an optimal solution の3通りしかないけど整数計画問題はそうとは限らなく、 いくらでもいい結果が存在する というパターンがある。 たとえば、 maximize subject to , is positive integer など…
www.sciencedirect.com 自分の問題の解決になるかなあと思って読んだけど特にならなかった。 https://xuzijian629.hatenadiary.jp/entry/2019/11/28/133732 こちらの記事とはかなりやり方が違う。 初めにtriangulateするところは同じだけど、かなり幾何的に…
www.semanticscholar.org 無料PDFが見つからなかったのでスライドを読んだ。 https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf?_ga=2.178289380.1937718360.1574912307-1595927464.1574667430 アルゴリズムは3ステップに別…
https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf をざっと見た。 平面グラフのsubgraph isomorphismで、のサイズを定数をすると、時間で解ける、という論文。 とくに、の木幅をとすると、時間で判定できるっぽい。 細かくは読んでいない。
cs.smith.edu Grid Graph がsolidであるとは、格子点におけるの補グラフの連結であるということである。 グリッドグラフ上でのハミルトンパス（もしくはサイクル）問題は、solidなグリッドグラフ（穴を含まない）なら多項式時間で解くことができるが、一般の…
優勝しました！ これでやっと競プロのコンテスト優勝者を名乗れる… 申し込み ICPCとかぶっているということで、賞金チャンスがかなり高まったのでモチベがあがります。 Girigiriは仲がいいのでこういう情報はちゃんと隠されずにシェアされてうれしいですね〜…
https://pdfs.semanticscholar.org/9c89/7e65499cc6caacabd8abab6071010b03248c.pdf この資料が秀逸だった。
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木と後退辺を覚えてお…
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（東…
コンテスト編はこちら xuzijian629.hatenablog.com レジ編 9月下旬ぐらいにレジります。The ICPC International Collegiate Programming Contestから参加したい大会を選び、あとは国内予選と同じです。思ったよりハードルが低かったです。普通はコーチが必要…
コンテスト編以外は後日書きます。 コンテスト ぼくが環境を構築する。ctrl:nocapsにする。設定から画面スプリットのショートカットを変更、マウススクロールの方向を変更、.vimrcの作成、.bashrcにg++のエイリアスを追記、geditのタブ幅等の変更、テンプレ…
なんか初めて見たので。 DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定) DAGを無向グラフとみなして橋を求めるのはダメです。 4頂点4辺で、辺がそれぞれ 1 2 2 3 1 4 2 4 を結ぶような…
チームでICPC練をしていたらサイクルの数を数える問題に遭遇した(Count Cycles: Asia Tsukuba Regional 2017) サイクル基底を知らずに解けたけど(追記: 解けてなかった)サイクル基底を知らなかったのでついでに調べた。 サイクル基底 まず直感的な説明をしま…
拾ったLinkCutTreeの使い方がわからないことがたまにあったので自分で一番使いやすいと思うものを書きました。 けんしんのLazySegmentTreeやぼくのImplictTreapとまったく同じインターフェースで使えます。 たまに便利なモノイドが追加されるのでそれが一気…
はじめに 昨年のAdvent Calendarで書いた、Implicit Treapというとても有能なデータ構造があります。 xuzijian629.hatenablog.com 機能をもりもり盛り付けた平衡二分探索木で、セグ木でできるような操作が、配列の要素を反転したり削除したり挿入したりしな…
とりあえずいくつか面白い論文をみつけた Randomized Incremental Construction of Delaunay and Voronoi Diagrams Randomized Algorithms for Geometric Optimization Problems An Introduction to Randomization in Computational Geometry ひとつ読んだの…
YouTube Moviesでおすすめに出てきたので300円払って見た。 www.youtube.com ストーリーは、初代龍が如く、およびそのリメイクである龍が如く 極に沿った形になっているがだいぶショートカットされている。 高評価58低評価13ですでに心配だったが見終えてみ…
紹介 NumPyの配列操作の仕組みについて紹介します。生のPythonよりもできる操作が多いのでこちらで統一します。 さて、NumPyで a = [1,...,n] b = a[::-1] としたとき、2行目の操作はかかご存知ですか？まあこれはです。他にもNumPyは配列に関する多くの操作…
なぜか京都会場で申し込んだら台風で東京会場が中止になったので大勝利した KUPC2019の東京会場ですが、登録TAに勝利して楽しみにされていたことかと思いますが、残念ながら台風19号の参加により中止とします。オンラインでの参加は可能ですので、自宅からバ…
突発旅行！じょえにきあくん笑 夏休みも最後の2日だし一泊二日で国内旅行したいなぁ〜と思っていたところ、実はラボのセミナー開始まで1週間あることに気づいたので、遠出しようと思いました。 ぼくはわりと突発旅行をよくするそうですが、海外旅行で、当日…
www.hackerrank.com before contest 普段会わない人と新宿でご飯でも食べようと思ったが、12:30頃に起床。そのまま会場へ向かう contest A, B, Cを開いて解く。速解き勢がいなかったためかFA。ちなみに見せ場はここで終了です D: n-dwich box 最初、正規表現…
ext/ropeの日本語の記事が皆無だったので使い方を書く。 できること 配列みたいにして使います。 ランダムアクセス 任意箇所への要素の挿入 任意箇所の要素の削除 がでできます。 サンプルコード #include <bits/stdc++.h> #include <ext/rope> using namespace std; using namespace </ext/rope></bits/stdc++.h>…
CuPyのインストールはこちら xuzijian629.hatenablog.com pip install chainer して import chainer すると >>> import chainer /Users/xuzijian629/.pyenv/versions/anaconda3-5.3.1/lib/python3.7/site-packages/chainer/backends/cuda.py:143: UserWarnin…
