Google Code Jam 2016 Round1A に参加した

updated: 2016-04-16

Google Code Jam 2016 Round1A に参加した.

Past Problems - Google Code Jam (過去のコンテスト一覧)

Round1A の前に Qualification Round という予選があり,そちらで A, B, C, D の四問 (それぞれ small, large と規模の異なる入力がある) を解き,Quarification ラウンドで 30 点を超えると Round1 に参加できる. Qualification Round についてもそのうち書くかもしれないが, 75 点だった.

 

一問目

問題を読み違えたので二度も WrongAnswer を出してしまった.

一文字ずつ追加していって辞書順で一番遅い単語を作り出せという問題で,現在の単語 (文字列) と追加する文字をそれぞれ T, c とすると, c+T と T+c を比べて辞書順でより遅い方を採用していけばいいと思う.

また,辞書順なので c が T の先頭文字より遅ければ c を先頭につける,という方法の方が速いかもしれない.こっちの方法で解いた.

 

二問目

問題を理解していなく,「行列が一部分だけ重なり,重なった部分が上書きされてしまったので,消えてしまった部分を答えろ」という問題だと勝手に思って解いた.

行列は行についても列についても単調増加になっているという条件があり,行列が 2 つ重なるということなので,重なって消えた部分に入っている数字が奇数回しか出現しなくなる.

以上で,奇数回出現している数字を昇順に並べて答えた.

※ 単調増加でない場合,上述の考え方では以下のような行列に対して正答できない.正答は 1 1 だけれど,1 は 6 回出現していて奇数回ではない.

1 1

1 1

1 1

 

三問目

自分の隣には自分がズッ友 (best friend forever) だと思ってる人がいないと輪に入れない,最大の輪は何人で作ることが出来るか,という問題だった.

強連結成分 (ここでは各ノードが自分が起点となるエッジを一つしか持たないので有向サイクルになる) を抜き出して並べるようなことを考えていたけれど,これは間違いだった.

サイクル数が 2 のサイクルを中心に,そのサイクルに向かって片思いしている列が延長されていくイメージで解いた.

具体的には,

  1. 入力を無向グラフ,有向グラフにする
  2. 無向グラフの連結成分,有向グラフの強連結成分を出す
  3. 有向グラフの強連結成分の中にあるノード数 2 のもの (つまり相互ズッ友のペア) を取り出す
  4. 3. で取り出したペアそれぞれに向かって引ける一番長いパスをそれぞれ取り出す
  5. 別のペアを取り出して 4. を行う
  6. ( (ペアと片思いの人たち) を複数並べたもの) と (サイクル数が 3 以上の最大サイクル) を比較して大きい方の輪が最大になる

これで解けた.

おそらく時間がかかったのは 4. なので,一番長いパスを探す範囲を, (当たり前だけれど) そのペアを含む連結成分に絞ったら速くなった.

 

残念ながら C-small, C-large は間に合わなくコンテスト終了後に解いたので, A, B だけ得点できた. Round1B で頑張ろう.

グラフの作成,連結成分の抽出,パスの確認などを全て Python のライブラリ networkx に頼ったので,この問題の実装はとても楽だった. networkx が便利だった.