丸くなってしまった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

ARC070 F「HonestOrUnkind」別解

HonestOrUnkind解いた。
面白かった、と思ってたけど想定解と違ったのでメモ。
想定解の方がシンプルで頭良い。

正直者を1人特定するところが違った。

まず人の組をN/2組作る。Nが奇数なら1人余る。
各組(x,y)について? x yを質問する。
'N'なら正嘘、嘘正、嘘嘘のどれか。(消費される人数は正≦嘘)
'Y'なら正正、嘘正、嘘嘘のどれか。(yを嘘にするためには嘘を2人消費する)
'Y'だった組のyを全部取り出した集合をTとする。
元々のN人では正>嘘である点に注意すると、

  • Nが偶数:Tの中でも正>嘘になる
  • Nが奇数:Tの中では正≧嘘になる

奇数のときも正>嘘にできれば、再帰的にやることにより高々2(N/2)=N回の質問で正直者を1人見つけられる。
奇数のときは「Tのサイズが偶数なら余っていた1人をTに追加する」とすることにより、正>嘘にできる。
いちおう証明↓
Tのサイズが奇数の場合:偶奇の性質上、正=嘘は成り立たないので正>嘘
余りが正だった場合:元が正≧嘘なんだから正を足せば正>嘘になる
余りが嘘だった場合:Nが偶数だった場合を思い出すと、正>嘘になっていてつまり正が嘘より2人以上多いので、嘘を1人足しても正>嘘
どのケースでも正>嘘になっていることが分かる。

AGC013F「Two Faced Cards」別解(TLE)

Two Faced Cardsのコンテスト中に書いてた別解です。
O(N√N logN) なのでTLEして悲しいけど紹介しておきます。
(想定解も理解したけどadhocで面白かった)

下ごしらえ

とりあえずC(とA,B)を0~Nに変換しておきます。
Ai<Biのカードは裏で使うメリットがないのでBi=Aiとしておきます。
これでBi≦Aiが保証できます。
ここで、Bi>Nのカードがあるとimpossibleです。
Ai>Nのカードは後々面倒なので、Ai=Biとして後で答えから-1します。

f:id:snuke:20170417220211j:plain
入力例2の図示

クエリが1個

クエリが1個のときは以下のような貪欲法で解けます。

貪欲法

Ci=0のカードから順に相方を決めていきます。
相方は、以下のようなmultiset<int> Sを使って決めます。

  • Ci=xのカードを見ている時、Bi=xのカードがあればSにAiを追加する
  • Ci=xのカードを見ている時、Sに入っているxを全てINFに置き換える
  • Sに入ってる数のうちの最大値を、今見ているカードの相方として取り出す

表として取れるものがあればそれを取り、なければ表も取れるようになるのが最も遅いものを取るというイメージです。
途中でSが空なのに取り出そうとしたら失敗です。

クエリ複数

次に、クエリが複数ある場合に発展させます。

dp[k]=「Ci=kのカードには相方が要らないときの答え」というのをk=0~Nについて全て前計算しておけば、各クエリに高速に答えることができます。
dp[k]の値はどうなっているでしょうか。

まず、k=Nのときに上のような貪欲法を行うと、どこかの時点で(少なくともk=Nでは)失敗します。
失敗したiをtとすると、k>tは全て-1です。
k=tについてはCi=tのカードをスキップしてそのまま貪欲法を続けて答えdp[t]を求めます。

あとはk<tの場合です。
あるkについて、上の貪欲法でSから取り出した値がINFだった場合は、kをスキップしてもk+1をスキップしても答えは変わらないのでdp[k]=dp[k+1]です。(どっちにしろどうせINFを取るだけで、Sの他の部分は変わらないため)
Sから取り出した値がx(≠INF)だった場合はどうでしょうか?
xを取る代わりにスキップをして貪欲法を続けたときにxが取られるようなiをpとします。
pは必ずx以下になります。(i=xになるとxがINFに変化し、S内の最大値になるため)
このとき、kをスキップした時のSの状況はpをスキップした時とほぼ同じです。異なるのはxが取られるタイミングだけです。
したがって、p<xのときはdp[k]=dp[p]、s=xのときはdp[k]=dp[p]+1となります。

pを全てのkについて求めておけば後ろからdpテーブルを埋めていくことができます。

ーーここまでが本質ーー

データ構造パート

pはどうやって求めればいいでしょうか?
xが取られるよりも先に取られうるものというのは以下の2通りです。(kの時点ではINFはSに入っていない点に注意)

  • Sにまだ残っているもの(値をyとすると、k=yでINFに変わって取れるようになる。y<xが成り立つ点に注意)
  • aiがx以上のもの(bi以降なら取れる)

starry sky tree(区間加算と区間minができるsegtree)を用意します。このsegtreeでは「ある区間内で値がhoge以下のものが初めて現れる場所」をO(log N)で求めることもできます。
上記の2通りについて[取れるようになるi, N+1)に+1をしておきます。
さらに、i=0~Nについて[i,N+1)に-1をしておきます。
kの値をvとすると、[k,x)のうちv-1以下の値が初めて現れる場所がpです。(なければp=x)

上の2通りの+1を適切な順で追加したり消したりしながらpを全部求めていきたいのですが、残念ながらMoをするしかないです。
ただ、普通にMoをすると右端を1つずらしたときに増えるものが多かったり少なかったりして壊れるので、右端を「何番目に小さいbiであるか」を基準として√N個ずつのブロックに分けます。しかし、それだけだとbiが全くないゾーンが広過ぎになってしまうことがあるので、biの集合に0~N追加した集合での何番目かを基準にするなどしなければいけません。
左端については1つずらしたときには高々1つしか増減しないのでOKです。

まとめ

というわけで最後の方わりと雑でしたが、O(N√N logN)になりました。
こんな感じで6ケースだけTLEしましたΩ\ζ°)