頻繁に忘れるのでメモしておく 隣接行列 固有値の和は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…

以前はcupyをインストールしましたが、今回もなかなかに面倒でした… xuzijian629.hatenablog.com バージョンについて 最近のpytorchをビルドするにはCUDA 9.0以上が必要なのですが、CUDA 9.0以上にした状態でcupyをインストールしようとすると、nvccのエラー…

team omorisuJoe(@omochana2, @risujiroh. @xuzijian629)で参加して5位（オンサイト2位）でした！ もともとteam Girigiriで参加すると思っていたのですが、ぼく以外のteam GirigiriのメンバーはTTPC2019募集開始日からすでに相手を決めていたらしく、会場で…

（追記）こんにちは、社会人のJoeです。この当時はいろいろ未熟なところが多く、記事の内容がかなり過激なのですが、当時の気持ちを尊重したいという考えもあって、残しておきます。記事の最後に社会人目線での今の感想も載せておくのでよければそこまで目を…

b-matchingというものを知った。 グラフが与えられたとき、次の条件を満たす辺集合はb-matchingであるという。 各頂点のdegree restrictionをとし、各辺のcapacity が与えられる。このとき各辺についてcapacity以下の重みをとって、各頂点について隣接する辺…

A separator theorem for minor-closed classes を読むと、minor-closedなグラフはのseparatorを持つのでは？という話がされている。この論文では実際に、をminorとして含まないようなグラフについて、のseparatorを持つことを証明している。 したがって、bo…

A Separator Theorem for Planar GraphsとOn Sparse Graphs with Dense Long Pathsを読む。 ちょっとずつまとめていく。 On Sparse Graphs with Dense Long Paths 論文の主定理は以下の通り どんな頂点を取り除いても長さのPathが残るようなDAGの辺数をとし…

e-archive.informatik.uni-koeln.de を読んだ。 https://icpc-girigiri.slack.com/archives/GJM417MNV/p1566016527000100 にファイルがある。 概要 平面グラフのmax-cutをmaximum weighted matchingに帰着させて解いている。平面グラフのmaximum weighted ma…

次数行列をかけて正規化してやらないとだめ。 証明したい

数学的なグラフは頂点の接続情報だけが重要だけど、分子は、立体的な構造を伴う。 ラベル付きグラフの重み（頂点間距離）を学習したり、頂点間距離からラベル（原子）を学習したりできる。 pre-trainingにいいかもしれない。

これやってる人いるかな。普通に気になる。 平面グラフ from yutaka1999 www.slideshare.net yutaka1999氏のスライドがあり、平面グラフ判定は本気を出すとでできるなどと書かれていてびっくりする。 Max-Cut e-archive.informatik.uni-koeln.de 平面グラフ…

https://arxiv.org/pdf/1905.12265.pdf 読んだ。大抵のGNNのタスクはnode classificationだけど、化学や生物の分野だとlocal similarityやgraph全体の特徴が重要になることが多い。 この論文では、自然言語処理で行われるような、Context PredictionやMaskin…

えー。また競プロとは全然関係のない記事です。同じことをやっていそうな人が少なくてエラーが出てこなかったのでまとめます。 手順1: CUDA対応MacBook Proを購入する えー。MacBook Mid 2012-2014 15 inchしか対応していないと思います。しかも15 inchじゃ…

Quadratic Assignment Problem (NP-hard) Given , () ただしはとの要素ごとの積の和 Graph Isomorphism 図は省略するが、同型なグラフがあったときに、頂点のラベル付けの置換行列をとすると、はとなる。 同型ならとなる。 Subgraph Isomorphism 頂点の個数…

https://arxiv.org/pdf/1905.10947.pdf PFNで著者と話したのでメモ GCNの表現能力についての問題。畳み込みの際に用いるの特異値が小さい場合、レイヤー数に対して指数的に表現能力が落ちてしまうという問題。 連結成分数に対応して大きさが決まる特定の空間…