読者です 読者をやめる 読者になる 読者になる

オセロ大会のこと

この記事は,OIT Advent Calendar 2016の11日目の記事です。

www.adventar.org

改めて自己紹介

2日目にも記事を書きましたがもう一度
現在OITのIS科3回生です.
IM科の研究室に所属しています.
HxS*1とか競技プログラミングチーム*2に所属しています.
このOIT Advent Calendarの企画をした人です.

オセロ大会

オセロ大会とはIS科学科長のF教授がOITの内部で年に1回開催している,オセロゲームプログラミングコンテスト(学内のみ)のことです.この大会は1回生から3回生に参加資格があります.
勝敗の判定は,AI同士の対戦は先手後手を入れ替えて2回対局し,最終石差によって勝者を決めるというものです.
大会の形式は参加者を4つの予選ブロックに割り振った中で総当たり戦を行った後,予選ブロック上位者が決勝に進みそこでも総当たり戦を行って優勝者を決めるというものです.

なんやかんやで1回生の時から3年連続で参加し続けており,今年度の大会がちょうど昨日で,大会に参加出来るのは3回生までというルールもあって引退(?)となったので,オセロの盤面の表現評価関数, ゲーム木探索アルゴリズム大会の様子辺りを中心にこれまでの振り返りをしたいと思います.

1回生

オセロ大会を知ったきっかけは何だったか明確には覚えていませんが,きっと競技プログラミングチームに参加するうちにF教授に勧誘されたんじゃないかと思います.

  • 盤面の表現
    4回生の先輩から受けたアドバイスもあってオセロの盤面は64bitの整数型2つで表現していました. しかし手の生成は愚直にfor文でループを回すものだったため激遅でした.これで爆速になると勘違いしていたのだから恥ずかしい.
  • 評価関数
    局面の評価関数はとても単純なもので,自分の石の数に隅を取っている数を足したものでした.中盤終盤共に同じ評価関数を使っていたし,この頃の自分にはゲームAIにおける評価値って概念を持っていなかった気がします.
  • 探索アルゴリズム
    オセロAIについて解説しているサイトに必ずと言っていいほどMinMax法なるアルゴリズムが紹介されていたため,これを実装してみることにしました.競技プログラミング再帰関数は書き慣れているためか簡単に書き上げることができました.
    その後AlphaBeta法を知るけど時間もなく一応動いてるものを壊したくない思いもあって実装せず,本番はMinMax法を実装したAIで大会に参加しました.
  • 大会の様子
    C#のスレッドを使って探索を並列化したと言っている人や,ちゃんと中盤と終盤でAIの方針を切り替えている人がいて,自分のプログラムではきっと太刀打ちできないだろうなあと不安でした.しかし実際対戦してみるとその人達のAIがバグっていたせいか,相手を全滅させて予選を勝ち抜くことができました.
    決勝でもなぜか勝ちを重ねることができ,最後の試合は自分と同じく競技プログラミングチームに所属している3回生の先輩との対戦でした.
    1回目の対局では1-63で大敗し,2回目の対局もそうなるだろうと予想していましたが,先輩のプログラムの思考時間が制限*3に引っかかり幸運にも64-0*4で勝つことができました.結果的に2局の合計最終石差では自分が1石差でリードしているため勝ち判定になりました.最後は怪しい勝ち方でしたがオセロ大会で優勝することができました.1回生が優勝するのは大会史上初だったらしいです.

2回生

この年が一番オセロAIの開発に打ち込んでいました.The FFO endgame test suite の#40の完全読みにかかる時間をひたすら短縮していました.最初は完全読みに5分ぐらいかかっていたけど最終的に12秒までに短縮できました.
詳しいことはここに書いてあります. odan3240.hatenablog.com

  • 盤面の表現
    手の生成もビット演算で行う所謂BitBoardを実装しました.これでFFOの#40が1分以内に終わるようになった記憶があります.

  • 評価関数
    機械学習ベースのものにしようと考えていたけど時間が足りず,人間が盤面1マスずつ重みを付けたもの+辺や角を意識した評価値になりました.

  • 探索アルゴリズム
    中盤のアルゴリズムは以下の本を参考にNegascout法を採用しました.中盤では11手先を読むように設定していました.

    ゲーム計算メカニズム (コンピュータ数学シリーズ 7)

    ゲーム計算メカニズム (コンピュータ数学シリーズ 7)

    • 作者: 岸本章宏,柴原一友,鈴木豪,小谷善行
    • 出版社/メーカー: コロナ社
    • 発売日: 2010/02/08
    • メディア: 単行本(ソフトカバー)
    • 購入: 3人 クリック: 66回
    • この商品を含むブログ (7件) を見る
    終盤はZebraの作者が速さ優先探索*5がいいと言っているらしい*6のでそれを採用しました.これによってFFOの#40が20秒台になったはず.
    空きマスが20個以下になったら完全読みするように設定していました.

  • 大会の様子
    前日までAIのバグ取りをしていました.Visual StudioでBOM付きじゃないUTF-8を使うと意味不明なバグを踏むので気をつけましょう.
    この年はCODE RUNNERと日程が被っていたので,学科の友達にAIだけ預けました. その友人に結果を聞いたところによると,ランダムに手を打ってくるAIに時間超過で負けた以外は全勝で優勝したらしいです.

終了直後は来年はもっと強いAIを開発して優勝しようなという気持ちに溢れていました.

3回生

1年前の大会直後は意気込んでいましたがこの年が一番やる気がありませんでした(悲しい).
プログラム自体は1年前のものとほぼ変わらず,置換表のバグを修正した程度でした.

  • 大会の様子
    F教授曰く参加者のレベルが低調な大会だったらしいです.参加者に1回生,2回生が1人もいなかったし,強制参加のF研の人たちは200行程度のとりあえず動作するオセロプログラムだったし僕も全く取り組んでなかったし仕方ないねって感じです.
    無事3連覇できたけど真面目に取り組んでなかったためか,喜びは薄かったです.

できればtensorflowで機械学習をやり直したり,Lazy SMPを実装したり,将棋所みたいなGUIのアプリを組んで参加したかった...
終盤ソルバの高速化に喜びを覚えたように評価関数のlossを小さくすることに喜びを覚えるようになったらまた開発を再開するのかなあ

おわり

結局一番オセロAIの開発の打ち込んでいたのは2回生の時でした.情報収集とコーディンを繰り返す日々で,OBの人のオセロAI開発ブログを発掘するなんてこともありました.
この時の経験によってプログラミング技術の向上だけでなく,単体テストを書いてTravis CIでコードの品質を担保するなど開発体制の勉強にもなったので,大会に参加出来たことに自分は満足しています.夏休みのインターンに申し込んだ時は話すネタにもなって選考を通過できましたし.

真面目に取り組むとAIを強くすることは楽しいしメリットもあるので,参加資格があるOITの人は是非参加してみるといいですよ.

*1:HxS wiki - HxSコンピュータサークル

*2:ACM-ICPCに参加するためのサークルのような組織

*3:1手の思考時間は5分まで

*4:ルールでバグや時間超過を起こすと無条件に64石を得る

*5:着手可能数が少ない順に探索するアルゴリズム

*6:強いオセロプログラムの内部動作

CODE FESTIVAL 2016参加記

はじめに

この記事は,OIT Advent Calendar 2016 - Adventarの2日目の記事です.
OITとの関わりとしては現在IS科の3回生です.
つい先日CODE FESTIVALという競技プログラミングの大会の決勝に参加してきたので,大学の人への宣伝も兼ねて参加記をAdvent Calendarとして書きます.

本選まで

CODE FESTIVALではA,B,Cの3つの予選があり,大学生以上の学生のうち既に通過した人を除いてそれぞれ100位以内,60位以内,60位以内の人が東京で行われる決勝に招待される.僕は予選Bで60位以内に入れたらしく通過した.

予選A

ACM-ICPC国内予選ぶりに競技プログラミングの大会に参加した.結果的に3完早解きが予選通過ラインだったが,あまりコーディングが速い方でもないので297位で無事死亡した.

予選B

お昼開始のコンテストで,起きてご飯食べてお昼寝していたら15分寝坊して絶望しながら参加した.実験用の図を紙に書こうとしてもうまく書けなかったので,本当に寝ぼけていたように思う.C問題,D問題が貪欲法が想定解の問題で,うまくその解法に気付けたので171位といういい順位を取ることができ,予選を通過できた.

本選

会場まで

12時の開会式に間に合うように7時に家を出た.地元の在来線に乗った瞬間スマホの充電器を家に忘れたことに気付いて絶望.
新幹線で富士山や新橋で電通のビルの写真を撮影した.

昨年得た知見として早めに会場に到着することで,交通費精算列を回避でき任意のサイズのTシャツを選べることがわかっていたので,早めに会場に到着するようにしていた.

コンテストまで

Indeedのツアーで一緒だったStoneDotさんや,KUPCで会って以来だったomuさん,やざてんさんに会ってパーカーほしいよねって話をする(決勝で一定以上の成績を取るとパーカーがプレゼントされる仕組み). テーブルには軽食が用意されていた. f:id:odan3240:20161202132808j:plain それとお菓子も去年同様用意されていてハッピー f:id:odan3240:20161202142543j:plain

コンテスト

A

やるだけ

int H,W;
string S[26][26];
int main() {
    cin>>H>>W;
    rep(i, H) rep(j, W) cin>>S[i][j];

    rep(i, H) rep(j, W) {
        if(S[i][j] == "snuke") {
            printf("%c%d\n", j + 'A', i + 1);
        }
    }

    return 0;
}

B

問題文に最大値の最小化が見えたので思考停止で二分探索.ACしてから二分探索部分あまり必要なかったのでは?と気付く.

ll N;
bool ok(ll i) {
    ll d = N - i;
    return i * (i - 1) / 2 >= d;
}
int main() {
    cin >> N;
    if (N == 1) {
        cout << "1" << endl;
        return 0;
    }

    ll lb = 0;
    ll ub = N;
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        if (ok(mid))
            ub = mid;
        else
            lb = mid;
    }
    cout << ub << endl;
    ll d = N - ub;
    for (int i = ub - 1; i > 0; i--) {
        if (d - i >= 0) {
            cout << i << endl;
            d -= i;
        }
    }
    assert(d == 0);
    return 0;
}

C

問題文を読むと連結か判定する問題だとわかって,制約を見ると人を頂点にグラフを作るとTLEするとわかる.言語を頂点にグラフを作るとうまくいきそうな気がしてコードを書く.言語1が必ず入力の中にあると勘違いしたコードを書いて1WAを貰うが修正してAC.

int N, M;
int K[100005];

int main() {
    cin >> N >> M;
    UnionFind uf(M);
    set<int> s;
    rep(i, N) {
        cin >> K[i];
        vector<int> vec;
        rep(j, K[i]) {
            int a;
            cin >> a;
            a--;
            s.insert(a);
            vec.push_back(a);
        }
        rep(j, vec.size()) if (j) { uf.unite(vec[j], vec[j - 1]); }
    }
    if (uf.size(*s.begin()) == s.size())
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

D

modで分類するのはすぐにわかったけど,二つの条件をどう使っていくかがわからなかった.とりあえず,二つ目の条件を先に使うのが正しいと思い込んでコードを書くが,modでまとめた後どうやってペアを見つければいいのかわからず,時間を溶かす.最終的に奇数のやつから使っていってそれでも足りないと偶数のやつを使うコードを書いた.

int N, M;
int X[100005];
int cnt[100005];
int mod[100005];
int pena[100005];

int main() {
    cin >> N >> M;
    rep(i, N) cin >> X[i];
    rep(i, N) cnt[X[i]]++;
    rep(i, N) mod[X[i] % M]++;
    int ans = 0;
    rep(i, M / 2 + 1) {
        if (i == ((M - i) % M)) {
            ans += mod[i] / 2;
            pena[i] = mod[i];
            continue;
        }
        int a = min(mod[i], mod[M - i]);
        ans += a;
        pena[i] = pena[M - i] = a;
    }
    int m = *max_element(X, X + N);
    rep(i, m + 1) {
        if (cnt[i] % 2 == 1) {
            cnt[i]--;
            pena[i % M]--;
        }
    }
    rep(i, M) {
        if (pena[i] > 0) {
            ans -= (pena[i] + 1) / 2;
        }
    }
    rep(i, m + 1) ans += cnt[i] / 2;
    cout << ans << endl;

    return 0;
}

E

この問題を解くと決めた段階で残り時間は50分程度だった.3時間コンテストはハマるとすぐに時間が溶けるので厳しい.TLEするDPは書けたけどここからどう計算量を減らすかがわからず時間を溶かす.終了10分前ぐらいにdp(t) := 時間tでの最大枚数にすれば良さそうなことに気付くけど状態の更新式がわからず終わり.

結果

4完で1500点の159位だった.あと100点でパーカーだったので悔しい.去年より順位を落として全体のレベルが上がっているのかなと感じた.

touristのトークライブ

2日前ぐらいにハッシュタグで質問したい内容を募集していたので,前から気になっていたことを投稿した.

プログラミングは,7歳の頃に両親からプログラミングを教わって始めたらしい.競プロは何か言ってたか忘れてしまった. あと競プロをやる上で重要なのは覚悟(日本語訳)って言っていたのは印象的だった.

夕飯

立食形式だった.取りに行ったのが遅かったせいか,残っている寿司ネタの偏りが酷くて笑った.美味しそうなやつを少し摘んで食べた程度f:id:odan3240:20161202135646j:plain

山本一成氏のトークライブ

モジュール化と高速化は両立しないってのは確かにそうだと感じた.また単体テストが重要だと聞いた時,Zebraの作者も同じようなことを言っていたのを思い出した.自分のオセロAI開発もそうだけど,研究にも役立てたいと思った.

iwi先生のペアプロ

全探索のコードの結果を眺めて考察することや図を書いて実験することの重要性を再確認できた.去年と同じで楽しくペアプロの様子を観戦できた.

エキシビションマッチ

今年はチーム戦だった.yurahunaさんと各スクリーンの前を行ったり来たりしていた.驚いたのはtouristのタイピングスピードで,途切れることなく滑らかに文字が入力されていって見ていて笑いがこみ上げた.僕がrepマクロ使ってforを書くより速いスピードで普通のforを書いているんじゃないかと思うレベル.反面autoとかrange-based forを使わずにコードを書いているのはなんでか気になったりした.

ホテル

今年は参加者が全員同じホテルではなく,幾つかのホテルに分散して宿泊することになったらしい.同じホテルの人について行って道に迷うことなく到着した.部屋にはスマホ用の充電器が用意されていて神だった.
このホテルは朝食も無料で用意されいて,特に僕の好物のいなり寿司が食べ放題だったのが嬉しかった.嬉しすぎていなり寿司10個食べたレベル.f:id:odan3240:20161202135501j:plain

トーナメント

テーブルには朝食が用意されていた. f:id:odan3240:20161202135845j:plain いなり寿司をたくさん食べたし賞味期限も先の方だったので後で食べた.
トーナメントの隣の席はpop_left さんで,2年前のRUPCで会ったことを覚えられていて感動しただけでなく,

こんなことまで言われてとても嬉しくなった.

Round1

A問題とB問題の両方に目を通す.部分点的にB問題の方が簡単だと思い400点ぐらい取れそうなDPを書き始めるもバグる.気づいた時には終了10分前になっていて,もっと低い部分点を取りに行こうとするも,うまくコードが書けず死亡.朝から太陽を生やした.去年の朝プロもそうだったけど朝は弱いらしい(?)

Round2以降

和エリアに移動してStoneDotさんとゆっくり問題を解いた.コンテストの間にまーすさんが来てテンプレートにINFは含めないほうがいいなどの有り難いお言葉をいただいた.
トーナメントのシールはRoundを通過するごとにもらえるらしく,それらをすべて組み合わせるとCode Festivalのロゴになってかっこいいと思った.

お昼

お腹が満腹気味だったが,"まい泉のとんかつ"というワードに勝てずトンカツ弁当を選んでしまう.
f:id:odan3240:20161202141333j:plain きついきつい言いながらも完食できた.
それと海外勢がお箸を使ってお弁当を食べていたことに驚いた.

LT

きゅうりさんが芸人していた.途中から見たので後で公開されると嬉しいなあ

挑戦状

今年も乱数で生成した色のRGB値を答える問題や,公式サイトの間違い探しなどへんてこな問題が多くてずっと笑い続けた.脳内で世界地図渡り歩けるのすごい.

リレー

去年は薄いピンク色だったけど今年は濃いピンク色だった.大学に来ていくか迷う.
本選の順位的にD問題を担当した.D問題は全探索するだけの簡単な問題だったが,チーム戦であることの緊張からかタイピングする手が震えていた.その結果配列の添字をtypoしていて一発AC出来ず,レプトンさんにもっと良い解法を教えてもらいそれでACした.
その後は他の人の担当している問題を一緒に考えて嘘解法を生やしたりして足を引っ張ってしまった.

表彰

ずっと立っていたせいか,身体がしんどくなったので地面に座って聞いていた.最近こういうことが多いので老いを感じる.
今年はサブイベント(?)に体力測定が追加されていたけど,これも何かデータ解析して発表したりするのかなと思った.体力測定は,中学の頃運動部なのに体力測定で学年最下位を取るレベルで運動は苦手なので上位は狙えないだろうし,大学の体力測定で腰を痛めたことがあったので考え軽めにやった.

閉会式

去年と同じく集合写真を撮った.
集合写真のために整列している時去年のことをふと思い出してしまい,あれからもう1年なのかと時間の速さを感じた.

帰路

NAIST勢の方と品川まで一緒に帰った.

終わりに

コンテストだけでなくサブイベントも楽しい大会でした. 今年は大学からは自分ひとりしか決勝に参加できなかったけど,来年も開催されるなら他の人と一緒に行きたいなあと思いました.
!!弊学の競技プログラミングチームは火曜5限と金曜5限に活動しているので興味ある人はぜひ声をかけてください!!

3日目はkeyakkoさんの「使用済Androidを適当にサーバ化して活用」です.楽しみですね!

ICPC2016国内予選参加記

チーム名lower_boundで参加して3完70位ぐらいでした
勝てなかった

チーム

3回生の自分と4回生の2人チームで参加した.4回生のうちの1人は去年一緒にアジア地区大会に行った人で今年も行けたらいいなあとか考えてた

本番

A問題

ぱっと見で簡単で先輩に投げた.すぐにACしてた.

B問題

よく読んでないけど先輩に投げた.入力を逐一読みながら処理を書いてたみたいで,全ての入力を読み終わる前に次のケースの入力を読みに行っていたせいで,バグってたらしい.一緒にソースコード読んで間違いを指摘してACした.

C問題

C問題を担当する予定だったのでまず読む.サンプルに最大ケース書いてて親切だと思った.サンプルの解釈を図に起こしていたら篩ぽいことに気付いた.横で先輩に書いてるコードが正しいかその都度確認してもらいながらコーディングした.すぐにコードが完成してACした.

gist.github.com

D問題

DPかな?状態をどう持つんだろう??みたいなことを相談しあってた.「数列の添字が2で割り切れるかどうかで2部グラフを作って,一番大きな完全マッチングを取り除いていけばいい」と考えて,実装したけどWAでつらくなる.最後まで反例あるのかなとか言い合ってたけど思いつかなくてコンテストが終了した.通した人の解法を聞くと,一番大きな完全マッチングを取り除くのが良い選択だというのが嘘だったみたい

感想

去年は最下位で通過できて,今年もと意気込んでたけどダメだった.ICPCは3年目だけどいつまで経ってもD以降が解けないし,TopCoderでDiv1に上がれないしでつらい.演習不足って言われれば確かにそうで何も言えないんだけど,来年に向けてどんな練習をすればいいんだろう...
あと,うちの大学からは4チーム参加して全てのチームが1完以上出来たのは良かったと思う.特に1回生だけのチームもあったし0完チームが出るのではと不安だった.

pydot3を使おうとしたらコケた

www.cl.ecei.tohoku.ac.jpをやっていてpydotを使う必要があったのでインストールしたけどうまく動いてくれなかった.いじってたら動作するようになったのでそれのメモ
他の環境ではどうなるかわかりません

Pythonのバージョン

Python 3.4.1 :: Anaconda 2.1.0 (x86_64)

インストール(python3系ではpydot3らしい)

pip install pydot3

サンプルソース

import pydot

edges=[('root', '日本語'), ('root', 'Latin'), ('root' , 'English'), ('Latin', 'English')]
g = pydot.graph_from_edges(edges)
g.write_jpeg('graph_from_edges_dot.jpg', prog='dot') 

まず最初に出るエラーはこれ

AttributeError: 'module' object has no attribute 'graph_from_edges'

import pydot# import pydot.pydot as pydotに書き換えるとこのエラーは消える

次に出るエラーはこれ

Couldn't import dot_parser, loading of dot files will not be possible.

site-packages/pydot/pydot.pyの32行目のException の中身をprintしてみるとcannot import name 'pydot'らしい
site-packages/pydot/dot_parser.pyfrom . import pydotimport pydotに書き換えるとこのエラーは消える

これでもまだ動作しなくてcannot import name 'Upcase'と言われる
Resolved #1 by jthomas8 · Pull Request #2 · log0/pydot3 · GitHub を参考にUpcaseupcaseTokensに書き換える

これで動作するようになる
site-packages/pydot/dot_parser.pyの方は from . import dot_parserのままでエラー吐かないのよくわからない
あとこのエラーの原因はpydot3の__init__.pyに何も書かれていないからだと思うけど,pythonのmoduleについて詳しくないから落ち着いたら勉強してそっち方向での解決策を探したい

オセロ3

そろそろまともな評価関数を作成しようと考えてリバーシの評価関数の最適化を読んで最急降下法の実装をしたけど,どこか実装がバグってるのか解が発散して困っていた.
最急降下法の練習にともうちょっと簡単な問題を設定してそれを解いてみようと考えて解いてみた.

問題

区間 [0, 2 \pi]を等分するM個の点 x_1, x_2, ..., x_M を取り,関数 \displaystyle f(\vec{w}) = \sum_{i=0}^{M} {(\sin(x_i) - \sum_{j=1}^{N} w_j {x_i}^j)}^2を最小化するベクトル \vec{w}を求める.
つまり,sinと多項式の和との差の二乗を最小にする係数を求めることになる.

最急降下法

pdfの式変形に従うと, \displaystyle  r_i = \sin(x_i) -\sum_{j=1}^{N} w_j {x_i}^jとすると  \displaystyle  \frac{\partial f}{\partial w_j} = -2 \sum_{i=1}^{M} r_i {x_i}^jになって,更新の式は \displaystyle w_j^{(k+1)} = w_j^{(k)} + 2 \alpha \sum_{i=1}^{M} r_i {x_i}^jになる.
実際に実装して,取る点の数と多項式の次数を調整してどの程度近似出来るかデータを取ってみた. f:id:odan3240:20160421115240p:plain
縦軸が誤差の値,横軸が次数,各グラフは点を何個取ったか.表示されていないのは結果がNaNになった部分.
次数が8辺りで誤差が改善されなくなっているのと,点の数(学習に使うデータの数)が増えるとNaNに発散しているのがわかる.
オセロの評価関数のために書いた最急降下法の解が発散したのは学習データを用意しすぎたのが原因なのかな.

実装したコード
github.com

追記

学習率 \alphaをデータの個数で割って正規化してやらないとダメで,その処理が抜けてました. f:id:odan3240:20160422094440p:plain

自作クラスをunordered_mapに突っ込む

自作クラスをunordered_mapに突っ込むには、std::hashを特殊化してそのクラスにoperator==が定義されていないといけません。
operator==の定義はメンバ変数同士が等価か調べればいいとして、std::hashを特殊化する時にハッシュ値をどう生成すればいいのか問題になると思います。上手にハッシュ値を生成してやらないと効率の悪いunordered_mapになってしまいます。

boostにはこれに対するhash_combine(size_t & seed, T const& v);という解決策があるのですが、C++の標準ライブラリには入っていないようです。ググるとこの関数の実装がヒットして次のようになってます。
Reference - 1.55.0
まあこれを自作クラスのハッシュ関数に実装すればいいのです。 ちなみに0x9e3779b9という数値の理由は2^32 / phi = 0x9e3779b9みたいです

stackoverflow.com

#include <bits/stdc++.h>
using namespace std;

struct Hoge {
    int n;
    double d;
};
bool operator==(const Hoge &lhs, const Hoge &rhs) {
    return lhs.n == rhs.n && lhs.d == rhs.d;
}
namespace std {
template <>
struct hash<Hoge> {
    size_t operator()(const Hoge &hoge) const {
        size_t seed = 0;
        auto n_hash = hash<int>()(hoge.n);
        auto d_hash = hash<double>()(hoge.d);

        seed ^= n_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= d_hash + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};
    
}
int main() {
    unordered_map<Hoge,int> mp;
    
    mp[Hoge{0,1.0}]=1;
    return 0;
}

RUPC2016参加記

一日目

去年もチームを組んだomuさんと、くじ引きで引いたnisshyさんと参加した
まずA問題を担当した。一番端に取り付けるのが効率いいしそうしようと考えて実装して通したけど、解説で入力のたびにその反対側に同じ重さだけ取り付ければ良いと聞いて自分の頭の悪さにつらくなった。
D問題で最大値の最小化だし二分探索?何か良い貪欲があるのかな?とか考えていたらomuさんがDPだと言って通したり、E問題でわからないなあこれって考えていたらnisshyさんがメモ化再帰で深さがO(\log N)だから大丈夫だと言って通していたりしているのを横で座っているだけだった。
チームとしてはA,B,C,D,Eの5完だった
ほぼ座ってるだけだった...

二日目

まずB問題を担当した。場合分けミスりそう、サンプルケースが弱いから自分でケースを作らないとダメ、添字が0と1逆になってたとかで時間がかかり30分後ぐらいにACした。
D問題の場合分けのチェックをチームの人と考えたあとF問題を通してるチームが多いからF問題を考えると解法が思いつく。実装して提出するけどWA.チームの人に反転処理が間違ってることを指摘されて修正してAC.算数力がなくてつらい。E問題について考えていたらいつの間にかG問題が通っていてすげーってなる。
残りの時間でE問題とH問題を考えていたけど通せずに終わり。
チームとしてはA,B,C,D,F,Gの6完だった
D問題とかH問題はチーム内で会話しながら解法を詰めていったけどこれは初めての経験で新鮮だった。

三日目

まずB問題を担当した。考えても2重ループになる、約数の個数っていくつだっけ?ローリングハッシュを使えば通せそう?とか考えて疑いながらも実装して投げると通った。
F問題はデータ構造ぽいけど「きっちり」をどう判定するんだって考えていたら、D問題を通した後のkzyKTさんが真ん中で折り返せば良いと言ってすごいなあと感心する。F問題を実装しているのを観察して終了間際にAC. チームとしてはA,B,D,Fの4完だった
真ん中で折り返すって発想が出ないのが自分の弱いところだと認識できた。がんばりたい...

おわりに

チーム戦は個人戦とは違う面白さがあったり強い人の思想を知れたりして楽しかったです。コンテスト終了後も競プロについて話していてモチベが上がりました。
あと最近競プロ始めた学科の人を連れてきたんだけど彼も刺激になったらしくてよかった。
運営や作問の方々ありがとうございました。