第5回 mixi git challengeに参加してきました

mixi git challengeとはミクシィ・グループが主催するgitの使い方に関するコンテストです.twitterのフォロワーに元参加者の方から「勉強になってビールも飲めるぞ」と聞いていたので申し込みました.人が殺到すると抽選で決まるらしい? ブログを書くまでが遠足らしいので,参加記を書きます.

シール

Githubmixi git challengeに関するシールを貰いました.PCにペタペタ貼る人なのでこれはとても嬉しい. f:id:odan3240:20170130214842j:plain f:id:odan3240:20170130214852j:plain

ご飯

節分が近いということで巻き寿司が入ったお弁当が支給されました.寿司をカレーで近似した前回よりは,近似制度が高いと思いました.チームメンバーと社員の方とで楽しく食べました. f:id:odan3240:20170130212402j:plain

コンテストについて

2人チーム制で同じ関西からやってきた人とチームになりました.運営側がチームを指定しているので優しい.
コンテストに使われた問題については言及できないので,チーム体制についてちょっと書きます.うちのチームはわりといいチームワークが取れていたと思います.
最初に取り組む問題はあらかじめ決めておき,解けた人から順番に次の問題に取り掛かろうという方針でした.しかしコンテストが始まってみるとお互い最初の問題からハマってしまいました.そのため最初1時間は正の点数を取れないまま過ぎ,その時点では最下位でした.
流石に何かおかしいだろうと考え,取り組んでいる問題の概要や解答の方針を相手に伝え,お互いの担当する問題をスワップすることにしました.交換してみると相方がハマってたのが嘘みたいにスッと通すことができて,とても興奮しました.
人は深く集中するとそれと同時に視界も狭くなり,簡単なミスに気付かなくなってしまいます.しかしその時に誰かに相談したり,先入観のない他の人に取り組んでもらうことで,簡単なミスを回避できたのかなと思いました.チームメンバーは大事大事.
大きく出遅れたのは痛かったですが,「多くのチームが解いている問題は簡単だろう」「落としているチームが多い問題は何かハマる要素があるから回避しよう」,などとと順位表から難易度を推測して次に取り組む問題を決めていきました.お互い競プロ経験者だったので順位表から問題難易度を見積もることには慣れていた気がします.
後半の追い上げもあって最終的には11チーム中4位で終わることができました.欲を言えば最初にハマって溶かした1時間にもっと問題を解きたかったし,3位以上は表彰されるので最後に取り組んでいた問題を間に合わせたかったです.

懇親会

待ちに待ったビール f:id:odan3240:20170130214426j:plain おつまみ f:id:odan3240:20170130214451j:plain コンビニからそのまま持ってきたようなおでん f:id:odan3240:20170130214445j:plain

社員の方と沢山お話できました.懇親会含め社員さんから聞いた話で印象に残ったのは次の通りです.

  • イケイケな開発体制で開発している
  • ミクシィ・キャリア・チャレンジという社内で転職できる制度がある
  • mixiは業務時間内に行われる勉強会を主催できる

どれも自分には魅力的でした.

感想

最高のイベントでした.問題を流用している関係上1度参加すると次は参加できないのですが,記憶を消してまた参加したいと思ってしまうほどでした.問題入れ替わってまた参加できたりしないかな
これからは大学の人などに宣伝,布教していきたいと考えています.あと作問できたら学内でgit challengeを主催してみたいなとも思っています.

運営をしてくださったミクシィ・グループさん,ありがとうございました.

OIT Advent Calendar 2016について

この記事は,OIT Advent Calendar 2016を作成した経緯や思いなどを書くポエム的なものです.

www.adventar.org

OIT Advent Calendar

作成するまで

Advent Calendarという文化は数年前から認知しており,いつか自分でも記事を書いてみたいと思っていました.
そんな中ある日,OITのAdvent Calendarをやれば面白いんじゃないか?と思い立ちました.

数日後,他のAdvent Calendarが作成され始めているのをTLで観察し,流れに任せて自分も作っちゃえと思い作成しました.

参加者について

11月頭はカレンダーを作ったものの中々参加者が集まらず,こんな気持ちになってました.

裏では大学の同学年や先輩後輩だけでなく,OBの方や先生に記事を書いて貰えないかと頼み込みしていました.そのおかげ(?)か12月が始まった頃には25日中13日が埋まっていました.
Advent Calendarが始まってみると公開された記事を読んだ人がカレンダーに登録したことや,僕の知らないところで勧誘してもらったこともあってあっという間にカレンダーの日付が埋まりました.最初の頃の不安はするだけ無駄だったんだと前向きになれました.

結果的に在校生だけでなく,OBや先生といった幅広い人に参加して貰えました.嬉しい.

作成した経緯

大きく分けて以下の二つがあります.

アウトプットする場が欲しかった

アウトプットする時に情報をまとめることでそれについての理解が更に深まるだけでなく,文章を書く能力の向上や情報を発信することで自分のアピールに繋がると言われています.ただ自分は,何か締め切りや目標を設定しないと動けない人間なので,Advent Calendar を良いきっかけにしようと考えて作成しました.記事の内容が非技術系でもオッケーにしたのはこのためでもあります.

同じ大学の人をもっと知りたかった

普段大学での行動範囲は狭いため知り合いは少なく,もっと大学の人やその人の考え,スキルなどを知りたいと思っていました.
そのため,自分の知らない人がカレンダーに登録することを作成当初から願っていたのですが,無事それも達成することが出来ました

最後に

僕がOITに在籍する限りはカレンダーを作成すると思うので,今年記事を書いてくださった人もそうでない人も,来年参加していただけるとうれしいです.

良いお年を

STLの練習問題

この記事は,Competitive Programming (その2) Advent Calendar 2016 - Adventar の13日目の記事です.

www.adventar.org

大学では競技プログラミングの勉強会を週2回のペースで開催しており,先週の勉強会のテーマはC++STLでした.
アルゴリズムの練習に良さそうな問題集は AOJ ジャンル分けメモ - ひよっこプログラマのプログラミング頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏 がありますが,STLの練習に良さそうな問題を集めたブログは見つかりませんでした*1

そこで自分のソースコードgrepしてSTLの練習に良さそうな問題をピックアップしました*2.今年のKUPCの懇親会でYazatenさんとSTLの練習になるような問題がなかなか見つからないという話題もあったので公開します(必要そうなSTLの部分は白文字で書いています).

AOJ

回文数

URL: Palindromic Number | Aizu Online Judge
必要そうなSTL: string

Princess's Marriage

URL: Princess's Marriage | Aizu Online Judge
必要そうなSTL: pair, sort

Kagisys

URL: Kagisys | Aizu Online Judge
必要そうなSTL: set

列車の編成パートII

URL: Organize Your Train part II | Aizu Online Judge
必要そうなSTL: set,string

英語の文章

URL: 単語の出現頻度 | Aizu Online Judge
必要そうなSTL: map

入力候補

URL: Input Candidates | Aizu Online Judge
必要そうなSTL: map

Atcoder

高橋君とパスワード

URL: B: 高橋君とパスワード - AtCoder Beginner Contest 032 | AtCoder
必要そうなSTL: set,string

座圧

URL: C: 座圧 - AtCoder Beginner Contest 036 | AtCoder
必要そうなSTL: map

(問題数が圧倒的に少ない...)

*1:誰か知っていたら教えてほしいです

*2:string,map,setを主に集めた

オセロ大会のこと

この記事は,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について詳しくないから落ち着いたら勉強してそっち方向での解決策を探したい