IOI2017

IOI2017を観戦しました。

師匠が圧倒的な1位を取り、日本チーム自体も金3銀1と過去最高成績で激アツでした。
金3も1,4,5位で凄すぎる。
おめでとう&お疲れ様!



本番から1時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か気になった問題を解いてみました。
今年の問題は、解いていない問題も含めてなかなか面白く、また、かなり難しめのセットだったと思います。解いた問題についての解説を書いたのでブログとして貼っておきます。

  • Day1 Nowrus 96.31点
    • 久々のOutputOnlyでした。とりあえずで書いてみた解法で高得点を取れたため、順位を大きく分けるというよりはタイブレイクとして機能していたのではないかと思います。ちゃんと焼きなましなどをすれば100点も可能なのかもしれません。
  • Day1 Toy Train 満点
    • 一見NP困難にしか見えないんですが、仮定をおいたりして考えて行くと多項式で解くことができ、ほえーってなった。ゲーム系なんですが、なかなか独特かつシンプルなルールで面白い。
    • yosupo氏の解法もどうぞ。こうやるとたしかに典型だけで片付けられるなぁ、不思議。
  • Day2 Books 満点
    • ありがちでシンプルな設定なんですが、なかなかにadhocで面白かった。それっぽいことをすれば50点来てしまうのですが、そこからは適当にやるだけでは満点は取れません。冷静にじっくり考察する力が試される良問。解法も面白いので結構好き。

KMPのK

snuke.hatenablog.com

上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。
KMPは、上の記事で紹介したMP(Morris-Pratt)にKnuthパワーが加わったものです。
さらなる考察がされて、文字列検索の効率が向上した感じです。
計算量的な面でも、全体計算量は線形のままですが、後述するような嬉しい点があります。

復習+α

まずはMPの復習からです。
上の記事で求めている A は 最長border と呼ばれるものらしいです。
文字列 S "aabaabaa" の A(border) は -1,0,1,0,1,2,3,4,5 となります。
この文字列の末尾にもう1文字加えたとき、A[9] はどう計算すればいいでしょうか?
f:id:snuke:20170712160204p:plain
図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。

  1. 赤い矢印を辿って、次の文字を見る。
  2. ? と一致していたらそこの次の位置が A[9] になる。
  3. 異なるなら、また赤い矢印を辿って・・・を続ける。

? が a,b,c のときについてそれぞれ実際にシミュレートしてみるとイメージが湧きやすいかもしれません。

さて、ここまでがMPですが、MPの計算量は均し計算量でO(N)です。
つまり、1ステップの計算量は最悪でO(N)になることもあります。
例えば、aaa...aaab について計算する時、b を追加したときには赤い矢印を a の個数回辿らなければなりません。

KMP

下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤い矢印を辿った場所」に張られたものです。
f:id:snuke:20170712155859p:plain
実は先程の A[9] を求めるステップでは、青い矢印を赤い矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。

実はこれで1ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。
「赤矢印を辿る」+「次の"次の文字"が異なる赤矢印までスキップする」というのを1ブロックとして考えます。
1ブロック進むごとに残りの長さが半分以下になっていくことを示せば、O(log N)になることが示せそうですね。

  • 「赤矢印を辿る」で半分以上進む場合:言うまでも半分以下になります。
  • 「赤矢印を辿る」で半分以上進まない場合:「次の〜スキップする」の方で半分以下まで減ることを示します。

f:id:snuke:20170717195852p:plain
図の緑と赤は文字を、青と紫は文字列を表します。
右端の赤矢印の長さを w とします。
図の文字列は周期が w であるため、次の赤矢印でもちょうど w 進みます。(w 進めることは明らかで、w 未満進むとすると前の赤矢印でもその分進めたはずなのでおかしい)
すると、進んだ先の"次の文字"も同じ文字(緑)なはずなのでスキップされるはずです。
で、次の赤矢印も w 進むはずで、スキップされて・・・というのが残りが w 未満になるまで続きます。
w が残りの長さの半分未満であったことを考えると、この場合でも1ブロック進むごとに残りの長さが半分以下になることが分かります。
以上、O(log N) の証明でした。

ちなみに Θ(log N) でもあることは "abacabadabacabae...." みたいな文字列を考えるとわかります。
文字種が2種類でも "0100010101000100" みたいな文字列(ace...が0でbd...が1)を考えると log N が作れます。
実装等はこの記事を参考にするといいでしょう。ここも良さそう。

応用問題

xmas contest 2015 D - Destroy the Duplicated Poem
問題概要を一口で説明すると「Trie木が与えられるので各頂点に対して赤矢印を求めよ」です。
普通にMPをやろうとすると、aaa...aaときてそのあとにbやらcやらと枝分かれしまくるケースとかで計算量が2乗に爆発してしまいます。
そこで、KMPを使えば遷移が常にO(log N)で抑えられてしまいます。やったー。
ソースコード
木上でやるとなると少し実装がトリッキーになるので頑張って混乱しないように整理して実装しましょう。
ちなみに想定解は違う解法だったので、期せずしてKMPの良い例題を作ってしまったらしい。

丸くなってしまったtwitterアイコンを戻す方法

なんか、twitterとtweetdeckのアイコンが突然丸くなった。
四角を想定して作られたアイコンの四隅が切り取られるのはアレなので、CSSをいじって直した。
twitter社はなにを思ってこんなことをしてしまったんだろう・・・?

直し方

まず、CSSをカスタマイズできるブラウザ拡張を入れます。

User CSSの使い方はここを参考にするといいでしょう。


次に、以下のCSStwitter.comに適用します。

.ProfileAvatar, .ProfileAvatar-image, .avatar, .js-action-profile-avatar {
    border-radius: 5% !important;
}

角丸の度合いを変えたかったら5%のところをいじって下さい。

Google Code Jam 2017 Round 3

通過しました。
初のGCJ決勝進出です。
GCJは現時点での第一目標だったのでとても嬉しい。
次はTCOかぁ、きっつい。

今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。
(けど謎の問題(sortアルゴリズムを推測せよとか、乱択とか)とか強実装とかが出てくると多分苦手)

戦略的にも最適に動けていたので、かなり理想的なパフォーマンスだった。
流れとしては、

  • SubmissionsとTop Scoresはちらちら動いて邪魔だし、焦りの原因になるので閉じておいて必要な時だけ見る
  • とりあえずAは解いておく
    • 逆向きに探索できるなぁとなる
    • 状態数を減らしたい
    • 前の状態が存在する条件=合計がL以下
      • そういう状態は18C9しかなくて余裕
    • 前の状態が存在しないのは探索せずに数式で計算する
      • L!から種類iがCi個ある時にCi!で割っていけば良くて、解けた
    • small時点で24位だった
    • largeはとりあえず保留するスタイル
      • 最大ケースが明らかに100000000で、これが爆速だったので通るだろと思う
  • とりあえずBも読んで少し考える
    • サンプルを見ながらサイクルにそって加算する感じだと思う
      • なんで負が出てくるのという違和感はあった
    • 他のサンプルを見るとサイクル(有向)がないのにOKな例がある
    • ある辺にx流すのと、逆辺に-xを流すのは同じだという考察
    • 無向グラフで考えた方が良さそう
    • サイクル基底っぽい
    • DFS木を書くと分かった
      • 後退辺に1を割り当てて、対応する木の区間(?)にも+1してやればいい
    • 非連結なケースを忘れたのと修正ミスで2WA
      • 出力をもうちょっとちゃんと確認すれば少なくとも2つ目は防げたし、これが今回唯一の反省点
    • largeは保留
  • Bをさらっと解けて有利になったという実感があったので順位表を見てFinishまでの道のりを確認する
  • D smallが簡単らしい
  • C smallもまぁまぁ解かれてる
  • とりあえずDを読んでlargeは捨てるのが正しそうだと思いつつsmallを解く
    • FAが11分台だったので実装も大したことないはずと考える
    • 小さいやつから伝播させていく感じの貪欲でいけそうとなる
      • 小さい数から見ていけば下限制約は保証できるので、うん正しそうという感じ
    • 通る、調子が良い
  • C-smallをやる前にlargeたちを送っておくかを考える
    • C-smallは必要そうな気配を感じるし、少なくともC問題文読んでからにするかとなる
    • もしlarge提出でトラブルが起きたら焦ってCの問題文長めだしテンパって読めなくなるのが想像できるし
    • C-smallやるだけ感があったのでやる、通る
  • この時点で通過をほぼ確信したので、largeたちをドキドキしながら出す。
  • のんびりC-largeでも考えるかーとなる(実際にはこれが解けないと通過できなかった)
    • 有向グラフのオイラー路なので、頂点ごとに独立にやっても勝手にオイラー路になるやろと思う
    • すぐできるし余裕もあるからと、とりあえず実装してみたけどsmallと合わない
    • 連結性が崩れる場合があることに気づく(他にもバグがあった(おい))
    • MSTで解けるなぁ、なんだこの絶妙な問題はとなる
    • 合わない
    • 始点を特別処理しないと行けないことに気づく
    • 提出(C-largeちょっと気が緩みすぎ感はあったか)
  • お祈りフェイズ。Dはさすがに無理だし、暇
  • ペナルティ差で準急に微妙に負けていた(◞‸◟)
  • 仕方ないからD-largeを綺麗に実装できないか考える
    • ボロノイ図みたいになるのはすぐ分かった
    • bounderyが8種類の直線で表せてそのandを取った領域内の値を頑張って計算したい
    • 始点から距離を1ずつ増やしていって距離が同じマスたちを一括で足す感じをイメージする
    • bounderyに引っかかると、増えなくなる方向が出てくる
    • 右下、右上、左下、左上と真上、真下、真右、真左の8種類の領域に分けてみると、bounderyにぶつかった時に増えなくなる分が割と簡単に求まることが分かる
    • 有限時間で実装できる気にはなったから実装を始めたけどさすがに間に合わない
      • (追記)後で気づきましたが、領域凸にならない場合あるやん!(sample1とか)これは実装不能ですね。
  • 終了、全部通って12位通過、めっちゃ嬉しい

GCJはいかに冷静に解くべき問題を取捨選択するかが重要で、これさえ間違えなければ解けるべき問題さえ解ければ割と通れる。
昔の自分だったら絶対やってないんですが、素早く書けそうなC/Dのsmallをさっさと回収するとだいぶ心に余裕が生まれたりもするので重要な気がする。
ストレステストにも使えるし、ベースの解法の確認ができることもあるし、無駄ってことはないと思うし。
GCJの戦略とかはりんごさんのツイートを見ると参考になると思います。
例えばこれとか。

おまけ:コンテスト前の準備
昼ごはんはで贅沢に天ざるうどんを食べた。
くっそうまかった。やっぱりこの店最高すぎる。(ちょっと遠いけど)(大体並んでるけど)
2014の問題を解いてたら眠くなったので仮眠を取った。
晩飯はがっつり食べずに、プリンとメロンパンと高千穂コーヒー牛乳で済ます。
念のため栄養ドリンクを買ったけど飲まなかった。
コンテスト前にプリンを食べるのはおすすめです。

最小費用流の負辺除去

つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。
この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。

最小費用流への認識

最小費用流を最大流みたいに「始点 S から終点 T に水を流す」という問題だと思っていたならそれは本質から少しずれています。(定義上は多分それで合ってると思いますが)
水の例えを用いつつより本質を付いた言い方をするならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。
つまり始点も終点も複数存在するという形がより本質に近いということです。
もっと言うと、始点と終点の区別もそんなにはっきりさせない方がいいでしょう。

もう少し具体的に変数を交えて書くとこんな感じです。

  • 有向グラフがある
  • 最初、頂点には余っている水の量 d_v が定まっている
    • d_v が負なら不足していることを表している
    • 全体でみると過不足はない ( \sum d_v = 0 )
  • 辺には容量 cap_e とコスト cost_e が定まっている
  • u \to v を使うと、u から v に水を移すことができる
    • 移す量を x とすると、0 \leq x \leq cap_e を満たさなければならず、コストは x \cdot cost_e 掛かる
  • 過不足を解消するための最小コストは?

最初から過不足がない場合は最小費用循環流問題ってやつになります。
負辺がある場合、わざわざサイクルに水を流してコストを減らすこともある点に注意。

負辺除去

本題です。
負辺がある場合は、最初に逆向きに流しておいて、コストが正の逆向きの辺があったとみなすだけで良いです。
負辺 u \to v が来たときに具体的にやる操作を書くと、こんな感じです。

  • d_u から cap_e を引き、d_vcap_e を足す
  • 答えに cost_e \cdot cap_e を足しておく
  • 容量 cap_e コスト -cost_e の辺 v→u を追加する

かなり自然じゃない?

実装

蟻本方式の実装でやるなら、超頂点 S', T' を用意して、

  • d_v が正:S' から v へ容量 d_v コスト 0 の辺を張る
  • d_v が負:v から T' へ容量 -d_v コスト 0 の辺を張る

で正の d_v の和だけ流せば良いです。
実装をいじれば超頂点を作らなくてもできると思います。
あと、cost scalingってやつもおすすめらしいのでそのうち書くかも。(流量が大きくなりがちなこの手法と相性が良さそう)

おまけ

上の定式化そのままではないケースへの対処法あれこれ

  • SからTに流すんだけど流量が自由な場合
    • T→Sに容量INFコスト0の辺を張るだけ
  • SからTに流すんだけど流せるだけ流さないといけない場合
    • T→Sに容量INFコスト-INFの辺を張っておいて後で答えからこの辺のコストを引く
  • 最小流量付きの辺がある場合
    • 負辺除去と同じノリであらかじめ最小流量だけ流しておけば良い

補足

負辺除去には他の方法もあるので、それらを比較したwata先生のツイートを引用させていただきます。(ありがとうございます)

  • Bellman-Fordでポテンシャル初期化(負の閉路無し) O(F m log n + nm).
  • 適当に定数足して非負に (大きさFの最大重み二部マッチングなど) O(F m log n).
  • 逆向きに流して負辺除去 O((F+F') m log n), F'は負の辺の容量の和.

ちなみにこれらは3つとも蟻本に載っています。
シチュエーションに合わせて別の手法を選んだ方が良いこともあるかもしれません。
(特に2つ目は実装楽だし早いしよく出てくるし便利)

ARC075 F 「Mirrored」 速い解法

ARC075F

とりあえず桁数を1~18まで全部試します。
例えば6桁なら、

D
= fedcba - abcdef
= 99999*(f-a)
  +9990*(e-b)
  + 900*(d-c)

となるようなa~f(0≦a~f≦9, a≠0)の個数を数えれば良いです。
(f-a),(e-b),(d-c)みたいに端から決めていくんですが、
解説ではDとの差を縮めていくようなものを探索していますが、
下の位のmodに注目すると、実は(f-a),(e-b),(d-c)の組み合わせは一意に決めていけることが分かります。
例えば(f-a)を決める時は、99999*(f-a)%10 == D%10 とならないといけなくて、「0≦abs(f-a)≦9」と「999999*2>(9990+900)*9(つまり2ずれると収拾がつかなくなる)」に注意するとそういう(f-a)は一意に定まります。
(e-b)を決める時は (9990*abs(e-b)%100 == abs(D-99999*(f-a))%100) みたいな感じでどんどんやっていきます。符号はどっちかだけが正しいです。
計算量は O(log^2 D) とかです。

ソースコード

ICPCのライブラリPDFの生成

ICPCのWFまたは多くのアジア地区予選では持ち込めるライブラリのページ数が決まっています。
また、PDFの右上にページ番号、左上に大学名を入れろという指定がついてきます。

PDF化するコマンド

sublimeに印刷機能がなかったし、ページ番号と大学名を入れる方法も分からなかったので調べたらenscriptっていうコマンドがあるらしい。
なければbrewとかでインストールすれば使える。
enscriptではpost scriptのファイルが吐かれるので、pstopdfコマンドを使うとPDFに出来る。

ライブラリをlibrary.cppっていう1つのファイルにまとめておけば、下みたいな感じでうまいことPDFに出来ます。

enscript --highlight=cpp --line-numbers --color --header='HOGE University (team: HOGE)                                                                                      Page $% of $=' --landscape -2 -o library.ps library.cpp
pstopdf library.ps

1つのファイルに纏める方法ですが、以下のpythonスクリプトを走らせたりすればいいです。

import os

for f in os.listdir("."):
  if f == "library.cpp":
    continue
  if ".cpp" not in f:
    continue
  print("#"*50)
  l = (50-len(f)-2)//2
  r = (50-len(f)-2)-l
  print("#"*l+" "+f+" "+"#"*r)
  print("#"*50)
  print("")
  with open(f) as f:
    print(f.read())
  print("")

ページ番号とかを挿入できるツール

すでにPDFがあって、ページ番号とかを挿入したいって場合はこのサイトを使えば良さそう。
カスタム設定とかを使えば左上に大学名っていう指定も出来そう。
オンライン操作でPDFファイルにページ番号を追加www.ilovepdf.com