コードを短く書く人のブログ

コードゴルフを稀に取り上げるブログ

Wiener's Attack を実装した

はてなTeX記法が辛いのでhackmdの方見てください.
link

二重辺連結成分分解

ゆらふなさんの記事を見て実装してみようと思ったので記事を書きました。
この記事ではlowlinkを使った方法でやっています。

定義

  • 橋 (Bridge): その一つの辺を取り除くとグラフが非連結になるような辺
  • 二重辺連結成分 (Biedge Connected Component ?): 橋を含まないような頂点集合

内容

二重辺連結成分は橋を含まないような頂点集合なので橋を列挙することで二重辺連結成分分解ができることがわかる。
橋の検出、列挙に関しては次のpdfがわかりやすい。グラフ探索アルゴリズムとその応用
基本的には深さ優先探索をするだけで求まる。まずグラフに対して適当な頂点を決めそこから深さ優先探索を行う。

$ord[v]:$ 深さ優先探索でその頂点を何番目に訪れたか
$low[v]:$ 後退辺を一度だけ使ってたどり着ける$ord$の最小値 $(lowlink)$

とすると深さ優先探索木上の辺$uv$が橋であるかの判定は
$$ord[u] < low[v]$$ で行える。$ord$は深さ優先探索木の根方向に行けば行くほど小さくなるので$u$の子である$v$は$ord[u]<ord[v]$を満たす。
$ord[u] >= low[v]$の場合は$u$より根方向に後退辺を用いて移動できるので$u$より根方向の場合は$u$に到達できるので
$uv$が橋でないことがわかる。逆に$ord[u]<low[v]$の場合は$v$から$u$より根方向に到達できないので橋であることがわかる。
一度の深さ優先探索で橋を列挙することができるので計算量は$O(n + m)$になる。

橋を列挙できれば橋の端点から橋となる辺を使わないように深さ優先探索で二重辺連結成分を列挙できる。
ただ橋が存在しない場合は適当な頂点から深さ優先探索すると良い。
全体の計算量は$O(n + m)$になる。

実装は以下のようになった。

二重辺連結成分分解

verifyにはARC039Dを用いた。submission

ARC039D

ICPC国内予選2016参加記

6/24(金)にあったICPC国内予選2016にICT48(@orisano,@ringoh72,@DeEn_queue)として出場しました。
結果は4完32位と去年より順位は下がってしまいとても悲しかったです。

大会前日

前日に今年用のライブラリを作ってないことに気が付き、去年のライブラリをベースに作成。
いろいろやってたら5時。1限もあるし寝れない。このまま挑むしかない。

大会当日

1限が終了してそのまま学校で就寝。3時間ほど寝てから今回国内予選初参加の
@ringoh72と@DeEn_queueの提出練習とプリンタのテストをして待機してました。

問題

A:全探索
僕がスピードのみを重視して O(n2) のコードを書いてAC。

B:問題を知らず
僕がC,Dを見ているうちに@ringoh72がサンプル合わないと言っていた。
C,Dの解法を考えているうちにACしていた。

C:篩っぽいことをする、最大ケースが与えられていなければ辛そう
@DeEn_queueが解法を考えてくれていたがブランクが長かったからなのか実装に悩んでいたので
僕が代わりにコードを書いてAC。

D:区間DP
僕が担当していて舐めプしてたら結構いろんなミスが見つかって辛かった。
解法自体は制約と見た感じからすぐわかったのだけどうまく実装できず。
そこそこ時間はかかったもののAC。

E:誤読
最初みて幾何かなと思い後回しにする。ちゃんと読むべきだった。
ちゃんと読んでも問題の意味を変に解釈してしまった。 おそらく一番時間を費やすべき問題だったと思うし反省。

F:外側から連結成分取り出して木を作って同型性判定
3人で考えてやるべきことはわかったのだが、「同型性判定ライブラリないからできない><」とか
甘えたことを言ってしまい断念。少し考えれば思いつきそうだし取り組むべきだった。

G:誤読
3人ともワープ場は飛行機の線路上に限らず任意の地点に置くことができると勘違いしてしまって断念。
clarができなくてはじめて困ってしまった。

H:わからず
フローのオーラを感じたが経験と知識不足から断念。

まとめ

二人とチームを組んで競プロするのは初めてだったので役割とかその辺がよくわからなかった。
チームで練習すべきだったなと痛感しました。そもそもチームが締め切り当日まで決まってなかったのがやばい。
アジア地区行けるといいな(3年連続になるといいな)

Git Challengeに参加してきました

3/5に開催されたmixiさん主催のgit challengeというイベントに参加してきました。

参加したきっかけ

@imishinist(たいさん)から「参加しないのですか???????」と煽られたのもありますが、
gitは頻繁に使うものの全然使いこなせてない感があり、そろそろスキルアップしたと思っていた矢先だったというのが大きいです。

感想

twitterで知っていた@KAGE_MIKUくんとチームで競技に取り組みました。
@KAGE_MIKUが話しやすい人でわからないところは聞くことができたし、shell芸っぽいところでは手伝うこともできたかなと思います。
結果として4位になり、嬉しさと悔しさがありました。
採点にトラブルがありHumanCIになっていたのが少し残念でしたが、それでもとても楽しめました。

競技終了後に解説があるのがとても良く、こんなコマンドあったんだ、こうやって解決するのか、などの気付きがありました。

こんな面白いイベントを開催してくれたmixiさんに感謝しかないです!
是非後輩たちは参加してみてください!!!!!!!!!!!!!!!!

学校とか部活とかでgit challengeのような取り組みをしてみるとgitの布教に使える気がするし作ってみたい感がある。

AOJ 0568 Pasta

AOJ0568Erlangで解いてみたのでBlogを書きます。
問題の概要については省略します。

前回と同様に JOI 2011-2012 予選 問題・採点用入力 から正答することを確認しています。

-module(aoj0568).
-export([main/0]).

main() ->
  {N, K} = get_pair(),
  Fixed = lists:reverse(lists:sort([get_pair() || _ <- lists:seq(1, K)])),
  io:format("~p~n", [pasta(N + 1, Fixed, {0, -1, -2})]),
  init:stop().

to_i(S) ->
  {I, _} = string:to_integer(S),
  I.

get_pair() ->
  [First, Second] = [to_i(V) || V <- string:tokens(io:get_line(""), " ")],
  {First, Second}.

pasta(N, [{N, P}|_], {Q, _, _}) when P /= Q -> 0;
pasta(N, [{N, P}|T], S={P, _, _}) -> pasta(N, T, S);
pasta(_, _, {P, P, P}) -> 0;
pasta(1, _, _) -> 1;
pasta(N, L, S={P, Q, _}) ->
  case get({N, S}) of
    undefined ->
      Ret = lists:foldl(fun(X, Acc) ->
                            Acc + pasta(N - 1, L, {X, P, Q})
                        end, 0, lists:seq(1, 3)) rem 10000,
      put({N, S}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

入力を受け取って、逆順にソートします。
逆順にソートする理由は引数を減らせるというだけの理由です。
基本的には全探索でパターンマッチにより遷移できない状態排除しています。
本来であれば過去2日分の情報を持つだけで遷移先を決定できるのですが、
過去3日分の情報を持つことでパターンマッチを容易にしています。
遷移する際に過去の情報をスライドさせるだけで良いのでとてもシンプルになります。

終わりに

やっぱりErlangだとプロセス辞書を使ってメモ化再帰が楽に綺麗にかけるので好きです。

AOJ 0595 Schedule

何を今更と思う方もいると思いますが、AOJ0595Erlangで解いた(未確認)ので記事を書くことにしました。

追記(4:35) JOI 2013-2014 予選 問題文・採点用入出力・解説の入出力例に対してすべて正解していました。

Erlangを書くのが非常に久しぶりだったのですがとても楽しくかけました。

問題概要に関してはAOJを見てください。

以下コードです。ぶっちゃけ普段からErlangを書かないのでErlangとして良いコードかはわかりません。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, true, false, false)]),
  init:stop().

schedule(S, J, O, I) ->
  (
   schedule(S, true, true, true, J, O, I) +
   schedule(S, true, true, false, J, O, I) +
   schedule(S, true, false, true, J, O, I) +
   schedule(S, true, false, false, J, O, I) +
   schedule(S, false, true, true, J, O, I) +
   schedule(S, false, true, false, J, O, I) +
   schedule(S, false, false, true, J, O, I) +
   schedule(S, false, false, false, J, O, I)
  ) rem 10007.
schedule([$J|_], false, _, _, _, _, _) -> 0;
schedule([$O|_], _, false, _, _, _, _) -> 0;
schedule([$I|_], _, _, false, _, _, _) -> 0;
schedule(_, J, O, I, PJ, PO, PI) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _, _, _, _, _) -> 1;
schedule([_|L], J, O, I, _, _, _) ->
  LL = length(L),
  case get({LL, J, O, I}) of
    undefined ->
      Ret = schedule(L, J, O, I),
      put({LL, J, O, I}, Ret),
      Ret;
    Memo -> Memo
  end.

再帰はパターンマッチとか使えるととても書きやすいですね。
Erlangにはプロセス辞書という仕組みがあってメモ化するのも非常に簡単です。
プロセス辞書にキャッシュを入れるのは正しいことなんでしょうかね。。。

追記(3:14):
公開してすぐにもっとシンプルに書けることに気が付きました。Blogに公開することは偉大ですね。

-module(aoj0595).
-export([main/0]).

main() ->
  _ = io:get_line(""),
  S = string:strip(io:get_line(""), right, $\n),
  io:format("~p~n", [schedule(S, {true, false, false})]),
  init:stop().

schedule(S, State) ->
  Bool = [true, false],
  Cand = [{J, O, I} || J <- Bool, O <- Bool, I <- Bool],
  lists:foldl(fun(X,Acc) -> Acc + schedule(S, X, State) end, 0, Cand) rem 10007.

schedule([$J|_], {false, _, _}, _) -> 0;
schedule([$O|_], {_, false, _}, _) -> 0;
schedule([$I|_], {_, _, false}, _) -> 0;
schedule(_, {J, O, I}, {PJ, PO, PI}) when not ((J and PJ) or (O and PO) or (I and PI)) -> 0;
schedule([_], _, _) -> 1;
schedule([_|L], State, _) ->
  LL = length(L),
  case get({LL, State}) of
    undefined ->
      Ret = schedule(L, State),
      put({LL, State}, Ret),
      Ret;
    Memo -> Memo
  end.

コードの概要

書いていることは至ってシンプルでJ君,O君,I君の今日と前の日の状態を持って,
それをパターンマッチによって遷移できない状態を除外しているだけです。
あり得る組み合わせだった場合、次の状態に遷移します。
遷移できる次の状態がたかだか8通りなのですべての遷移を試すコードになっています。
あとは引数によって状態が変わらないのでメモ化することができます。

終わりに

Erlangっぽいコードが書きたいなら競プロするな?って感じですね。

第26回高専プロコン競技部門 反省会場

この記事はICT Advent Calendar 2015の7日目として書かれました。

はじめに

ブログの更新は1年ぶりになります、@orisanoです。
去年のICT Advent Calendarぶりの投稿になります。
今年はいろんなイベントや大会に参加しましたし、残り短いですがまだまだ参加します。
今年参加した中で個人的に最も注力したのが"""高専プロコン"""です。
読んでると思われる層の人は知っていると思うので詳しくは説明しません。
今年は競技部門に参加してきました。そのことについて書こうと思います。

高専プロコン競技部門と僕

今回の高専プロコン競技部門(以下競技部門)のチームは進捗優先探索という名前で

  • 僕 (専攻科1年) (リーダー兼コーダー)
  • レオきゅん (4年) (コーダー)
  • じんくん (2年) (コーダー)
  • 1年生2人

という構成で役割としてはリーダー(初)のような物をやっていました。
ちなみに僕は競技部門に参加するのが今年で4回目になります。

  • 舞鶴大会 (良い問題、なとりうむさんに初めてあった)
  • 有明大会 (サイコロ回、感情喪失)
  • 旭川大会 (サイコロ通信回)
  • 長野大会 (今回)

どの大会も思い出深いですね。(サイコロは絶対にユルサナイ)

初動

今年の競技部門の課題は「石畳職人Z」というタイトルで、
概要としては「全部埋まるかどうかわからないジグソーパズルを出来るだけ埋めよう」というものでした。
詳細が知りたい方はこちら

問題が公開されてすぐに練習場の作成にとりかかりました。
去年と違って競技者として参加するというものあって公開しませんでしたし、内部的にも活用しませんでした。
練習場の作成を通して、ルールの理解や曖昧な部分が理解できるのでとてもおすすめです。
練習場の作成が終わった頃から簡単なサーベイをしたり、チームメンバーに対して
探索アルゴリズムの概要をレクチャーしたりしていました。
それと並行してSiv3Dを用いたビジュアライザー兼手動ソルバーなどを作りました。
(本当はこの辺から一年生に対してちゃんと指示を出したりすべきだったんだろなぁ)

6~8月

土台が出来上がってきたので、ソルバーの実装ににとりかかりました。
非公式練習場(以下練習場)に提出を始めたのこの時期からです。
(練習場自体は5月くらいにはできていて、当時では信じられない解が提出されていた)
今回モチベーションが保てたのも練習場の存在があったからと言っても過言ではないでしょう。
練習場を公開していた@mecha_g3さんには感謝しかないです。
この頃は僕のソルバーはボロボロで全然良い解が出ずとてもつらい思いをしていました。
一方じんくんのソルバーがそれなりに良い解を出しており、評価関数の重みなどを参考にしたところスコアがかなり改善したことを覚えています。
じんくんありがとう。。。
KNCTが練習場にたくさん発生していて上位を独占していた頃でもありました、この時はひたすらKNCT爆発しないかなとか不穏なことを言っていた気がします。

最終的には僕もKNCTを名乗っていました。

ブレイクスルーとして高速化のために制限をかけたソルバーが
良いスコアを出すようになり、練習場でほとんどの問題で1位になりました。
8月の後半(?)からTMCITの攻撃が始まって、競争が激化します。
がスコアが全然改善せず、モチベーションがどんどん維持できなくなっていきました。
進捗管理も疎かになりました。ほんとにダメですね。

9月~

夏休みの期間はインターンシップで株式会社ABEJAさんとDeNAさんに行きました。
合わせて3週間ほどでしたがとても良い経験になりました。
その間は開発お休みしていました。( ◞‸◟ )

ここからアルゴリズムベースの改良は少なくし、高速化や提出ツールの作成などに入りました。
tcmallocなど修正無しで高速化が見込めるツールの導入や、
Instrumentsなどを見ながらボトルネックを探して高速化していました。
また_GLIBCXX_PARALLELで楽して並列化を行いました。
これでそれまでの4倍程度の速度が出るようになりました。やったね。

提出ツールの作成にあたって、チームの中で僕が一人だけ
Macユーザだったのでマルチプラットフォームを意識しなければいけなくなりました。
ISUCONのために勉強していたgolangで書きました。クロスコンパイル最高!

問題の1位取得数は6個で1位だったので比較的心おだやかに長野へ向かいました。

本番

長野に到着してからはどうやってTMCITの人を闇討ちするかを考えていました。いませんでした。

初日は練習と1回戦があったのですが練習の様子を見ると
自動で問題取得、解の提出ができないと困るということが分かりました。
空いた時間を使って取得、提出の流れを自動化してくれるツールを作りました。これが1回戦で非常に役に立ちました。
1回戦は第2試合だったのですが、1位、1位、2位と最終成績2位で突破することができました。(NAPROCKを除くと1位)
1問目はほとんど提出の速度を競う勝負になっていたので
自動化ツールが火をふき1位を取ることができました。
1回戦に関しては数ヶ月の努力があったのでそんなに不安はありませんでした。
準決勝は、5位、3位、3位と最終成績3位で突破することができました。
僕は4回目で初の決勝進出だったのでとても嬉しかったです。(顔がニヤついた写真が。。。)
決勝は10位と個人的には残念な結果でしたが、特別賞がもらえたのでよかったです。

反省

リーダーとしてもっとちゃんと仕事をふるべきだった。
進捗確認も絶やさずするべきだったし、困っているところをヒアリングすべきだった。
せっかくチームに入ってもらった1年生たちに仕事を振れず、
かと言って何かを教えることもできず、プロコンの楽しさを
十分に経験させられなかったことが一番の反省点です。本当に申し訳ない。

最後に

なんだかんだ個人的には今年のプロコンとても楽しめたので大満足です。
専攻科に進学した意味があったと思える出来事でした。
現地では他の高専の競技部門の人とそれなりに交流できたし、最高でした!!
チャンスがある後輩の皆さんは自分の武器を磨いて高専プロコンに出ましょう!!
以上、老害からでした。

明日は駐日ユーゴスラビア臨時政府大使館(@ICT_yugosoviet)です。
めちゃくちゃおもしろい記事を書いてくれることを期待しています。