Meta Hacker Cup 2022 Qualification Round 出場記＆解説

概要

Meta Hacker Cup 2022のQualification Roundが終わりました。
日本語記事がなさそうだったので、紹介と解説をします。
解説コードはC++です。

本番では6問中4問解けて50ptでした。通過ラインは9ptなので無事通過です。
B2、Dも解けていたのですが提出形式に対応できずptを得られませんでした。そのあたりの反省点も書いていきます。

Meta Hacker Cupとは？

Metaが年1回開催している国際的なプログラミングコンテストです。
Facebook Hacker Cup（FHC）の名前で2011年から始まったコンテストで、年1回開催の個人戦のプログラミングコンテストとしてはGoogle Code Jam（GCJ）、Topcoder Open（TCO）と並び称されています。

全5ラウンドからなります。
・Qualification Round：72時間制。1問正解で通過。
・Round 1：24時間制。一定以上の点数で通過。
・Round 2：3時間制。上位500人が通過。
・Round 3：3時間制。25人が通過。
・Final Round：4時間制。オフライン開催。
Round 2の上位2000人に入るとTシャツ、Round 3の上位200人に入るとシャツに付けるバッジ、Round 3通過の25人には海外招待と賞金のプライズがあります。

Google Code Jamとは「1問解ければ通過の72時間予選」「多段階のラウンドで途中でTシャツ」「オフラインで25人が決勝」というあたりは共通ですが、Round 1の方式が違いますね。
Google Code JamもMeta Hacker Cupも、Qualification Roundを通過するのは割と簡単です。AtCoder茶色やPaiza Aランクならまず通りますし、競技プログラミング未経験でも十分通過可能です。
問題文が英語で、出題傾向や提出方法もAtCoderと異なるため、出るといい経験になると思います。

独特な提出方式

Meta Hacker Cupは、他のプログラミングコンテストと異なる提出手順を採用しています。

1. 問題ページにあるサンプル入出力を試す（いつもと同じ）
2. 提出フォームからテスト用の入力ケースをダウンロードし、手元で実行して出力結果をファイルにまとめる
3. 2の出力のファイルを提出フォームからアップロードする
4. この提出結果が正しい場合のみ、5に進める（間違えのペナルティはない）
5. 採点用の入力ケースをダウンロードする（6分間のカウントダウンが始まる）
6. 5のケースを手元で実行し、出力結果をファイルにまとめる
7. 出力結果とソースコードを提出フォームからアップロードする

以上の手順で提出します。
この時、5～7は6分以内に行う必要があります。間に合わなかった場合、その問題のスコアは0点で確定し、コンテスト中に提出することはできません。
また、手元での実行なのでコードの実行時間制限はありません。5,7が2分間とすると240秒が事実上の実行時間制限となります。
また、実行環境に制限もないので、多分スパコンで並列処理させても大丈夫です（それでゴリ押しできる問題が出るかは別として）
なお、回答の正否はコンテスト終了まで分かりませんし、6分間を過ぎると提出の訂正もできません。以上のことから、AtCoderのコンテストとは実行時間の見積もりや提出戦略が変わりえます。

とはいえ、なかなか初参加でこれらを有利に使えるものでもないと思うので、提出方法に起因する失点をしないのが大切かなと思います。
また6分間使えるといってもDL・UPやファイル入出力に費やす時間が長いので、計算量の見積もりはいつも通りO(10^9)を目安とします。

ちなみに5でダウンロードできるのはパスワード付きzipファイルなので、7-zipなどのパスワード対応の解凍ソフトを予めダウンロードしておく必要があります。

余談

Qualification Roundは72時間制ですが、長時間PCに向かってコードを書き続けている必要があるということはありません。通常は全問取り組んでも1～3時間程度の参加になると思います。通過だけなら72時間のうち1時間確保して取り組めば通過できるでしょう。
今年のQualification Roundは土曜～月曜でしたが、自分は土曜日曜がイベント参加で、月曜は仕事のため、土日に考察したものを月曜の夜に実装しました。

土曜日はLa prièreというアーティストの1stライブでした。物販に並んでいる間に問題文を読んで考察しました。この時点ではC2までは回答の目処が立ち、Dは問題の趣旨は理解できたけど計算量削減の方法が分からないなという感じでした。

日曜日は匿名ラジオというラジオのトークイベントに参加しました。物販購入から開場まで時間があったので、近くのららぽーとをブラブラしながらDについて考えていました。計算量は未証明ですが、実装方針は立ちました。

どちらも最高でした！ぜひ観てみてください！！
……という布教がしたいわけではなくですね（いや布教はしたいですが）
こういう「問題文をとりあえず頭に入れておいて、日常を楽しみながら空き時間に考察する」というやり方は驚くほど捗ります。物販に並びながら問題を読んでボンヤリと考えていただけなのに、実装する段階になったらどの問題も実装方針がクリアになっていました。

例えばAHCレッドコーダーのTERRYさんも、1週間のコンテストの1日目の最初に問題文を読んで、少しずつ考察を進めながら観光をしていました。

長期間のコンテストでは忙しくても最初に問題文に目を通しておくかおかないかは雲泥の差ですし、日頃から難しい問題を何問か頭にストックしておくのも有効だなと再認識しました。

さて、以降は問題解説です。

A: Second Hands

https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/A
$N$個の部品と、$2$つの箱があります。
それぞれの部品の形が$S_1..S_N$で与えらます。
また、1つの箱には$K$個まで部品を入れることができます。
このとき、同じ箱に同じ形の部品が入らないように$N$個すべてをどちらかの箱に入れることができるか、判定してください。
（できるなら"YES"、できないなら"NO"を出力）

制約：$1 ≦ T ≦ 90, \ 1 ≦ N, K, S_i ≦ 100$

解法

まず、部品が$2×K$よりも多い場合、2つの箱に入りきらないので"NO"です。
また、同じ形の部品が3個以上ある場合も"NO"です。
逆にそれ以外は"YES"となります。具体的には、2個ある部品を別々の箱に入れてから、1個ある部品を（Kを超えないように）適当に入れることができます。

同じ形の部品の個数は、map（言語によって連想配列、ディクショナリなど）を使って管理するのが素直です。

解答コード

A.cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
  // 入力
  int N, K;
  cin >> N >> K;
  vector<int> S(N);
  for (int i = 0; i < N; i++) cin >> S[i];

  // 商品の形ごとの個数を数える
  map<int, int> mp;
  for (int i = 0; i < N; i++) {
    mp[S[i]]++;
  }

  // YESで初期化し、NOか判定する
  string ans = "YES";
  // 商品が2×Kよりも多い場合、NO
  if (N > K * 2) ans = "NO";
  for (auto p : mp) {
    // 同じ形の商品が3個以上ある場合、NO
    if (p.second > 2) ans = "NO";
  }

  // 出力
  cout << ans << "\n";
}

int main() {
  int T;
  cin >> T;
  for (int i = 0; i < T; i++) {
    cout << "Case #" << i + 1 << ": ";
    solve();
  }
  return 0;
}

ファイル入出力の方法は自由なので「言語名　ファイル入出力」でググってもいいですし、標準入出力とリダイレクトを活用するのも簡単です。
例えばいつものように標準入出力のcin, coutを使ったコードをコンパイルし、inputという名前のファイルに入力ケースを用意したあと、実行結果をoutputという名前のファイルに出力したい場合、以下で十分です。
$ ./a.out < input > output
速度面でベターな方法は言語や環境によって色々あるかもしれませんが、Qualification Roundを抜ける分にはこれで困らないはずです。

感想

今回は制約が小さいので3重ループでも間に合いますね。
問題文が英語で提出方法も独特ですが、問題自体は解けたのではないでしょうか？
これが解ければRound 1に進出です。
AtCoderならABC-Bのdiff100程度の問題かなと思います。部品の数の上限が増え箱の個数もパラメータとなった場合、diff300程度まで上がるかもしれません。

B: Second Friend

$R行×C列$のグリッドと初期状態が与えられます。
各マスの初期状態は「木」「空白」「石」のいずれかです。
自分は0マス以上好きなだけ「空白」を「木」に変えることができます。
このときそれぞれの木が2つ以上の木に隣接している、つまりそれぞれの木について「上下左右の4マスのうち、2マス以上が木」であるような状態にすることができるか判定し、可能なら具体的な最終状態を出力してください。
（出力する最終状態はどれでもいい。不可能なら"Impossible"と出力）

B1: Second Friend

B1では「石」がありません。
つまり、初期状態は「木」「空白」のどちらかです。

入力の制約は次の通りです。
$1 ≦ T ≦ 85$
$1 ≦ R, C ≦ 100$

解法

基本的には盤面を全て木で埋めてしまえば「それぞれの木について、上下左右の4マスのうち、2マス以上が木」を満たせそうです。
しかし盤面が1行または1列の場合、全て木で埋めると端のマスが条件を満たしません。
では盤面が1行または1列の場合、条件を満たすような最終盤面はあるでしょうか？ 実は木が1本もない場合、条件を満たしていますね。一方で一本でも木がある場合、どんな設置も条件を満たさないことが簡単に証明できます。
まとめると、
・盤面が1行または1列で木が1本もない場合、入力の盤面をそのまま出力する
・盤面が1行または1列で木が1本でもある場合、Impossibleを出力する
・それ以外の場合、全てのマスを木に変えた盤面を出力する
と良いので、これを素直に実装します。

解答コード

B1.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void solve(int testCase) {
  /* input */
  int R, C;
  cin >> R >> C;
  vector<string> S(R);
  rep(i, R) cin >> S[i];

  /* solve */
  string ans = "Possible";
  if (R != 1 && C != 1) {
    rep(i, R) rep(j, C) S[i][j] = '^';
  } else {
    rep(i, R) rep(j, C) {
      if (S[i][j] == '^') ans = "Impossible";
    }
  }

  /* output */
  printf("Case #%d: %s\n", testCase, ans.c_str());
  if (ans == "Possible") {
    rep(i, R) cout << S[i] << "\n";
  }
}

int main() {
  int T;
  cin >> T;
  rep(ti, T) solve(ti + 1);
  return 0;
}

感想

コーナーケースに気付けますかという問題ですが、サンプルが優しいですね。

B2: Second Second Friend

B2では石があります。

制約
$1 ≦ T ≦ 80$
$1 ≦ R, C ≦ 3000$

解法

石の配置によっては木が置けない（そこに木を置くと隣2マスを木にできない）位置が出てきます。
具体的には隣接4マスのうち3マスが「①盤外」「②石」「③木が置けないと判明している空白」の場合、木が置けません。
ところで1つ目の③は②の隣接マスに発生しますし、2つ目の③は②か1つ目の③の隣接マスに発生します。
ということで、石を起点に幅優先探索（BFS）すれば木が置けない位置を列挙できそうです。

木が置けない位置を列挙したあとは、木が置ける位置を木で埋めた上で、「それぞれの木について、上下左右の4マスのうち、2マス以上が木」となっているかチェックすることで判定できます。

各②③は1回しかキューに入ることはないので、テストケース1個あたりの計算量はO(RC)です。
BFSの動作や実装が分からない方は以下の記事がオススメです。

BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

解答コード

B2.cpp

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void solve(int testCase) {
  /* input */
  int R, C;
  cin >> R >> C;
  vs S(R);
  rep(i, R) cin >> S[i];

  /* solve */
  string ans = "Possible";
  vi dy = {-1, 0, 0, 1};
  vi dx = {0, -1, 1, 0};
  vvi visited(R, vi(C));

  // 隣接4マスに木もしくは空白が2つ以上あるならtrueを返す
  auto hasFriends = [&](int y, int x) {
    int cnt = 0;
    rep(k, 4) {
      int y2 = y + dy[k];
      int x2 = x + dx[k];
      if (y2 < 0 || x2 < 0 || y2 >= R || x2 >= C) continue;
      if (S[y2][x2] == '^' || S[y2][x2] == '.') cnt++;
    }
    return cnt >= 2;
  };
  // 石を始点に幅優先探索し、木を置けないマスに'x'印を付ける
  auto bfs = [&](int startY, int startX) {
    queue<pii> q;
    visited[startY][startX] = 1;
    q.emplace(startY, startX);

    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      rep(k, 4) {
        int y = p.first + dy[k];
        int x = p.second + dx[k];
        if (y < 0 || x < 0 || y >= R || x >= C) continue;
        // 木を2つ隣接させられないマスは'x'印を付けておく
        if (!hasFriends(y, x)) {
          if (S[y][x] == '.') S[y][x] = 'x';
          if (visited[y][x]) continue;
          visited[y][x] = 1;
          q.emplace(y, x);
        }
      }
    }
  };

  if (R == 1 || C == 1) {
    rep(i, R) rep(j, C) {
      if (S[i][j] == '^') ans = "Impossible";
    }
  } else {
    // 木を置けない箇所をBFSで探索
    rep(i, R) rep(j, C) {
      if (S[i][j] == '#') {
        if (visited[i][j]) continue;
        bfs(i, j);
      }
    }
    // 置いていいところ全てに木を置く
    rep(i, R) rep(j, C) if (S[i][j] == '.') S[i][j] = '^';
    // '×'印を元に戻しておく
    rep(i, R) rep(j, C) if (S[i][j] == 'x') S[i][j] = '.';
    // 条件を満たしているかチェック
    rep(i, R) rep(j, C) {
      if (S[i][j] == '^') {
        int cnt = 0;
        rep(k, 4) {
          int y = i + dy[k];
          int x = j + dx[k];
          if (y < 0 || x < 0 || y >= R || x >= C) continue;
          if (S[y][x] == '^') cnt++;
        }
        if (cnt <= 1) ans = "Impossible";
      }
    }
  }

  /* output */
  printf("Case #%d: %s\n", testCase, ans.c_str());
  if (ans == "Possible") {
    rep(i, R) cout << S[i] << "\n";
  }
}

int main() {
  int T;
  cin >> T;
  rep(ti, T) solve(ti + 1);
  return 0;
}

・hasFriends, bfsを関数やλ式として切り出しておくと見通しがよくなる
・dy, dxを用意しておくのがグリッド探索のプチテクニック
・最後の条件を満たしているかのチェックはhasFriendsではないので注意

感想

考察した上でグリッド上のBFSを書く必要があり、競技プログラミングらしい問題になってきました。
AtCoderだと緑diffのABC-Dだと思います。

コンテスト中は入力ファイルが重く、モタついている間に6分が経過しました。
「テストケースのseedが変わってまたダウンロードからになるのかな」くらいの認識でゆっくりやっていましたが、6分以内に提出できない場合は0ptで、二度と提出できないルールでした。

C: Second Meaning

モールス符号では、メッセージが複数通りに解釈できることがあります。
例えばEは「.」、Tは「-」、Nは「-.」なので、「-.」というメッセージが「TE」なのか「N」なのか分かりません。「.....--.-.-.-..-.-.-...-.--.」は "HACKER CUP"とも"SEE META RENT A VAN"とも解釈できるそうです。

さて問題Cは、モールス符号とは異なり、どんなメッセージも1通りにしか解釈できないような符号の集合を構築する問題です。
入力として、その集合に含まれる1種類目の符号$C_1$と、何種類の符号を作ればいいかという$N$が与えられます。
出力は、2種類目からN種類目までの符号です。

例えば、入力が「.-.」「N = 3」であれば、「...」「---」を出力すると条件を満たしています。

C1: Second Meaning

制約
$1 ≦ T ≦ 100$
$2 ≦ N ≦ 100$
1種類目の文字$C_1$の長さは1～100文字
2～N種類目に使っていい文字の長さは1～200文字

解法

$M$文字で作れる符号の種類は$2^M$通りです。
したがって、例えば入力$C_1$が「.-.」で$N=8$の場合、3文字で「.-.」以外の$7$種類を出力すればいいですが、$N = 10$の場合は3文字では表しきれません。
つまり、固定長符号では$C_1$の文字数が小さく$N$が大きい場合、条件を満たせないことがあります。

ここで、情報科学や通信工学の素養があればハフマン圧縮のことを思い出して接頭符号を作ることもできますが、C2の解法をC1でも適用する方が簡単だと思います。
続きはC2の解法に書きます（C2のコードでC1も解けます）

C2: Second Second Meaning

制約
$1 ≦ T ≦ 95$
$2 ≦ N ≦ 95$
1種類目の文字の長さは1～100文字
2～N種類目に使っていい文字の長さは1～10文字

C1よりも2種類目以降で使っていい文字の長さが短くなっています。

解法

固定長符号では条件を満たせないことは分かりましたが、できるだけ文字の長さが同じである方が、符号の区別は簡単そうです。
仮に2～N種類目を10文字に固定することができるなら話は早そうです。
それが可能か考えるてみると、1種類目の1文字目と2～N種類目の1文字目を別の文字にしてしまえば、符号の区別ができることが分かります。
1種類目の1文字目を「.」、2～N種類目の1文字目を「-」、1種類目の文字の長さを$lenC1$とした場合、以下の手順で読み込めばいいですね。

i = 1
while(i <= メッセージの長さ)
  if(メッセージのi文字目が「.」)
     その符号は1種類目
     i += lenC1
  else 
     その符号は2～N種類目（互いに判別可能）
     i += 10

1種類目と1文字目が異なる長さ10の符号は512種類あり、Nの上限よりも大きいので、2～N種類目を10文字に固定しても条件を満たす集合を作れることが分かりました。
2～N種類の列挙は、解答コードではbit全探索でやっていますが、再帰を使うのもアリです。

解答コード

C.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
void solve(int testCase) {
  /* input */
  int N;
  cin >> N;
  string C;
  cin >> C;

  vector<string> ans;

  /* solve */
  string init = "..........";
  if (C[0] == '.') init[0] = '-';

  int bit = -1;
  while ((int)ans.size() + 1 < N) {
    bit++;
    string s = init;
    rep(i, 9) {
      if (bit & (1 << i)) s[i + 1] = '-';
    }
    ans.push_back(s);
  }

  /* output */
  printf("Case #%d:\n", testCase);
  rep(i, (int)ans.size()) cout << ans[i] << "\n";
}

int main() {
  int T;
  cin >> T;
  rep(ti, T) solve(ti + 1);
  return 0;
}

感想

解法を思いつくまでが難しいですね。
こういうアドホックな考察はコツを伝えづらいですが、
「1符号目の文字数がある程度長ければ、固定長にすれば区別できる」
「1符号目の文字数が短い場合、うまく区別する方法はないか？」
「1符号目と、2符号目以降で1文字目を変えてしまえばいい！」
という流れで考えられると良かったんじゃないかと思います。

D: Second Flight

$N$頂点$M$辺の重み付き無向グラフが与えられ、$Q$個のクエリに答える問題です。
クエリ$X, Y$について、
・頂点$X$と頂点$Y$の間に辺がある場合、辺の重みの2倍
・各頂点$Z$について、頂点$X$と頂点$Z$、頂点$Y$と頂点$Z$の間に辺がある場合、2つの辺の重みの$min$
を足し合わせた値を出力します。

例えば画像において、
X = 1、Y = 2 出力25
X = 1、Y = 3 出力20
の要領です。

制約
$1 ≦ T ≦ 70$
$1 ≦ N, M, Q ≦ 200,000$
$1 ≦ C_i ≦ 10^9$
$1 ≦ A_i, B_i ≦ N; A_i ≠ B_i$
$1 ≦ X_i, Y_i ≦ N; X_i ≠ Y_i$
$全テストケースのQの合計は5,000,000以下$

解法

頂点も辺もなかなか多いので、先に全部前処理するのは間に合いません。
しかしクエリもなかなか多いので、クエリ毎にO(M)以上掛かるようでは間に合わず、工夫が必要そうです。

クエリ毎に求める方針で考えてみると、毎回
「頂点Xから辺が伸びている各頂点から、頂点Yに対して辺が伸びていれば加える」
の計算をすることになります。
ここで、「頂点$X$から辺が伸びている各頂点」について考える時は$X$の次数の分だけ時間が掛かりますが、「ある頂点から頂点$Y$に辺が伸びているか」はハッシュテーブルを使うと$O(1)$で求まることができます。
つまり、頂点$X$と頂点$Y$のうち、次数が少ない方を$X$とした方が効率が良さそうです。
ついでに、同じクエリが複数回来た場合に備えてメモ化しておきましょう。

これでクエリ毎の計算量は$O(min(Xの次数, Yの次数))$となりました。
ここで、各頂点の次数の和は辺の数の2倍、つまり$2M$となります（グラフ理論ではわざわざこれを握手定理と言います）
$Q$個のクエリを
・同じクエリは存在しない（メモを使わせない）
・$min(Xの次数, Yの次数)$の和が最大になる
ように構築するのが入力のワーストケースですが、この場合も実は計算量は$O(QM)$よりも良くなることが証明できます。

が、コンテスト中は証明してません。「これ以上は思いつかないから、これで通ると信じよう」をやりました。
解説のSolution 2に計算量の解析が書いてあるので、こちらを参照してください。
https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/D/solution

Solution 1は頂点の次数の大きさによって処理を分ける別解です。
次数が$√M$以上の場合のみ前処理し、$√M$未満の場合は逐次処理することで計算量を抑えることができるそうです。
（※こういうテクニックも平方分割と呼ぶらしいですが、平方分割と検索すると一見(?)異なるものがヒットしますね）

解答コード

D.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void solve(int testCase) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  /* input */
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<unordered_map<int, int>> to(N);
  vector<unordered_map<int, ll>> memo(N);
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    to[a][b] = c;
    to[b][a] = c;
  }

  /* solve */
  printf("Case #%d: ", testCase);
  rep(qi, Q) {
    int X, Y;
    cin >> X >> Y;
    --X, --Y;
    // 次数が小さい方をXとする
    if (to[X].size() > to[Y].size()) swap(X, Y);
    ll ans = 0;

    if (memo[X].count(Y)) {
      ans = memo[X][Y];
    } else {
      if (to[X].count(Y)) ans += 2 * to[X][Y];

      for (auto &[Z, toXZ] : to[X]) {
        if (to[Z].count(Y)) {
          ans += min(toXZ, to[Z][Y]);
        }
      }
      memo[X][Y] = ans;
    }

    printf("%lld%c", ans, (qi == Q - 1 ? '\n' : ' '));
  }
}

int main() {
  int T;
  cin >> T;
  rep(ti, T) solve(ti + 1);
  return 0;
}

感想

Solution 2の方が思いつきやすいですが、証明はSolution 1の方が簡単なので、Solution 1を抑えておく方が類題が出た時に再現性が高そうです。
まぁコンテスト中は未証明でも正解して、コンテスト後に理解できればOKということで。

ところでコンテスト中は実行が6分間に間に合いませんでした。
手元の実行ではWSL2を用いていたのですが、コンテスト後に調べたところ、Windows上にあるファイルと入出力をするととても遅いということが分かりました。そこで実行ファイルと入出力ファイルをlinux上に置いて実行したところ、90秒で実行が終わりました。

AとB1だけ通して「予選通過できるから満足」で終えていたらRound 1以降で痛い目を見たと思うので、致命的にならないQualificationでB2とDの失敗を経験できてよかったです。