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完だった
真ん中で折り返すって発想が出ないのが自分の弱いところだと認識できた。がんばりたい...

おわりに

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

オセロAI2

進捗メモ。続くかな

置換表のバグが取れた。バグの原因は同じ局面かつ次に打つ色が異なる場合を同じ状態として持っていたため。このような状態で置換表がバグると考えてはいたけど、実際には起こりえないとして無視していたら実際に発生したっていう。去年の本番直前にバグに気付けてほんとよかった。

Boardの着手可能手の列挙と反転処理の実装にSIMD命令を使ってみたがあまり速くはならなかった。使い方が間違ってるのか、これが普通なのか分からない。FFO40でしかベンチマーク計測してないけど
具体的には、着手可能手の列挙の部分に手を加えると2秒程度の高速化、反転処理の部分に手を加えるとむしろ遅くなった。反転処理の部分は条件分岐を消すために必ず16回ループを回すようにしているのが原因で、SIMD命令を使わない方が速い結果になったんだろうと考えられるけど、着手可能手の列挙の部分は原因不明。

あと、SIMD命令で条件condが真ならbを、偽ならcをaに代入するには以下のようにすればいい

a = (b & cond) | (c & cond)

maskを使えば条件分岐を消せることを知った時は感動した