更新日時で差をつけろ

むしろ差をつけられている

7/2: 3AC, IOLを調べた

テストn日目。世界史です。まずまずかな。作文課題を潰さないと…

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder

B: P-CASカードと高橋君 - AtCoder Regular Contest 005 | AtCoder

ARC 027 B: 大事な数なのでZ回書きまLた。(Union-Find) - 更新日時で差をつけろ

今日は3ACです。400点問題だし、多少はね？

Union-Findを考えていたら頭痛が引いたのでよかったです。でも夕方まで買い物に行く気になりませんでした。

なんとなく国際言語学オリンピック(IOL)について調べていると、過去問が公開されていたので見てみました。
去年の最後の問題をすこし見て面白かったのでコンビニで印刷して1時間ほどトライしました。
たまたまその問題は頑張れば解けそう、というレベルだったのですが、
他の問題は脳みそがひっくり返りそうなぐらい難しかったです(そりゃそうだ)。

言語学の練習ってどこでできるんだろう？と思い、見つけたサイトを貼っておきます。
どのサイトも「前提知識はいらないよ！」「楽しいよ！」とアピールしている気がする…

North American Computational Linguistics Olympiad
北アメリカの言語学の地方大会の問題集です。

International Linguistics Olympiad - Sample Problems IOLの初心者向けの練習問題

How should one start preparing for the International Olympiad in Linguistics (IOL)? - Quora 過去のIOL銅メダリストの回答がついたQuoraの質問。リンクがペタペタ貼ってあります。

ARC 027 B: 大事な数なのでZ回書きまLた。(Union-Find)

競プロ

解説見ずにUnion-Findの問題とけたの初めてでうれしい〜〜〜 他の問題ももうちょっと粘るようにしよう。

訪問済み(この問題だと"計算済み"？)のグループをvisitedで管理するときに誤って文字そのもの(グループの要素)を入れてしまい、2WA。

7
AABCDEF
ABCDEFG

のようなときに誤った答えを出してしまう。

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
const ll INF = 1e9;

// see: http://dai1741.github.io/maximum-algo-2012/docs/minimum-spanning-tree/
struct UnionFind {
    vector<int> par;
    vector<int> size;

    UnionFind(int n) : par(n), size(n, 1) {
        for(int i = 0; i < n; i++) par[i] = i;
    }

    int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void unite(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py) return;
        if (size[px] < size[py]) swap(px, py);

        par[py] = px;
        size[px] += size[py];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int N;
    string s, t;
    cin >> N >> s >> t;
    UnionFind uf(36); // alphabet 26文字 + 数字(0~9) 10文字

    for (int i = 0; i < N; i++) {
        int spos = isalpha(s[i]) ? s[i] - 'A' + 10 : s[i] - '0';
        int tpos = isalpha(t[i]) ? t[i] - 'A' + 10 : t[i] - '0';

        uf.unite(spos, tpos);
    }

    ll ans = 1;
    vector<bool> visited(36);
    for (int i = 0; i < N; i++) {
        int spos = isalpha(s[i]) ? s[i] - 'A' + 10 : s[i] - '0';
        int tpos = isalpha(t[i]) ? t[i] - 'A' + 10 : t[i] - '0';
        if (visited[uf.find(spos)] && visited[uf.find(tpos)]) continue;
        visited[uf.find(spos)] = true;
        visited[uf.find(tpos)] = true; // ここをvisited[tpos]にしてた

        vector<int> sames;
        for (char i = 0; i < 10; i++) {
            if (uf.same(spos, i)) {
                sames.push_back(i);
            }
        }
        if (sames.size() == 0) {
            ans *= (i == 0) ? 9 : 10;
        } else {
            ans *= sames.size();
        }
    }

    cout << ans << endl;

    return 0;
}

IOIに出場された方、誰が誰だがさっぱりだけどすごいと思った(こなみ)。

ABC 041 D: 徒競走(bitDP)

トポロジカルソートの数え上げというのはわかったけど、bitDPの実装の仕方がわからなかった。

Submission #788045 - AtCoder Beginner Contest 041 | AtCoder
公式の解説と、この回答をベースに理解しました。
解説の数式と、コードをすべて日本語に書き換えて理解しました。自然言語は偉大だなあ

// bitDPを文系の脳みそで理解する男・実質文学科

#include <iostream>

using namespace std;
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    int g[N][N] = {};
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a][b] = 1;
    }

    ll dp[1<<N] = {};
    dp[0] = 1; // 空集合のときトポロジカルソートの方法は1つ
    for (int A = 0; A < (1<<N); A++) { // うさぎの集合Aを０から列挙 -> すべてのうさぎを使う場合まで積み上げていく
        for (int v = 0; v < N; v++) { // v = Aから取り除くうさぎを列挙
            // Aにvが含まれているならパス(vが「Aから取り除くうさぎ」にならないので)(含まれていないなら、A=S-{v}と言える)
            if (A>>v & 1) continue;
            bool f = true; // vは一番右にくるか?こないか?
            for (int k = 0; k < N; k++) { // 他のうさぎに対して
                // kがAに含まれていて、vからkに伸びる有向辺があれば、vは集合Aで一番右に来ない
                if ((A>>k & 1) && g[v][k] == 1) f = false;
            }
            if (f) dp[A | (1<<v)] += dp[A]; // 一番右にくるならA + {v} = Sの通り数に加える(これをN回行うので総和になる)
            // ORで加算ができる
        }
    }

    cout << dp[(1<<N) - 1] << endl;

    return 0;
}

7/19

日記

火曜日。なんだか起きるのがつらかったなあ。
起床のプロになるのは難しい。

C: 総和 - AtCoder Beginner Contest 037 | AtCoder
C: オセロ - AtCoder Beginner Contest 035 | AtCoder
今日は2ACです。CTFしたかったけど腹を冷房で痛めてしまって1時間半ほど動けませんでした。 白湯を飲んでゆっくり治しました。
以前は解けなかった問題なのですが、改めて見返してみると累積和・しゃくとり法であっさり解けました。放置ってやっぱり効果ありますよね。

C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder これもWAのまま放置していたのですが、やっと解説が理解できたので明日実装します。
そろそろD問題も始めて行こうかなと。アルゴリズムとデータ構造をもっと使いこなせるようにならないと^^;

UbuntuのポインタのスピードをxinputをつかってMacのそれに合わせました。速い方が使いやすい！
いい加減Sinatraの開発と競プロ/CTFでOSを切り替えるのもだるくなってきたので、試験が終わったら完全にUbuntuに開発環境を移そうかと考えています。
ただMySQL/MariaDBの環境設定のトラウマがあるので心配です…(VPS)

寮では部屋替え。幸いにも私の部屋は人の入れ替わりがありませんでした。

ELCASの選抜に行ってきた

京都大学のELCASの選抜に行ってきました。
朝早くに家を出て、吉田キャンパスで数学試験・化学の講義・宇宙望遠鏡の講義を受けました。

モバイルバッテリーを忘れてしまい、乗り換えなどいろいろ不便でした。
祇園祭と被っていたので日本人も外国人も多かったです。なんでこんな時期にするかなぁ…

数学試験は高校受験の知識でなんとか解きました。変なミスを犯してWAにならないと良いのですが…。
高専入ってから数学は三角関数、数と式、集合といった分野ばっかりだったので、久しぶりに三平方の定理とか使うと楽しかったです(楽しかったとは言ってない)。

化学の講義も宇宙望遠鏡の講義もおもしろかったです。これ聴きに来ただけでもよかった。うっかり内容書いたりしたらまずいかもしれないので辞めておきます。

帰りは京阪電車と新快速で立ちっぱなしでした。PCとカバンとリュックサックを持ちながらなので結構ツラかったです。

7/15, 7/16

日記

２日分まとめて…

7/15 Sat

こたまねぎさんの高校で開かれた競プロ講習会(初心者編)に行ってました〜。
メインの講習会はテスト期間ということで高専側からstopが入っちゃって><;
olphe さんともお会いすることができてよかったです。

なかなか思うように解けないのでうーん…

夜はARCでした。2完したかったけど、Dが木の問題で実装のしかたがわからず1完！(((
最後あきらめモードでEに手を出してみて、Eでもなんとかなりそうなことがわかったのはよかった。
C埋めを早く終わらせて、D埋めを進めないと(汗)…

7/16 Sun

午前は競プロ、午後はSinatraでバチャコンのシステムを実装していました。Sinatra楽しい。
昨日はあのまま寝てしまって放置していたD問題を通しました。
「最適な行動」って難しいなあ。

バチャコンシステム => GitHub - sei0o/WachaCon: AtCoderじゃなくてもバチャコンしたい！
鋭意製作中。
提出データ取得の定期処理をどのように書こうか迷っています。
クライアント側で問題名を取得するときにSOPを回避するために YQL を使ってみました。
ちょっと反則的な使い方の気もするけど便利。スクレイピングが捗ります。

昼はインターンする予定の会社の方とSkypeでお話。
外国から機械学習が得意な人が来ているそうで…プロコンの相談しようかなと画策しています^^;

slackを開こうとしてmacOSを起動した状態でcontrol(Superキー)を連打している自分がいました。ubuntuに毒されてきた(??)。

学校の課題は進捗0です。
明日からコード書く時間減らしていかないとなあ。

明日はELCASの試験だーーーーー
あ〜〜〜〜〜〜〜