最小値の最大化を最大値の最小化と思い込みタイムロス。
最小値をk以上にできるかという判定問題を考えれば、2-SATに帰着できることは分かったがどう考えても500点の難易度ではないので実装を考えた。
結局色々考えたあげく、2人の間の関係を(同じ符号のみOK/異なる符号のみOK/どちらでもOK)の3つに分け、dfsして解いた。2-SATに還元したほうがマシだったまである。

D問題

どう考えても順序が必要なので、H順,P順がダメな事を確かめてH+P順を考えたがうまく証明できない。
めちゃくちゃ色々考えて詰まる。
残り1時間くらいになったので仕方なく他を読む。

F問題

Eは回文というキーワードを見た瞬間無理と感じたので、構築ゲーのFを考える。できなさそう。残り30分くらいでDに戻る。

D問題

実験でどうもH+P順が正しそうなのでDPを実装中。バグって時間切れ。
終了後15分くらいで解けた。

4完を目標にしていたが3完でレートも40以上減ってとても悲しい。

Dの貪欲部分の証明

2以上の最適解が存在すると仮定する。
この時、座布団を置けない人は後ろに固めても最適である。以降座布団を置く人のみを考える。
連続する2人に注目する。この2人が座布団を置く前の座布団の枚数を $x$ ,先に座布団を置く人を $(H_1,P_1)$ 、後に置く人を $(H_2,P_2)$ とおく。
この時次が成り立つ。
$x \leq H_1$ かつ $x+P_1 \leq H_2$
ここで、 $H_1 + P_1 > H_2 + P_2$ と仮定し、この2人の順序を入れ替えても同じ人数で座布団をおけること、すなわち $x \leq H_2かつx+P_2 \leq H_1$ を示す。
$x \leq H_2 - P_1 \leq H_2$
$x + P_2 \leq H_2 + P_2 < H_1 + P_1 \leq H_1$
ゆえに、座布団を積む人は $H_i + P_i$ 昇順に並べ替えてもよい。

トーナメント

本戦が3完で冷えたため、もっとも下のグループ6に入った。

Round1

なぜかC,D問題の2問。
C問題を開く。カッコ列と言えばDP。
カッコ列１つでどうこうするのかと思い込み誤読する。
素直なDPの $O(N^2)$ だとやばいが、カッコ列に対応するxy平面上を動く点を考えると、原点近くの5つくらいしか要らないことに気づいてなんとかなった。
遷移を書くのがややしんどかった。
D問題は最小の部分点（パスの場合）を目指したが、ギリギリ提出してWA。
勝ち上がった。

Round2

A問題を読む。概要を理解するのが少し難しい。
部分点をよく読むと200点はただ最小全域木を実装すれば取れることに気づき、提出。
Aでさらに点を取れる気がしなかったのでBへ。
B問題、k=1の操作が左シフトなことには気づくが、k=n-1は全く思いつかなかった。
最初の部分点を幅優先探索で取ろうとしたが時間切れ。
200点のみだが早めだったため勝ち上がり。

Round3

Round2までの順位表から、グループ6では早解きだけしてれば勝てそうというのが分かったので、とにかく小さい点から素早く取る作戦にした。
Eの200点(1): 愚直に距離（演算はmin）を計算するだけ。面倒なのでダイクストラを貼った。
Fの200点: bitDPで全列挙して条件に合うやつをカウントするだけ。
Eの200点(2): コストが2の辺のみで連結成分を考えて、うまく計算するだけ。UnionFindを貼った。
余った時間は祈ってた。
結果作戦大成功、2位でトーナメント勝利。
１位は本戦なぜか0点の赤コーダーなので実質優勝（？）
4年間CODE FESTIVALに出て壇上は実は初めてな気がする。本戦がダメだった分ちゃんとパフォーマンスを出せて良かった。

リレー

チーム内の本戦順位は下から2番めだったが、開始直後に雑に問題を取ったのでD問題を読んだ。
そこそこ考えたが、1と2を含む連結成分のうち大きい方に残りの頂点全部くっつけてクリークにすればよさそう。
と、考えた所でJ問題の公式が降ってきて実装を任された。
万が一公式が間違っていたら大変なことになるので不安だったが、断れないのでやった。
実装中にキーボード操作が一切効かなくなるトラブルが発生してパソコン再起動（つらい）
実装もintをintで割るなどして3WAくらい出し、パソコンスペースで時間を食いすぎてしまった。
後半戦で実装が詰まる状況になったのでこれは良くなかった。
JをACしてからは隣のrianさんとEの考察をしていた。式変形していたらそれっぽいのが出てきたので、rianさんと確認し、海外プロのお墨付きも貰って良さそうだとなった。
Eは通ったので一安心。
実験ゲーや構築ゲーが残っていなかったので残り時間は祈っていた。
チームとしては8完で終わった。

雑多な感想

秋葉原UDXを知らず、電気街口から大通りの方に歩きながらGoogle Mapを開いてびっくりした。
参加人数が前年から200人→100人になったり、一部コンテンツが縮小してしまったのは残念だが、海外参加者が世界中から集まったり、置いてあるお弁当が強そうだったりと良くなっている点もあった。（まい泉とかね）
席が映像や音響をやってる人と超近く、真後ろに高そうな機材が並んでいた。機械を眺めるのは面白いが、近くを通ったり飲み物を運ぶのは怖い。
今年もCODE FESTIVAL開いてくれたリクルートに感謝🙏
じゃがりこチーズ味が戦利品バッグに入りっぱなしなことを今思い出した

2017-06-15

Splatoon2 に向けてボイスチャット環境を変えた

ゲーム

Splatoonをやる時はイヤホンとヘッドセットを同時に装着していたので耳が痛くなっていた。
ヘッドセットが壊れたのと、Splatoon2が発売されることを考えてボイスチャット環境を見直した。

ゲーム音とPCの音をミキサーで混ぜてヘッドセットにつなぐことで、ヘッドホンとイヤホンの同時装着から解放され、各音量をツマミで調整できるようになった。

買ったもの

ミキサー： YAMAHA AG03

YAMAHA ウェブキャスティングミキサー 3チャンネル AG03

出版社/メーカー: ヤマハ(YAMAHA)
発売日: 2015/05/31
メディア: エレクトロニクス
この商品を含むブログを見る

ヘッドセット： Logicool G430

Logicool ロジクール G430 サラウンドゲーミングヘッドセット Dolby 7.1 Windows対応

出版社/メーカー: ロジクール
発売日: 2013/08/23
メディア: Personal Computers
この商品を含むブログを見る

ケーブル： audio-technica ATL462A/1.5
http://www.yodobashi.com/product/100000001001251353/

ゲームの音(GamePad, Switch, AVT-C875から)とPCからの音をパソコンの外で混ぜたいのでミキサーを使用する。
ミキサーについては全然分からなかったので、先例があった(Splatoon での VC 環境について - モノトーンの伝説日記)AG03を買ってみた。
AG03のブロック図は下の記事のリンクにあるので、参考になるかもしれない。
http://www.dtmstation.com/archives/51931706.html

ヘッドセットはPCでFPSなどをやることを考えてサラウンド対応のものにした。
ステレオミニプラグで接続できることを確かめる。(USBのみのやつはダメ)

接続例

接続はこんな感じになる。
f:id:piroz95:20170614234845j:plain

背面でUSBケーブルがPCと繋がっている。
ヘッドセットは中央につなぐ。
ゲームからの音声は、ステレオミニプラグ→モノラル標準プラグ×2の変換ケーブルを使って上部2/3につなぐ。

自分の声を聞かないようにするために右下のMONITOR MUTEボタンを押す。

TO PCのスイッチはDRY CH 1-2Gにする。その他にするとゲーム音などの余計な音もPCに送られる。
この場合一番左のスライダーはマイク音量に関係しない。マイク音量の調整は中央左のツマミを使う。
(あとエフェクトをかけられなくなる)

一番下のツマミの左がゲーム音、真ん中がPCからの音、右が全体の音に対応する。

ゲーム音はAUXを通して入れてもOK。使うケーブルが違う。この場合ツマミでゲーム音を調整できないのでちょっとダサい。

2017-06-14

ACM-ICPC 2017 World Final 参加記

プロコン参加記 ICPC

バンコク大会で3位(サブリージョンで2位)で、World Final参加権を得ました。(バンコク行ってた時はFinal行けると思ってなかった)

東工大・チームpo(僕,yosupo,dnk,コーチhadrori)は5完で34位でした。
ちなみにペナルティ込みだと51位です。
応援・協力して頂いたみなさんありがとうございました。

本番のチームとしてのパフォーマンスはイマイチ目だったので悔しいです。

写真とかはここに多分あります。
icpcnews.com
トップの流れる画像4枚の一つにプラクティス中のチームの様子が映っててビックリ。

コンテスト

(覚えてる限り)

バンコクの時と同じくとりあえず3分割して並列に読むところからスタート。
僕はAから読み始めて、Aは幾何なのでパス、Bは超面倒系か？正確に読めなかったのでパス、Cは概要が簡単でまだ解けそう
Cの概要をよすぽに伝えて、解法を考えてもらった。
が、ここで箱を取るだけで移動できないと思いこんで伝えてしまう大失敗をした。

Cは最小流量制約付き最小費用流で解けるとよすぽに聞いたが、僕が組めないので実装をdnkにパス。
よすぽにスライド最小値覚えてますかって聞かれる→覚えてないのでパス

I問題の概要をよすぽに伝えて、僕は変換規則は単語だと思っていたんだけど、文字と言われてそうだねやるだけだねとなった。
Iを実装してAC。

順位表からFが簡単らしいので読んで概要をよすぽに伝えて、DP解法を貰った。
このときCかDのデバッグでパソコン空いてなかったので紙で実装を詰めるのと空いた時に書くのを往復して通した。

このあとはいろんな問題を読んで、B考えてこれはSATソルバーが無いと無理でしょｗとなって、Gの考察を始めた。
Gの考察中にCの誤読が判明した(絶望)
Cを読み直して正しい概要をよすぽに投げる。

Gはよすぽと相談しながら解いていった。ノートを塗って色々実験した。
サンプルが通ったあと、提出してRE。アサーションに引っかかってそうなのでランダムケースを食わせてみて実験。
気づいていないコーナーケース(これ→###)があって、修正。
それでも通らなくてよすぽにデバッグしてもらって修正、AC。

最後は詰まってるAのライブラリ写経ミスがないか調べたり祈ったりしてた。

反省

個人の部分では、要精進(毎回言ってる)を除くと、
C:思い込みで違う問題を伝えてしまったので最悪
I:ちゃんと読めてたら別に相談しなくてもよかった
F:これくらいの問題は相談しなくても解けるようにしたいかも？
G:これが通せたのは良かった

ラピッドシティと色々

サマータイム込みで日本との時差が-15時間。
日本→デンバーだと東回りで時間が巻き戻る。

日本と比べると緯度と標高が高くて、寒くて乾燥してた。

大統領の顔の彫刻があるラシュモア山で有名。
チームの顔をスキャンしてラシュモア山の彫刻っぽく3Dプリントしてくれたやつをもらえた。
f:id:piroz95:20170614232415j:plain
正直どれが誰かを判別するのは結構難しい。

Finalの前の日の夜にダウンタウンに出て肉を食べた。
f:id:piroz95:20170614232118j:plain
量が少なすぎるように見えるが、肉が超分厚くてこれでも7oz(200gくらい)。

これはラピッドシティからデンバーに帰る途中の機内から撮影したアメリカン農業
f:id:piroz95:20170614232508j:plain

英語

気を使ってくれないと厳しい。
ギリギリできたのがフロントに電話して歯ブラシと歯磨き粉をもらうレベル。
ラピッドシティからデンバーに飛ぶ前、搭乗ゲートで止められて早口で喋られて分からんって言ったら席を替えられた。
(非常口付近の席は非常時にコミュニケーションを取れる人が座る必要があるため)

今後

今年のICPCに参加するかは未定です

2017-03-21

RCO presents 日本橋ハーフマラソン参加記

プロコン参加記マラソン

ハーフマラソン（走らない）

予選

A19位,B9位で総合8位でした。

A:一箇所選んでそこからサイズ8にするのを繰り返す。選ぶ場所は大きい数を優先。サイズを大きくするのは隣接する最も大きい数を選んでいく。
— カードの更新 (@p_shiki37) 2017年3月4日

B:最も近い、到着時スコアが正になるエサを食べるのを繰り返す。ただしスコアが負になるエサは壁っぽく扱う。
— カードの更新 (@p_shiki37) 2017年3月4日

やったことが解説の想定とほぼ同じだった。
www.rco.recruit.co.jp

本戦

RCO presents 日本橋ハーフマラソン本戦 - RCO presents 日本橋ハーフマラソン本戦 | AtCoder

A45位,B39位で総合46位でした😇
めちゃくちゃ冷えてます

学生10位まで賞金出るって聞いたとき狙えると思ったんですが本戦全然ダメでしたね・・・
さすがに悔しかったので時間をかけて復習していましたが、本戦1位のmamekinさんのスコアが抜けません

A問題

本戦中

クエリあたりの効率が大事な気がしたので、来た客に対して何手で渡せるか求めようとした。
ここで幅優先探索でなぜかいい感じなると思って実装してしまった。
実際の所、いい客には沢山のタンクを使う必要があるので3手程度しか読めない探索では何も出来ない。これは本番後に気づいた。
ここに2時間半費やして、最終的に下から2番目の点数だったので大事故となった。

練習

まず、来た客にたいしてfillとsellだけで売れたら売る、売れないならskipという貪欲を書いた。
これだけで本戦のスコアの1.5倍が出た。(3.4M点)

その後、
・Dの低い客を無視して小さいタンクにchangeを繰り返す(5.0M点)
・客が来る前に大きいタンクにfillしておく(6.2M点)
でスコアが上がった。

今の手持ちで、Dが一定以上の客が来た場合の稼げる期待値のようなものをスコアにして、fillとchangeを使った1手先のスコアの期待値を最大化するようにしたら、点数が7.3M程度に激増した。
1手読みのような凝ったことをしている人はあまり居なくて、changeやfillのルールとしきい値をうまく調整すると同程度の得点が取れる模様。

B問題

本戦中

実際の道路を参考に一方通行とか交差点を駆使すればいけるんじゃないかと思い、一部のマスでは移動できる方向を制限するようなことを考えた。
Aで時間を食っていたこともあって、結局まともな実装ができずほとんど点が取れなかった。

練習

目的地に向かう動きとランダムに動く動きをうまく混ぜるといい感じになるらしい。

・できるだけ目的地に向かっていくが、停止するのを禁止する。
・同じ距離になる場合はランダムに向きを選ぶ
・行動順はランダムに決める
でかなりいい感じに動くことが分かった。

終盤になったら停止を許可してできるだけ近づくといい感じになる。(6.7K点)

ここで引っかかって抜けられなくなってるやつがまだ残ってるので、5ターン中2ターンランダムに動かすと点数が伸びた。(388K点)

それでもまだ引っかかってるやつが残るので、これをスコアを下げずにいい感じにしたかったが面倒そうなので諦めた。

他の方針として、片側に詰めて並べていって最後にバッと戻す方針というのもあって、それも実装してみた。(497K点)

市松模様に並べて動かしていくという方針もあるが、これはめちゃくちゃ難しそう。

最後の方ビームサーチとか取り入れるともうちょっと落とせそう？ 42663点 / 172手 pic.twitter.com/K7yhZYzECz
— koyumeishi (@koyumeishi_) 2017年3月21日

この問題の設定、見覚えがあると思って調べた所、Asymmetric Simple Exclusion Processと呼ばれているらしい。

反省や感想

今回は最初に間違った方針で、しかも重い実装に取り掛かってしまったので取り返しのつかないことになった。
まず最初に貪欲を考えるという方針が良いような気がする。
しかし、CODE RUNNERの2回目の予選A(交わらないように直線を引くやつ)のように、貪欲よりも頭の良い解法が圧倒的に良い場合もあるのでそのあたりは難しいなあと思った。
短時間マラソンでは、自信のない重い実装はやめたほうがよさそう。

その他：
・東京駅から徒歩2分、乗り継ぎもなかったのでめちゃくちゃ楽だった
・企業紹介と文章要約アルゴリズムについてのスライド？はどちらも面白かった。（途中で置いていかれた）
・懇親会は主にピザ🍕とフライドチキン🍗

2016-12-21

2-SATを探索で解く方法とyukicoder No.470 Inverse S+T Problem

問題解説

2-SATを想定解とする問題をyukicoderで出題しました。
No.470 Inverse S+T Problem - yukicoder

想定解通りの2-SAT解法とは別に、計算量のよく分からない探索を結構通されてしまいました。
探索解の中に正当なものがあるのか、調べていたところ2-SATを暗黙的に解いている提出が見つかりました。
たとえばヘクトさんの提出です。

その解き方というのが、Wikipediaの2-SATの解法の一つとして載っているLimited backtrakingです。
2-satisfiability - Wikipedia
http://epubs.siam.org/doi/abs/10.1137/0205048

例を用いて大雑把に説明します。
$(\lnot x_1 \lor x_2) \land (\lnot x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_5) \land (x_1 \lor x_3) \land (\lnot x_3 \lor x_4) \land (x_5 \lor x_6)$
が充足可能か調べましょう。

真であると分かったリテラルの集合を $T$ で表します。
まず適当な変数を選び( $x_1$ とします)真だと仮定します。( $T = \{ x_1 \}$ )
$\lnot x_1$ は偽になるので、このリテラルを含む節では、もう片方が真になる必要があります。
1つめの節から $T$ に $x_2$ を加えます。
2つめの節から $T$ に $\lnot x_2$ を加えます。
ここで $T = \{ x_1, x_2, \lnot x_2 \}$ となり、矛盾が見つかりました。

今度は $x_1$ が偽だと仮定します。( $T = \{ \lnot x_1 \}$ )
$x_1$ を含む節に注目します。
4つめの節から $T$ に $x_3$ を加えます。
$x_1$ を含む節は1つだけです。新たに $T$ に加わった $x_3$ に対して、 $\lnot x_3$ を含み、真であることが確定していない節に注目します。
5つめの節から $T$ に $x_4$ を加えます。
これで( $T = \{ \lnot x_1, x_3, x_4\}$ )になりました。これ以上 $T$ に追加することもできませんし、矛盾もみつかりませんでした。

$T$ に含まれているリテラルを含むような節は、残りの変数の値によらず真になります。
そうでない節は、 $T$ に出てくる変数を含みません。この例では、 $(x_5 \lor x_6)$ が余っています。

残った小さな問題についてこの手続を繰り返していきます。最終的に節が無くなれば残りの変数は適当に決めてよいです。
もし部分的な式が充足不能ならば全体も充足不能ですし、部分的な式が充足可能ならばいままでに確定した真偽の割り当てと合わせて全体が充足可能です。

ある程度無駄を省けば計算量は $O(nc)$ になると思います(nが変数の数,cが節の数)。
このアプローチでも工夫すると線形時間で解けるらしいです。

2016-12-19

ARC066/ABC050 D: Xor Sum - OEISからの解法

問題解説

コンテスト中に解けませんでした。

問題

D: Xor Sum - AtCoder Regular Contest 066 | AtCoder

解法

小さい $N$ に対して実験してOEISで検索します。
2,4,5,8,10,13,14,18,21,26,28,33,36,40,41 - OEIS

A007729が答えになりそうですが、残念ながらいい感じに求める式は見つかりません。
しかし、この数列はA002487の部分和で表されることが分かります。

A002487の一般項は次にように表せます。
$\begin{eqnarray} s(n) = \begin{cases} n & (0 \leq n \leq 1) \\ s(n/2) & (n \geq 2, nが偶数) \\ s((n-1)/2) + s((n+1)/2) & (n \geq 2, nが奇数) \\ \end{cases} \end{eqnarray}$

これの部分和 $f(n)=\sum_{i=0}^n s(i)$ を頑張って式変形します。

$n \geq 3$ のとき、
$s(0)=0$ であることを用いて、
$\begin{eqnarray} f(n) & = & \sum_{i=0}^n s(i) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(2i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} s(2i+1) \\ & = & s(0) + s(1) + \sum_{i=1}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} \{s(i) + s(i+1)\} \\ & = & \sum_{i=0}^{\lfloor n/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} s(i) + \sum_{i=0}^{\lfloor (n-1)/2 \rfloor +1} s(i) \\ & = & f(\lfloor n / 2 \rfloor) + f(\lfloor (n-1) / 2 \rfloor) + f(\lfloor (n+1) / 2 \rfloor) \end{eqnarray}$

これであとはメモ化再帰で $f(N+1)$ を出力すると解けます。

ソースコード

import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		System.out.println(f(n+1));
	}
	static HashMap<Long, Long> hm = new HashMap<>();
	public static long f(long n) {
		Long memo = hm.get(n);
		if (memo != null) return memo;
		if (n <= 2) {
			return n;
		}
		long res = f(n/2) + f((n-1)/2) + f((n+1)/2);
		res %= MOD;
		hm.put(n, res);
		return res;
	}
}

計算量

メモ化再帰の遷移に注目すると、三つ又に分かれているように見えます。
$n$ を $2$ で割っていっているのでいつかは $n$ が小さい値になることは分かりますが、途中で状態数が爆発しないのでしょうか？
実はこの遷移では大丈夫です。

ある呼び出しの深さにおいて、引数 $n$ の取りうる値が $x$ 以上 $x+a$ 未満だったとします。
次の深さにおいて、引数 $n$ の取りうる値は $\lfloor (x-1)/2 \rfloor$ 以上 $\lfloor (x+a+1)/2 \rfloor$ 未満になります。
この幅はfloorを無視して $(a+2)/2$ 程度になるので、引数の取り得る値の幅は結局定数になります。

したがって計算量は再帰の深さと同じ $O(\log N)$ です。
再帰の形が $f((n+a)/b)$ (ただし $b(>1),a$ は定数)の形の時は安心してよさそうです。