CODE FESTIVAL 2016 参加記

時系列順に書いていきます。

1日目

到着

11:10頃到着した。知り合いが結構いた。

本戦

本戦は3時間(12:30 - 15:30)であった。4完(A,B,C,D)2半(E,H)の計2,700点(54位)でパーカーを取得した。以下簡単に時系列順にコンテストの進め方を書く:

  • 0h00m - 0h30m (12:30 - 13:00)
    A,B,C,D問題を解いた。(+1500)
  • 0h30m - 1h00m (13:00 - 13:30)
    最初の15分でEの部分点を通し(+500)、残り15分で満点解法を考えていた。それでもわからなかったので後回しにして、別の解ける問題を探すことにした。
  • 1h00m - 1h40m (13:30 - 14:10)
    Hを考察し、部分点を手に入れた(+700)。
  • 1h40m - 2h10m (14:10 - 14:40)
    Gが解けそうだったので解こうとした。自明な解法(queueに枝を突っ込んでKruskal)をやってみたがTLEなどで落ちたので断念した。
  • 2h10m - 3h00m (14:40 - 15:30)
    Eの満点やFを解こうとした。Fの考察について、dpでやりそうだということは分かったが、indexについてかなり長い時間試行錯誤*1を繰り返したので、時間がかなり取られてしまった。正解が分かった時点では残り時間が10分程度しかなく、そこからバグなく実装することができなかったため、Fは正解できずに終わった。*2 *3

11/28追記: 提出一覧f:id:koba-e964:20161128130513j:plain

11/28追記: 終了後に高校で同期だったyurahunaに遭遇した。高校の同期であったことはこの時初めて知った。東京に来た地元の人間は相当稀なので嬉しかった。

夕食・自由時間

今年の夕食はケータリングだった。*4

自由時間は割と暇を持て余しがちだった。将棋AIのトークを聞きに行って、そのあと学科同期の人たち*5で集まってボドゲで遊んだ。

Exhibition直前に太鼓の達人をminus3thetaと一緒にやった。曲は知らなかったのでminusに選んでもらった(マリオワールドのむずかしいだった)。一応合格できたが疲労で死ぬかと思った。minusがうまかった*6。

Exhibition

強い人が強いことをやっているなぁという印象だった。色々思うところがあり*7、それとなく聞き流しながら一人でfinalの復習をやっていた。

Team Relay (Introduction)

チームリレーの顔合わせ、自己紹介をやった。私たちはTeam Dで、海外勢はFatalEagleで、日本勢はHuziwara, kobae964, siotouto, ei1333, beet, dolicas, zeptometer, ioryz, haradukaの9人だった。
英語の練習をするためにFatalEagleに話しかけようとするも、緊張のあまりろくに話せないという事態になってしまった。

宿泊

イベントが終わって全員帰宅かホテルに向かうという形になった。今年はホテルがバラバラなようで、ホテルへのバスは出ず自分で歩いていかなければならなかった。*8

2日目

朝プロ (Elimination Tournament)

3回戦まで行くも敗退。

  • 1回目 (group11)
    A 500, B 100の計600点で通過。
  • 2回目 (group11 + group12 -> group06)
    A 700, B 200の計900点で通過。Aはよくわからなかったがサンプルケースからエスパーして通った*9ので一人で爆笑していた。*10
  • 3回目 (group05 + group06 -> group3)
    A 200, B 400の計600点で脱落。通過したかったらAは700点取る必要があった。

また自由時間

筋力: 17ptくらいしかとれなかった。前屈+10cm, ジャンプ36cm*11, 握力36kgf, 背筋120kgf。
LT: chokudaiがハンドスプリングをやっていて強かった。

Team Relay

作戦タイム

まず、11問の問題に対して10人のメンバーなので、2問解く人間を決めなければならなかった。スタッフの方から「チーム内でチーム内順位3位以下の人」が2問解くという説明を受けたので、チーム内順位3位の私が2問解くことにした。
次に、10人のメンバーを3つのクラスタに分け、それぞれのクラスタに問題を割り当てた。*12 割り当ては以下の通り:

  • A,B,C,D,E
    dolicas, zeptometer, ioryz, haraduka, kobae964
  • F,G,H
    siotouto, ei1333, beet
  • I,J,K
    FatalEagle, Huziwara, kobae964
本番

チーム内全員の動きを把握していたわけではないので、細かい動きは分からないが、私たちのチームは非常によく戦い、2位になった。
私の動きは以下の通り:

  • 最初
    Eを読んで即*13解法を思いつき、haradukaがAを解き終わった直後に実装してEを通した(07m04s)。
  • 中盤
    Iをやることにして、簡単な解法を思いついたので行ったものの、コーディングスペースで間違いに気づき、WAをもらった(nが奇数の時にしかうまくいかない解法だった)。11/28追記: FatalEagleがJ問題の解法を思いつき、そのアイデア*14の素晴らしさに感服した。またHuziwaraとFatalEagleがK問題を頑張って考察していたが、私はこの手の問題が苦手で全く貢献できなかった。
  • 後半
    他の人のアイデア*15を使って、n=2のときはダメで、それ以外のnについて具体的に解を構成する方法を見出した。*16 焦っている中でのdfs解法なので実装に手こずりそうだった(し実際にWAも3回出した)が、Huziwaraによる的確なデバッグにより見事AC(71m27s)して2位になった。

11/28追記: スコアボードf:id:koba-e964:20161128130145j:plain

インタビュー

私がIを通してチームが2位になった直後、カメラマンがインタビューに来た。なぜか私が感想を聞かれることになったが、緊張のあまり(日本語なのに!!)ろくに聞き取れず返答もままならない、という醜態を晒すことになった。

aftermath

テンションが上がりまくっていて、極度の疲労状態になり、足腰もガタガタという状態が全完後1時間くらい続いた。FatalEagleが他の(全完した)チームの人と話したいと言ってきたので、スタッフの人に尋ねてみた。*17 またFatalEagleに「この"3y3s"の意味わかる?」と聞いたら、「"eyes"のことで、問題番号の"I"とかけているのでは」という答えをもらった。*18

表彰

1位のチーム(50分程度で全完した)が表彰されているのを見てすごいなぁと思っていたら、2位のチームも表彰される*19ということになって、足腰ガタガタのまま壇上に上がった。Best Collaborator Awardのマグカップをもらったが、手が痺れて落とす危険性が高かったので後ろの人に持ってもらった。もしかしたらまたインタビューされるかもしれないと思って何を言うか少しだけ考えたが、その予感は的中してしまい、感想を言うことになってしまった。qnighyへの対抗意識からせっかくの機会なので英語で以下のようなスピーチをした(文法的にヤバい場所は赤で、可能な改善点は青でハイライトしている):

EVERY ONE of our team worked very well*20, and our team worked quite well together*21. I couldn't be prouder to*22 compete and enjoy with every other people*23 in this*24 team.

翻訳:

(通訳の方、駄文で本当に失礼しました…。)
そのあとはいよいよ足腰がやばくなって来たので座ったりした。

Team Relay 総括

上に書いた通りである。

帰路

学科同期とセイクで優勝した
11/28追記: そのあと汐留駅のイルミネーションを見た。雨だったのが残念だが、こういうところに恋人と行くとロマンティックなんだろうなぁなどということをぼんやりと考えていた。

総括

とても楽しかった。特に問題を早く解くことは苦手なので、朝プロは良い練習になった。また英語で話すのも苦手*25なので、練習の機会としても絶好の機会であった。

まとめ

関係者の皆さん、本当にありがとうございました!!!

*1:[現在の移動の数]に加えて、[今まで見た頂点の数] -> [今まで見た頂点の数][番号最大の頂点から戻れる頂点番号の最小値] -> [今まで見た頂点の数][頂点1に戻る道のある頂点の番号の最大値] という順番で考察した。最後のは正解

*2:自分の実装力の低さ、Gと戯れていたことに対する後悔などで精神がズタボロになっていた。

*3:事前に順位表を見てqnighyがE,Fを通していたのは知っていたので、Fを通して勝ちたいと思ったが、間に合わなかった。

*4:去年はチケットと自分の好きな食事を交換する形式だった。遅く行っても(選ばなければ)食事は残っているだろうと思って遅めに行ったら、そもそも食事が残っていなくて辛い思いをした。

*5:kw_udon, zptmtr,minus3theta

*6:確か200,000 < 私のスコア < 230,000 < 270,000 < minusのスコアだったと記憶している

*7:この時点ではまだfinalの結果が思わしくなかったことについての傷が癒えていなかった。

*8:一概に悪いとも言えなくて、ホテルから会場に向かうのにバスを使う必要がなく、寝坊してもある程度はカバーできる。

*9:ceil(x/2) / pはエスパーしようと思えばできる。

*10:あとで周囲に聞いたら、期待値の線型性などを使うと簡単に答えが導出できるということが分かった。

*11:モヤシなので体力がなく、とくにジャンプ力が弱い

*12:去年の私のチームのやり方と同じである。

*13:11/28追記:よく考えて見ると、少し詰まって5分くらいかかったので、「即」ではなかった。

*14:3行ごとに1行全て埋める + 周囲を埋める

*15:n=2kのケースはn=kのケースに帰着できる。11/28追記:zeptometerらが思いついた気がするが、記憶がはっきりしない(すみません…)。

*16:n=4の時はad-hocにつくる。

*17:OKだが、解法を話すのはやめてほしいということだった。

*18:実はこれは某音ゲー由来だということを、帰宅してから知った。

*19:Best Collaborator Award

*20:考え直したらhardの方がそれっぽい

*21:acting as oneなどという表現も使いたい

*22:proud to Vは〇〇できる(現在)ことを誇りに思うので、"prouder to have competed and enjoyed"の方が良さそう、だけど話している間にそんなことを考えるのは無理

*23:all the other membersなどがよい

*24:ourの方がよいかなぁ

*25:他人より苦手とは言ってない、残念ながらこれでもかなりマシな方らしい

CODE THANKS FESTIVAL 2014(A日程) 参加記

当時(2014/12/7)に書いたまま下書きに残っていたので、今更&未完成気味ですが一応公開しておきます。

---------------------------
2014/12/7のCODE THANKS FESTIVAL 2014 A日程に参加してきました。

問題の感想

A カメツル算

4 * a + 2 * b。 やるだけ。

B バッジ

機械A, B, Cを生産能力の高い順に並べ替えて順番に使うだけ…なんですが、割と「並べ替える」ところではまる人がいた印象があります。
自前で条件分岐を使いまくって並べ替えを行うと時間がかかりまくってバグの原因にもなるので、必ず標準ライブラリのソートを使いましょう。
(C++なら<algorithm>をインクルードして

int a[3];
/*a に値を入れる */
std::sort(a, a+3); /* a[0]から小さい順になる */
std::reverse(a, a+3); /* a[0]から大きい順になる */

でできます。
)

C コンテスト

やるだけ。1-indexedであることに注意しましょう。

D 定期券

やるだけですが普通にやると条件分岐が面倒です。解説でもあったように共通部分を引くと良いでしょう。

E 儀式

i番目だけをやり忘れた時の結果を計算することを考えます。いちいち(n-1)回シミュレーションをやると時間がかかるので、操作が可換(どの順でやっても結果が同じ)であることを利用して、最終結果にi番目の操作の逆の操作を行いましょう。

F 順位表

参加者を頂点としたグラフに「順位の低い方から高い方へ向く辺を設ける」ということをすべての大小関係に対して行います。そのようにしてできた有向グラフにおいて、1から辺をたどって到達できる頂点数を数えればよいです。詳しくは解説を参照。

G 通勤電車と気分

部分点解法(n <= 10)は各乗客に対して2パターンをどちらも試せばできます(O(2^n)-時間)。この部分点解法を狙うときは、例えばn>=15のときにexit(1);などを行うと良いでしょう。
満点解法を書くには空き座席のパターンをつかむ必要があります。席に誰かが座っている状態を1、そうでない状態を0をするときに、余中の状態は
111...11101010101...0100000
というようになることを利用します。

H 模様替え

感想

本選2日目に予定が入ってしまい参加できなくて残念だったのですが、今回この様な機会をいただくことができてありがたく思っています。
B日程には(すでに予定が入っているので)参加しません。

素数判定を1.5倍速くする話


このツイートを見てこの論文の存在を知り、どのくらい速くなるのか疑問に思ったので性能評価をしてみました。

やったこと

32bit符号なし整数の高速な素数判定方法の実装及び既存のアルゴリズムとの性能比較。

環境

学科で渡されたノートパソコン。

結果

$ g++ -O2 -Wall Forisek.cpp -o Forisek
$ time ./Forisek 1
prime count: 14630842

real 0m30.210s
user 0m30.182s
sys 0m0.000s
$ time ./Forisek 2
prime count: 14630842

real 0m45.133s
user 0m45.035s
sys 0m0.012s

上が論文の手法、下が2,7,61の3種類の底によるMiller-Rabin法です。
およそ1.5倍の高速化となりました。

考察

どちらの手法でも高速化のために小さな約数があるかの判定を行っているので、単純に3倍にならなかったものと思われます。

これから

64bit符号なし整数の素数判定についてはまだ読んでいないので、これから取り組んでみます。
結局学生の手抜きレポートみたいな出来になってしまった…(>_<)

参考

ミラー-ラビン素数判定法 - Wikipedia Miller-Rabin法自体の詳細はここが参考になります。
Miller-Rabin SPRP bases records Miller-Rabin法の底の選び方などの参考になります。

Scala覚え書き(構文編)

最近Scalaを始めました。(函数型プログラミングと手続型プログラミングの良いとこ取りをできると聞いて)

以下覚え書きみたいな感じでこの数日で学んだことを書いていきます。
主にJavaを知っている人向けにJavaとの違いをメインに書きます。
今回は構文の話です。

構文

演算子

四則演算

Javaでは四則演算はint, long, doubleなどのプリミティブ型にしか使えませんでしたが、ScalaではBigInt(scala.math.BigInt, BigIntegerのScala版)などの型を持つ値に対しても使用可能になっています。またユーザーの定義する型についても自由に演算子を定義することが可能です。

1引数メソッドとの関係

Scalaでは四則演算を含む演算子はただの1引数のメソッドとして定義されており、例えば

a + b

という式は

a.+(b)

として解釈されます。逆に1引数のメソッドは(その名前が何であっても)中置記法の2項演算子として書くことができ、例えばBigIntのpowメソッドを呼び出す際に、

a pow 4

と書けば

a.pow(4)

と同じ扱いになります。
演算子の優先順序や結合性はその名前の最初の文字などによって決められており(例えばここを参照)、このためシフト演算子(<<)と比較(<)が同じ優先順序になるという面白いことが起きています。また、名前の最後の文字が":"のメソッドは右結合で、中置記法で書くと左右が逆になります。例えば

a :: b

は

b.::(a)

とみなされます(おそらく不変リストの定義のための仕様)。

宣言

変数

Scalaにはどこを参照するかを変更可能な変数と変更不可能な変数があり、それぞれvalとvarを使って定義します。例えば

val q : Int = 4 // q is of type Int and initialized with 4. The value of q cannot be changed.

や

var r : Int = 5 // r is of type Int and initialized with 5. One can modify the value of r by assignment (for example, "r = 3").

などと定義します。varで定義した方は例えば

r = 3

などとして値を変更することができます。
また、クラスのインスタンスを格納する変数をvalで定義した場合、どこを参照するかを変更することはできませんが、中身を変更することはできます。例えば

val arr = Array(1,2,3) // Initialized with an Int array with element {1,2,3}.
arr(0) = 4 // The first element becomes 4.

は正しくコンパイルできます。

クラス

Javaでは

public class AAA {
public int ff(int q) { /* ... */ }
}

だったのが、Scalaでは

class AAA {
def ff(q : Int) : Int { /* ... */ }
}

と書くことになります。(デフォルトでpublic)
staticメソッドは書けませんが、代わりにオブジェクトという、Javaでいうstaticメソッドしかないクラスを定義することができます。例えば、

object WW {
def gg(q : Int) : Int { /* ... */ }
}

で大体Javaの

public class WW {
public static int gg(int q) { /* ... */ }
}

と同じ意味です。


次は型システムと標準ライブラリについてです。

ラムダ式→SKIコンビネータ項

概要

ラムダ式をSKIコンビネータの式に変換するプログラムを書きました。
koba-e964/ski-comb · GitHub

やったこと

ラムダ式→SKIコンビネータの項の変換

実装は
高階ことりちゃんと学ぶSKIコンビネータ
を参考にしました。

例

Haskell風の書き方で説明します。やり方は上のリンク先に書いてあるので、ここでは実例だけ紹介します。
C = \x y z -> x (y z)
をSKIコンビネータ項に直してみましょう。
(1) 全てのλ抽象を新しく導入した関数に直す。このとき、新しく導入される関数の定義は、
関数名 自由変数... ラムダ式で束縛される変数
の形になる。
まずトップレベルの\x->...を直しましょう。

C = M
M x = \y z -> x (y z)

続いてM xの内部の\y -> ...を直します。

C = M
M x = N x
N x y = \z -> x (y z)

同様にして最終的には以下のようになります。

C = M
M x = N x
N x y = O x y
O x y z = x (y z)

(2) 関数の引数を消去してS,K,Iのみで表す
O x y z = x (y z)
O x y z = (K x z) (y z)
O x y z = S (K x) y z
O x y = S (K x) y
O x = S (K x)
O x = (K S x) (K x)
O x = S (K S) K x
O = S (K S) K

C=M=N=O*1より、結局
C = S (K S) K
がわかる。

課題


ここのやり取りで気付いたのですが、今のままだと実行時間も出力されるコードも線型よりも速いペースで増大します。現在のところどのくらいのペースで増大するのか見積もりができていないので、

  • 計算量・出力されるコードの大きさの増大の速さの見積もり
  • 高速化・サイズ削減

が目標になるかと思います。

*1:実際のコードではここもちゃんとやっているのでコードが肥大化します

ICPC 2014 Domestic

ICPC 2014 DomesticにAyatakaというチーム名で参加しました。
(メンバ:ばいなり(b_inary), うどん(kw_udon_), こば(kobae964))

A
うどんがやってくれました

B
私がやりました( Ideone.com - 2gTylp - Online C++ Compiler & Debugging Tool )

C
ばいなりがやってくれました

D
うどんと私がやりました ( Ideone.com - bJqf8d - Online C++ Compiler & Debugging Tool )

E
ばいなりがやってくれました

F
全員で考えました。
貪欲に残り回数が一番多い方向へ転がすという方針でやったら失敗しました。コンテスト終了後に7完したチームに解法を聞いたらあざやかでびっくり。

G
捨てました

こんな感じで5完13位( ACM-ICPC 2014 国内予選順位表 )でした。選ばれなかったAyataka(>_<)

モナド変換子の圏論的理解(Categorical understanding of monad transformers)

モナド変換子

Haskellにおいてモナド変換子(Monad transformer)は、以下の条件を満たすtです:

  • tのkindは(* -> *) -> * -> *
  • lift :: Monad m => m a -> t m aが定義されている
  • liftが以下の法則を満たす:
    1. lift . return = return
    2. ∀m k. lift (m >>= k) = lift m >>= (lift . k)

(この定義を便宜上函数的定義(functional definition)と呼びます。)
この定義を圏論の言葉を使って書きなおすことを考えると、以下のようになります:

  • tのkindは(* -> *) -> * -> *
  • lift :: Monad m => m a -> t m aが定義されている
  • liftが以下の法則を満たす:
    1. liftはmからt mへの自然変換(natural transformation)になっている。つまり、
      • ∀(k :: a -> b). fmap k . lift = lift . fmap k
    2. liftはEndofunctorの圏におけるモノイド対象の準同型である。つまり、以下が成立する:
      • lift . return = return (単位元を保つ)
      • lift . join = join . fmap lift . lift (積を保つ)

(この定義を便宜上圏論的定義(categorical definition)と呼びます。)

この二つの定義が同値であることを示します。

函数的定義→圏論的定義

(1) lift . return = return
(2) ∀m k. lift (m >>= k) = lift m >>= (lift . k)
を仮定する。

(i) ∀(k :: a -> b). fmap k . lift = lift . fmap k

(2)においてk=return . fを代入すると
∀m f. lift (m >>= return . f) = lift m >>= (lift . return . f)
∀m f. lift (m >>= return . f) = lift m >>= (return . f) ((1)より)
fmap f m = m >>= return . fを利用すると
∀m f. lift (fmap f m) = fmap f (lift m)
∀f. lift . fmap f = fmap f . lift (mを消去)

(ii-i) lift . return = return

(1)から自明。

(ii-ii) lift . join = join . fmap lift . lift

(2)にk=idを代入すると
∀m. lift (m >>= id) = lift m >>= (lift . id)
m >>= id = join m, idは恒等射より
∀m. lift (join m) = lift m >>= lift
m >>= k = join (fmap k m)より
∀m. lift (join m) = join (fmap lift (lift m))
mを消去して
lift . join = join . fmap lift . lift

圏論的定義→函数的定義

読者の演習問題とする。(訳:疲れました)

追記(2014/06/25)要望があったので答えを載せます。(白い文字で書いているので選択すると読めます)
(i) ∀(k :: a -> b). fmap k . lift = lift . fmap k
(ii-i) lift . return = return
(ii-ii) lift . join = join . fmap lift . lift
を仮定する。

(1) lift . return = return

(i)から自明。

(2) ∀m k. lift (m >>= k) = lift m >>= (lift . k)

(以下白文字)

(i)の両辺に左からjoin . fmap liftを合成して
∀k. join . fmap lift . fmap k . lift = join . fmap lift . lift . fmap k
(ii-ii)を右辺に適用して
∀k. join . fmap lift . fmap k . lift = lift . join . fmap k
fmap (g . f) = fmap g . fmap fより
∀k. join . fmap (lift . k) . lift = lift . join . fmap k
両辺をmに適用して
∀m k. join (fmap (lift . k) (lift m)) = lift (join (fmap k m))
m >>= k = join (fmap k m)を利用して変形すると
∀m k. lift m >>= lift . k = lift (m >>= k)