木幅が1のグラフの木分解と動的計画法

普通に木DPをします。 ei1333.hateblo.jp

DDCC2020参加記

NHK杯で羽生結弦を(オンサイトで)見ていたら予選出れなかった じょえくんとしてDDCCに参加していません— 卒論に内容はいらない!🐄 (@ei1333) January 25, 2020 うしくんもぐもぐ笑 これはなに? たぷりすたべる

Minimum Feedback Vertex Setの乱択アルゴリズム

Feedback Vertex Set (FVS)とは、グラフの頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。 最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知…

卒論名言集

1年前の卒論関連のSlackを見返していたらわりと面白かったのでまとめます ちなみに締切は2/1だったみたいです。 1/19 DDCCの装置実装部門の話で盛り上がっている 1/20 けんしん「またライブラリの闇と戦っていたら1日が終了しかけている」 1/21 (ラボ内締切…

【小学校の試験の採点基準的な】よくツイッターでみるやつについての見解

ツイッターでもう見飽きた話題の一つなんですが、話題自体としてはそこそこ議論の余地があるものなので見解をまとめておきます。 ざっとツイッターを見る限り、算数・数学の試験を 算数・数学をわかっているかのチェック 課程を理解しているかのチェック と…

じょえチャンネル開設にむけて

ICML提出したら開設してみようかな〜と思っています コンテストの解説とかをメインコンテンツにするつもりはまったくなくて、普通に競プロerたちがワイワイガヤガヤやって、界隈ならではの盛り上がり方ができるところを動画にしたいなと思っています プログ…

2020年の抱負

今年の目標は ICML/NeurIPS/AAAI/ICLRのどれかに通す グラフアルゴリズム系の学会のどれかに通す 強いメンタルをもつ です。がんばるぞ〜

研究がまた先行研究とかぶった話

まあ別に初めてではないのであれなんですが 今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、 先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて…

平面グラフアルゴリズム

お待たせいたしました。Competitive Programming Advent Calendar 2019 8日目の記事です。 平面グラフとは 平面グラフとは、平面に辺を交差させずに描画できるグラフのことをいいます。現実世界の例では多くのroad mapがそうであったりします。平面グラフで…

非CTF勢によるCTFの解き方

writeupです。 ++age;今日誕生日なので, 1日限定でCTFを開催してみました。https://t.co/U02CnUnGge問題はあまり難しくないかもしれませんが, 息抜きにでも参加してみてください!— Tasker (@task4233) December 4, 2019 深夜にツイッターを見ていたら面白そ…

DPC広島に参加しました

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

タイ旅行の知見

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のタブ幅等の変更、テンプレ…

DAGの橋?

なんか初めて見たので。 DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定) DAGを無向グラフとみなして橋を求めるのはダメです。 4頂点4辺で、辺がそれぞれ 1 2 2 3 1 4 2 4 を結ぶような…

サイクル基底・サイクルの個数について

チームでICPC練をしていたらサイクルの数を数える問題に遭遇した(Count Cycles: Asia Tsukuba Regional 2017) サイクル基底を知らずに解けたけど(追記: 解けてなかった)サイクル基底を知らなかったのでついでに調べた。 サイクル基底 まず直感的な説明をしま…

LinkCutTreeを書きました

拾ったLinkCutTreeの使い方がわからないことがたまにあったので自分で一番使いやすいと思うものを書きました。 けんしんのLazySegmentTreeやぼくのImplictTreapとまったく同じインターフェースで使えます。 たまに便利なモノイドが追加されるのでそれが一気…

進化したImplicit Treapたち

はじめに 昨年のAdvent Calendarで書いた、Implicit Treapというとても有能なデータ構造があります。 xuzijian629.hatenablog.com 機能をもりもり盛り付けた平衡二分探索木で、セグ木でできるような操作が、配列の要素を反転したり削除したり挿入したりしな…

龍が如く 劇場版 (2007) 感想

YouTube Moviesでおすすめに出てきたので300円払って見た。 www.youtube.com ストーリーは、初代龍が如く、およびそのリメイクである龍が如く 極に沿った形になっているがだいぶショートカットされている。 高評価58低評価13ですでに心配だったが見終えてみ…

Python(特にNumPy)の配列操作

紹介 NumPyの配列操作の仕組みについて紹介します。生のPythonよりもできる操作が多いのでこちらで統一します。 さて、NumPyで a = [1,...,n] b = a[::-1] としたとき、2行目の操作はかかご存知ですか?まあこれはです。他にもNumPyは配列に関する多くの操作…

KUPC2019参加記

なぜか京都会場で申し込んだら台風で東京会場が中止になったので大勝利した KUPC2019の東京会場ですが、登録TAに勝利して楽しみにされていたことかと思いますが、残念ながら台風19号の参加により中止とします。オンラインでの参加は可能ですので、自宅からバ…

フフホト市旅行記

突発旅行!じょえにきあくん笑 夏休みも最後の2日だし一泊二日で国内旅行したいなぁ〜と思っていたところ、実はラボのセミナー開始まで1週間あることに気づいたので、遠出しようと思いました。 ぼくはわりと突発旅行をよくするそうですが、海外旅行で、当日…

ゆるふわオンサイト2に参加した

www.hackerrank.com before contest 普段会わない人と新宿でご飯でも食べようと思ったが、12:30頃に起床。そのまま会場へ向かう contest A, B, Cを開いて解く。速解き勢がいなかったためかFA。ちなみに見せ場はここで終了です D: n-dwich box 最初、正規表現…

GNU C++ ext/rope

ext/ropeの日本語の記事が皆無だったので使い方を書く。 できること 配列みたいにして使います。 ランダムアクセス 任意箇所への要素の挿入 任意箇所の要素の削除 がでできます。 サンプルコード #include <bits/stdc++.h> #include <ext/rope> using namespace std; using namespace </ext/rope></bits/stdc++.h>…

Macでchainerを使う(CUDA, cuDNNと)

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…

GPU対応Macでpytorchを使う

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

TTPC2019に参加しました

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

Googleのインターンホストマッチングに2年連続落ちた話

やってられるかこのクソ運ゲー採用 まあ今回はホストマッチング用のFormを提出しなかったぼくが悪いようですが(マッチング時期を夏休みのインターンとかぶらないように変えたかっただけなんですが未提出という扱いになったっぽい)、以前から言いたいことが多…

Macでcupyをインストールする

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

自分用Makefileのメモ書き

基本構文 <target>: <files> <commands> <target>: <commands> 実行 makeとやると、Makefileに定義された最初のターゲットが実行される。他のターゲットを実行するにはmake clean, make installなど臨機応変にターゲット名を入力。 特別なターゲット名 .PHONY .PHONY test とかよくみる。コマンド名とフ</commands></target></commands></files></target>…