Google Hash Code 2021 Online Qualifications 参加記

2/26 2:30-6:30 (日本時間) に開催された Google Hash Code 2021 に参加しました。

codingcompetitions.withgoogle.com

Hash Code への参加は初めてでしたが、とても楽しかったです。

結果は 4510位/9004チーム中でした。同じ点数のチームがたくさんいたのできっと同じ解法だったのでしょう。

Google Hash Code とは

Google Code Jam と同じく、Google 主催のプログラミングコンテストです。 個人戦のアルゴ系のコンテストである Code Jam とは異なり、チーム戦の短時間マラソンマッチです。 1つの問題と複数のテストケースが示され、2-4人のチームでできるだけ高いスコアを目指します。 あまり他のコンテストでは見ない形式で、今回参加してみても独特の面白さを感じました。

これでせめてもう少し早い時間帯の開催だと嬉しいのですが、世界中に参加者がいることを考えるとあまり我儘も言えないですね……。

Google Hash Code についてもう少し知りたい方は、公式サイトや診断人さんの記事を読んでみてください。 shindannin.hatenadiary.com

チームについて

FORTIUS というチーム名で、matsu7874 さん との2人チームでした。

言語は matsu7874 さん製ソルバーが Rust、Noimin 製ソルバーが C++、その他共用スクリプトに Python、という感じに特に統一はしていないのですが、統一したほうが良かったのかもしれないと思いました (後述) 。

問題について

道路と交差点、車とその辿るべき経路が与えられます。

各交差点の信号機の切り替えスケジュールを指定して、できるだけ多くの車ができるだけ早く目的の経路を辿り切れるようにするという問題でした。

(問題文 pdf より引用)

問題の制約は

• シミュレーションの最大秒数 $D \leq 10^4$

• 交差点の数 $D \leq 10^5$

• 道路の数 $S \leq 10^5$

• 車の数 $V \leq 10^3$

など、何も考えずにシミュレートしていると現実的な時間で計算が終わらなくなりそうなものになっていました。 マラソン形式のコンテストではありますが、そういう意味ではアルゴっぽい面白さもあったように思います。

実際に解いてみたい！ という方はジャッジシステムのページから問題文がダウンロードできます。

競技前・競技中の動き

前々日〜当日 1:30

リポジトリを用意しました。

提出物はソースコードの zip および各テストケースに対する出力であるということはわかっていたので、複数のソルバーの中で各テストケースに対する最高スコアの出力を判定し、ソースコードを zip に固めるスクリプトを書きました。

これらの準備は matsu7874 さんと私の両方で行いましたが、個人的な準備としてはコンビニで夜食とモンスターを買って、帰宅後に仮眠を取りました。

2:30

問題文はまだ公開されていません。事前準備として matsu7874 さんとGoogle Meet の通話を繋ぎ、Google による配信を見て問題が公開されるのを待ちました。私が英語が得意ではありませんが、 Google Map がどうこうとか言っていたように聞こえたのでもしかしたらグラフ系の問題か？ なんて思ったり思わなかったりしました。

2:45

問題文が公開されました。私がリポジトリにテストケースを追加している間、matsu7874 さんが問題文を読んでくださっていました。

テストケースを push 後に合流したのですが、このときに matsu7874 さんが問題の概要を簡潔に口頭で伝えてくださったので私が問題を読むのはその続きからでよく、効率が良かったです。

問題文を読んで認識を合わせたあと、最初はmatsu7874 さんがビジュアライザを、私がスコア計算のスクリプトを書いていくことになりました。

5:00 頃

この辺りでスコア計算が完成し、時間も時間なのでいい加減 solver を書き始めないとな〜と焦りだしました。

書くのが簡単そうでそれなりのスコアが出そうな、「各交差点の全部の信号を1秒ずつ青にする」solver を書いてみることにしました。

5:30 頃

「各交差点の全部の信号を1秒ずつ青にする」solver での解を提出しました。

スコアは以下の通り。

• A – An example 1,001 points
• B – By the ocean 4,565,642 points
• C – Checkmate 1,231,878 points
• D – Daily commute 969,685 points
• E – Etoile 661,797 points
• F – Forever jammed 455,737 points

ここで私たちは重大な事実に気付いてしまいます。ビジュアライザは用意されていたのです。

これはやってしまいました。もちろん、リッチなビジュアライザではないので自前のビジュアライザを用意すると言う手もあるにはあります。ただ私たちは2人チームであり、ビジュアライザが一応用意されているとなると、ビジュアライザの優先度は下がります。例えば私が思いついた最初の解法以外のシンプルな解法のソルバーをお願いするなどしておいたほうがよほど matsu7874 さんの実装力が活かせるというものでした……。

残り時間はあと1時間を切りました。ここで 0 から新しいソルバーを作るのは難しいので、最初に提出したソルバーをそれぞれの方針で改良することにしましいた。

6:30

最後の悪あがきでテストケース A のスコアのみが上がりましたが、そもそもテストケース A は小さなテストケースなので全体のスコアにはあまり寄与せず。

楽しかったのですが、まだまだ不完全燃焼なまま競技時間が終わってしまいました。4時間はあまりに短く、必死だったので、コンビニで買っておいた 500ml 缶モンスターがほとんど消費されていませんでした (ただしそのモンスターはその日の仕事中に大いに役に立ちました) 。

良かった点

初参加でなかなか勝手が掴めませんでしたが、やって良かったな思ったこともいくつかありました。

• スコア計算・ソースコード圧縮を行うスクリプトを事前に用意しておいたこと。
• チームで通話を繋ぎながら問題文を読み、認識を合わせられたこと。私は英語の問題文を読むときに誤読しがちなので、認識を合わせることで安心してすこけいさんを書き始めることができました。
• 過去の参加者のブログを読みながら当日に有効になりうる立ち回りについて勉強していたこと。 (まだまだ情報の少ないコンテストのはずですが、日本人の記事は結構簡単に見つかってすごかったです)

反省点

• 問題文を読み終わったら、とりあえず早めに提出をしてみるべきでした。提出していればもっと早くビジュアライザの存在に気づけたでしょうし、各テストケースで出せるスコアのスケールの違いについても考えやすかったはず。
• 言語は合わせたほうが良かったかもしれません。スコア計算部分は焼きなまし等を行うときに必要になるので、使いまわせたほうが便利です。(チーム全員が化物みたいな実装力を持っていれば別ですが少なくとも私は違うので……)
• 最大スコアを取るソルバーの出力を判定するスクリプトを書きましたが、なくても良かったかもしれません。チームのスコアは「各テストケースに対するスコアの最大値」の総和なので、最新の提出であるテストケースについてのスコアが下がったところで最終スコアには影響しません。今回はソルバーを書く時間が十分に取れなかったのがスコアを伸ばしきれかった要因なので、とりあえず各テストケースに対する出力を出して提出して、提出回数 (≒書く solver の種類数）を増やすべきでした。このあたりは来年ルールが変わったらまた違うかもしれませんが。

おわりに

個人的には、ICFPC のようなプロコン総合格闘技みを残しつつ、 ICFPC よりもアルゴの人にとっつきやすくなっていてとても楽しいコンテストでした。

来年度もスケジュールと睡眠の調整を頑張って、なんとか出たいですね。

New Year Contest 2015 E - ひも

問題: E - ひも

問題概要

$N ( \leq 10^5)$ 個の区別できるノードがある。 $i (1 \leq i \leq N)$ 番目のノードの次数が $a_i (1 \leq a_i \leq 3) $であり、すべてのノードが直接または間接的に辺で繋がれており、かつ辺が全体で $N-1$ 本となるようなグラフの数を $10^9+7$ で割った余りを求めよ。

解法概要

$N$ 個のノード、$N-1$ 本の辺、それらがすべて繋がっている、ということは問題の条件通りに作ったグラフは木になる。また、辺は $N-1$ 本だから、ノードの次数の合計は $2 (N-1) $ となる。

したがって、 $\sum_{i=1}^N a_i \neq 2 (N-1)$ の場合答えは 0 である。

以下は $\sum_{i=1}^N a_i = 2 (N-1)$ の場合のみを考える。

上図は Sample Input 1 を図にしたものである。

木を作る操作の言い換え

これをもとに考えると、木を作る操作は次のように言い換えられる。

1. 「残りの腕が 1 本のパーツ」と「残りの腕が 2,3 本のパーツ」を1つずつ選んで繋ぐ。
2. 1 の操作を $N-2$ 回繰り返す。
3. 「残りの腕が 2, 3 本のノード」がなくなるので、最後に「残りの腕が 1 本のパーツ」同士を繋ぐ。

1 について、残りのパーツ数の合計が 3 以上のうちは次のように「残りの腕が 1 本のパーツ」同士を繋げることはできない。これらを繋げてしまうと、今後勝手に腕を増やさない限り $N$ 個のノードからなる木を作ることができなくなってしまう。

元々「残りの腕が 2,3 本のパーツ」だったものが、「残りの腕が 1 本のパーツ」と繋げることで残りの腕が 1 本になったら、「残りの腕が 1 本のパーツ」に移動する。

元々の腕が3本あっても、「残りの腕が 1 本のパーツ」と繋ぐ対象に2回選ばれることで「残りの腕が 1 本のパーツ」になれる。

最後 ($N-1$ 回目の操作) は「残りの腕が1本のパーツ」だけになるので、この2つを繋ぐことになる。 (もし $N-1$ 回目まで残りの腕が2本以上あるパーツが残っているとすると、多重辺や自己ループを作らない限り各ノードの次数の制約を満たすことはできない。しかし多重辺や自己ループを入れようとすると、今度は辺の数が $N-1$ を超えてしまう)

重複を作らないようにする

しかし前の節での木の作り方をそのまま式にして数えようと思ったときに、同じ木を2回以上数えてしまう可能性がある。例えば、

• ノード 1 とノード 3 を繋ぐ
• ノード 4 とノード 5 を繋ぐ

これらの操作はどちらを先に実行しても結果は同じである。

そこで、操作の対象となるパーツのうち「残りの腕が 1 本のパーツ」の選び方を「その時点で最もノード番号の小さいもの (複数ノードからなるパーツの場合は残っている腕を持つノードの番号が最も小さいもの) 」と固定する。操作の順番が自由だと都合が悪いときに、順番を固定しても一般性が失われないものについて「条件を満たすものの中から最も添字の小さいもの」から操作するようにすると考えやすくなる問題は競プロでよくある。

すると、「残りの腕が 2,3 本のパーツ」の選び方の順番は $(N-2)!$ 通りになる。 ($N-1$ 回目の操作以外は「残りの腕が 1 本のパーツ」同士をくっつけることはできないので $N-2$)

しかし、「残りの腕が 1 本のパーツ」の選び方を固定してもまだ重複の可能性がある。

腕が3本あるパーツがある場合、出来上がる木の根を適当に (例えばノード 1 に) 固定したとしても、左の子と右の子を入れ替えたような木をどちらもカウントしてしまう。 今回作る木は頂点こそ区別するが、辺を区別しないので、それらは 1 つとしてカウントしなければならない。 そのため、腕が3本あるパーツの数を $t$ として $2^t$ で割っておく必要がある。

したがって、今回求めるべきグラフの数は

$$\frac{(N-2)!}{2^t}$$

である。ただし $t$ は $a_i = 3$ となる $i$ の数である。

ソースコード

#include <iostream>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1[f:id:noimin:20201209221656p:plain]000000007;
constexpr int N_MAX = 100000;

ll fact[N_MAX+1], rfact[N_MAX+1];

ll modpow(ll a, ll p) {
    ll ret = 1LL;
    while(p) {
        if(p & 1) {
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        p >>= 1;
    }
    return ret;
}

void init_fact(ll n) {
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(ll i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * i) % MOD;
        rfact[i] = modpow(fact[i], MOD-2);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    init_fact(n);
    ll a[n], s = 0;
    for(int i=0;i<n;++i) {
        cin >> a[i];
        s += a[i];
    }
    if(s != 2 * (n-1)) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = fact[n-2];
    for(int i=0;i<n;++i) {
        ans *= rfact[a[i]-1];
        ans %= MOD;
    }

    cout << ans << endl;
}

所感

この答えの式はPrüfer sequence として有名らしい。 (参考: New Year Contest 2015 E問題 - ひも - ゲームにっき（仮）別館（仮）)

AtCoder Regular Contest 109 D - く

問題: D - L

解説: 公式解説

問題概要

二次元の平面上の点 $(0, 0), (0, 1), (1, 0)$ に石が一つずつ並んでいる。このような石の置き方をくの字であると呼ぶ (詳細な条件は問題文参照) 。

3つの石の中から1つ選んで好きな位置に移動させる操作を好きだけ行うことができる。ただし、各操作の後、石はくの字になっていなければならない。

石が点 $(\mathit{ax},\mathit{ay}),(\mathit{bx},\mathit{by}),(\mathit{cx},\mathit{cy})$ にひとつずつ石が置かれている状態になるまでに必要な最小の操作回数を求めよ。

$T$ 個 ($T \lt 10^3$) のテストケースが与えられるので、それぞれ答えよ。

解法概要

くの字となる並び方は、くの字の中心 (または左下など) の座標が定まっても一意には定まらない。

そこで、x, y 各座標の値の和を考えてみると、

• 同じ「く」の形のまま x 座標またはy座標の方向に+1/-1 だけ平行移動すると平行移動した座標に対応する和は +3/-3 する
• 中心を変えないまま他2つの石の位置を変えると、x 座標またはy座標の和が +2/-2 する

というわけで、x, y 座標の値の和と3つの石の位置を対応付ければ良さそうである。

x, y座標の値の和と、1回の操作で和がどのように変化するかをグラフで表したものが下の図である。

(グラフの画像は https://csacademy.com/app/graph_editor/ で作成)

一応、くの字の向きで塗り分け (囲み分け？) してある。

私の場合はこれだけ見ても立式できそうになかったので、範囲を限って必要な移動回数を手で求めてみた。

4333333
3322223
3221123
3210123
3211123
3222233
3333334

(0 のところが初期状態 $(0, 0), (0, 1), (1, 0)$ に対応する)

なんとなく法則性が見えてきた。座標の和が取りうる値 $\cdots, 0, 1, 2, 4, 5, \cdots$ を $\cdots, 0, 1, 2, 3, 4, \cdots$ のように対応づけ、その値を x, y 座標について $x^{\prime}, y^{\prime}$ とする。すると、多くの場合について必要な移動回数は $\max (\left| x^{\prime} \right|, \left| y^{\prime} \right|)$ となるが、$x^{\prime} = y^{\prime}$ の場合のみ $+1$ する必要があることがわかる (ただし $\max (x^{\prime}, y^{\prime})$ が 0 または 1 の場合を除く。)

あとは「座標の和が取りうる値 $\cdots, 0, 1, 2, 4, 5, \cdots$ を $\cdots, 0, 1, 2, 3, 4, \cdots$ のように対応づけ」の部分をコードに落とし込む。

座標の和が取りうる値は 0 以外は 3 で割ったときに (1 または 2 の) あまりが出る値なので、変換前の和を $x$ $y$ とすると

$x^{\prime} = \lfloor \frac{x}{3} \rfloor \times 2 + (x \%3 - 1) $

のようになる。 $y$ についても同様。

ただし、これをそのままコードにすると座標の値の和が負になったときに正しく計算できない。

たとえば C++ では (-1) / 3 のような計算は -1 ではなく 0 になる。今回の場合は割られる数が負でかつ割り切れない場合にはより絶対値の大きい方の値を出してほしいので、割られる数が負の数の場合のみ $2 = 3-1$ を引くことで調整している。また、負の余り $-2, -1$ はそれぞれ $1, 2$ に対応づけてほしいので、あまりが正となるような調整も入れている。

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

using ll =  long long;

void solve() {
    ll gx = 0, gy = 0, x, y;
    for(int i=0;i<3;++i) {
        cin >> x >> y;
        gx += x; gy += y;
    }

    ll xx = (gx + (gx < 0 ? -2 : 0)) /3 * 2 + ((gx%3 + 3) % 3 - 1);
    ll yy = (gy + (gy < 0 ? -2 : 0)) /3 * 2 + ((gy%3 + 3) % 3 - 1);
    ll ans = max(abs(xx), abs(yy));
    if(xx == yy) {
        if(xx >= 2 || xx < 0) {
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

所感

「和でくの字を区別できる」ことに気づくのが第一関門、実験をして法則性を見つけるところが第二関門。

私は本番では第一関門も突破できませんでした……。