Google Code Jam(GCJ) 2010 Online Round 1: Sub-Round C
概要
ぐーぐる先生のプログラミングコンテスト。Online Round 1は150分のSub-Roundが3回開催され、各Sub-Roundから上位1000人が選ばれる。
通過者は次のSub-Roundには参加できない。通過しなかった場合は参加しなかった場合と同じく、次のSub-Roundに再挑戦できる。
僕は時間の問題でCだけ参加した。なんか通ったらしいので2待ち。
A
2つの建物の間をLANケーブルがスパゲッティーしている。どれくらいスパゲッティーしているか。
各端点を順序を保持したまま[0,n)に変換して片方からもう片方への検索配列にしてバブルソートの回数をO(N^2)で計測すればいい。
言葉ではうまく説明できないけどまあ問題見ろ。
C
知ってるか？チェス盤(大きさは8とは限らない正方形の市松模様)はチェスの木から作られるんだぜ。でもチェスの木は必ずしも市松模様にはなってないんだ。
市松模様になってるチェス盤で大きくて上のほうにあって左側にあるやつから順番に切り抜く。切り取れる枚数を大きさ別に出力せよ。
とりあえずxorかけて市松模様ではなく同じ色の最大の長方形を検出する問題に変形。
んでもって、ある一辺の長さについてはDP的な走査をかけたりしてO(N^2)で検出できる。
しかしO(N^3)は真面目に256^3*100だと1677721600となり相当ヤバい。しかしInput200KBの制約みて考えを改める。
結局Largeは終わるか心配な程度に時間かかったけど終わった。
結果
なんかよくわからないけど満点で37位通過らしい。
Round 2では1Aや1Bで通過した人と合流するのか。こわい。
