wataの日記

プロコンや研究の話など書くかも

ICFPC 2019 参加記

今年もUnagiチームのいつものメンバーで参戦。今年の問題は二次元グリッド上でロボットを動かして全部の空きマスを塗りつぶすという基礎タスクに、追加仕様でブーストアイテムなどが加わっていくというものだった。暫定順位では1位なので優勝出来ていると良…

ICFPC 2018 参加記

今年もチームUnagiのいつものメンバーで参加。今年の問題は最大40体のロボットを並列に操作して指定された3Dオブジェクトを出来るだけ効率よく構築・破壊するというタスクだった。各ロボットにどう仕事を割り振るかやお互い干渉しないようにどう動かすか…

0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms

NIIの吉田さん、阪大の山口さんとの共著論文 https://arxiv.org/abs/1704.02700 が理論計算機科学のトップ会議FOCS 2018に採択されました。 概略 与えられたグラフが森か?二部か?与えられた2-CNFが充足可能か?など様々な問題が単純なDFS (unit propagatio…

Linear-time Kernelization for Feedback Vertex Set

https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします. 概略 取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い,与えられた無向グラフの最小FVSを求める問題をFVS問題と言います.これは有名なNP困…

ICFPC 2016 参加記

運悪く日程が被ったDCJ決勝は棄権し今年もいつものチームでICFPCに参加.メンバーと役割分担,問題概要はchokudaiの記事を参照.ソルバの実行結果ログなどから思い出したところによると,以下の様に3日間作業した. 一日目(Lightning) 公式Twitterの発言か…