先週に続いて今回もまたGCJの話でお茶を濁そうとしています。tamaです。
お茶を濁すっつーかこの1週間で一番無難に人に話せる技術的話題だったので…
（週末に作業してたプライベートのサイトのこと書こうと思ってたけど内容的に晒せなくなったっていう）

Google Code Jam 2016 Round 1A とは

おさらい。

Google Code JamはGoogleが開催している競技プログラミングのコンテスト。
Google Code Jam 2016 はその2016年の本大会で、Qualification Round（予選大会）を通過すると Round 1 に参加できます。

1A ？

そうなんです。この週末に開かれたのは Round 1A。
Round 1 は 1A 1B 1C の3回開催されます。
各2時間半の時間制限の中で上位1,000位に入ると Round 2 に進出できます。
（合計3,000人 Round 2 に参加できます）

GCJ2106-1A 振り返り

2時間半確保できなかったので参戦しなかったのですが、全3問、
Largeまで全部パスして100pt満点でも上位1,000位に入賞できなかったようなので
レベルが高かったというか問題の難易度が高くなかったみたいです。

そんな中、
Problem B. Rank and File
がGCJらしくてとてもおもしろかったのでとりあげてみたいと思います。

Problem B. Rank and File

ストーリーはさておき。
N×N の正方形のマスの中に左→右、上→下の順に大きくなるように数字が埋まっているとき、
横に一列ずつN列、縦にも一行ずつN行を抜き出したけどひとつだけデータをなくしてしまった。
それを見つけろ。という問題。

Sample はもともと

1 2 3
2 3 4
3 5 6

という3×3のマス。入力されているデータは

• 1 2 3 ← 1列目横一列
• 2 3 5 ← 2行目縦一行
• 3 5 6 ← 3列目横一列
• 2 3 4 ← 2列目横一列
• 1 2 3 ← 1行目縦一行

で、3行目の縦一行「3 4 6」を答えとして導き出すというものです。
（縦と横は逆転しているかもしれないのであくまで入力値からの憶測ですが）

これを丁寧に問こうとすると仮置きをしたりややこしいことをしないといけなくなることも。
（なくした行の数字がわからないので確定で置いていいか判断ができなくてパターン検証が必要になる）

でもでも、同じマス（の数字）は縦に見たときと横に見たときとで2回数えることになります。
ということは 必ず 出現する数字の回数は偶数になるはず。
（2ヶ所別のマスに同じ数字が入っていても4回カウントされて偶数になる）
数字ごとに出現回数を数えて奇数のものがあればそれは なくした行or列に含まれていた数字 です。
そしてそれは 左→右 or 上→下 に小さい順で並んでいるはず！

これに気付くととてもシンプルなソースで答えを見つけることができます。

こういう…一見フクザツというかややこしい処理やアルゴリズムを実装しないといけないものも、
本質を突くとめっちゃカンタンに高速に答えを求められるっていうパズル性が競技プログラミングの魅力です✨
特にGCJは「ヒラメクと一瞬」系の問題が（他の競技プログラミングより）多い気がして楽しいです。

興味を持った方は過去問をどうぞ(o'ヮ'o)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#!/usr/bin/env python

import sys


def solve(N, lines):
    counter = {}
    for line in lines:
        for num in line:
            counter[num] = counter.get(num, 0) + 1
    answer = [num for num, cnt in counter.items() if cnt % 2]
    return ' '.join(map(str, sorted(answer)))


def main(IN, OUT):
    T = int(IN.readline())
    for index in range(T):
        N = int(IN.readline().strip())
        lines = [map(int, IN.readline().split()) for n in range(2 * N - 1)]
        OUT.write('Case #%d: %s\n' % (index + 1, solve(N, lines)))


if __name__ == '__main__':
    main(sys.stdin, sys.stdout)