IOLの練習問題(Intermediate Level): Basque Numbers

日本語版が入ってないので書きます(なんとなく)。
パット見意味不明でも少しずつわかってきて面白かった。

IOLの練習問題はここからゲットできます。
International Linguistics Olympiad - Sample Problems

数字を当てる問題です。問題文が1行なので日本人にやさしい。

実はこの問題、

bost × zazpi = hogeita hama
bost zazpi × bederatzi = hirurogeita hiru

は

bost × zazpi = hogeita hama bost
zazpi × bederatzi = hirurogeita hiru

と読み替えないと公式解答とつじつまが合いません。改行の場所間違えちゃったのかなあ
無論私の勘違いの可能性もありますが…ただバスク語を調べてもhogeita hamaなんて数ないんですよね…

解法

原文曰く、Basque numbers are identified straightforwardly、つまり やるだけ とのことです。
えっ？

文字を変数に見立てて変形していきました。こうすれば1番めの空欄はすぐに埋まります。

bi * bost = hamar, bi * hamar = hogei -> bi * bi * bost = hogei
lau * bost = 空欄1, bi * bi = lau -> bi * bi * bost = 空欄1

したがって空欄1 = hogeiといった具合です。

hogeita bostはhogei + bostと予想し、

「hiru * hamar = hogeita hamar」
hiru * hamar = hogei + hamar
 = bi * bi * bost + bi * bost
 = bi * bost * (bi + 1) = hamar * (bi + 1)
hiru = bi + 1

「bost * bost = hogeita bost」
bost * bost = hogei + bost
 = bi * bi * bost + bost
 = bost(bi*bi+1)
bost = bi * bi + 1

bi * bi = lauより、biは0,1ではないとわかります(bi * bi = biとならないので)。 また、lauは単語の短さから、1ケタの数字と推測しました。
lau <= 9となるので、biは2か3と絞り込めます。
特に理由はないのですが、bi = 2として先程の式に代入すると、hamar = 10, hogei = 20, bost = 5, zazpi = 7, lau = 4, hiru = 3, bederatzi = 9とわかります。
あえて理由を考えるなら、bi = 3とすると、zazpiが 12 という微妙すぎる数字になるからではないでしょうか(zazpi * hamar = hirurogeita hamarより)。さすがのバスク話者もここまでしないだろ(((
ここで空欄2 * hamar = laurogeita(=lau * hogeita) + hamarより、空欄2 = bederatziと出ます(手抜き)。

あとは数字を当てはめるだけです。
なかなか変な解説になってしまいました。 冒頭の問題のミスっぽいもののせいでbederatziがなにかわからず撃沈しました….

ARC 035 B: アットコーダー王国のコンテスト事情

ARC過去問の難易度レビュー - ヘクトのメモ
hecさんの記事を参考にできそうなものから進めています。

B: アットコーダー王国のコンテスト事情 - AtCoder Regular Contest 035 | AtCoder

短い時間で解ける問題から解くのが最もコンテストペナルティが少なくなります。
解くのにかかる時間を昇順にソートして、貪欲法っぽく(別の言い方をするなら「普通に」)時間を足していきます。

解き方の順は以下のように通り数をかけるだけです。(入力例2を例にすると)

1minの問題 1min 2min 2min 2min (最適な解く順番)
<---- 2! -----> <---- 3! ---->

2! * 3! = 2 * 6 = 12

このとき階乗を求める関数で随時modを取っていかないとオーバーフローで計算できなくなります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll modfact(ll n) { // 階乗して1e9+7で割ったあまりを計算
    if (n <= 1) return 1;
    return (n * modfact(n - 1)) % MOD;
}

int main() {
    int N;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];

    sort(T.begin(), T.end());

    ll ansMin = 0; // 求める最小のコンテストペナルティ
    ll ansWays = 1; // 求める通り数
    ll sum = 0;
    int prev = T[0];
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (prev == T[i]) {
            cnt++;
        } else {
            ansWays *= modfact(cnt);
            ansWays %= MOD;
            cnt = 1;
        }
        sum += T[i];
        ansMin += sum;
        prev = T[i];
    }
    if (cnt > 0) {
        ansWays *= modfact(cnt);
        ansWays %= MOD;
    }

    cout << ansMin << endl;
    cout << ansWays << endl;

    return 0;
}

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とカバンとリュックサックを持ちながらなので結構ツラかったです。