Alien Rhyme

接尾辞が一致するペアを可能な限り作る問題。

問題文読むのがつらいが、文字は50文字しかないので、実装自体はそこまで難しくない。

対象となる全Wordの末尾を取得し、2個以上被るものがあればそれを抜けばよい。

この時、末尾が3つ以上被るときどれを取ってよいか、という問題が発生するが、接尾辞の長いほうから考えることによって、どれを取得してもよい。

なぜならば、ある末尾k文字で一致している3つのワードがあった時、末尾k-1文字～1文字の間はすべてこれらのワードは同じ末尾の文字列が出てくることになる。つまり、どれをとっても残るものはこれ以降の末尾の一致を考えたときに全く変わらなくなる。

Nはhiddenでも高々1000だったので、O(N²)ぐらいまでなら大丈夫そうってことで以下の実装に。

from collections import Counter

def solve(N, words):
    ans = 0
    for n in range(50, 0, -1):
        c = Counter(w[::-1][:n] for w in words if len(w) >= n)
        for v, count in c.items():
            if count >= 2:
                ans += 1
                remove_indexes = [i for i, w in enumerate(words) if w.endswith(v[::-1])]
                words.pop(remove_indexes[1])
                words.pop(remove_indexes[0])
    return ans * 2


t = int(input())
for case in range(1, t + 1):
    N = int(input())
    words = []
    for i in range(N):
        words.append(input())
    print("Case #%d: %s" % (case, solve(N, words)))

codingcompetitions.withgoogle.com

Golf Gophers

これも問題文を読むのが大変。インタラクティブ問題。

最大18枚の羽根を持つ風車を設置すると、夜の間にいたずらされて、回転させられてしまう。

回転させられる風車がどれかはわからないが、 1回のいたずらで全員同じ方向で1枚の羽根の分だけ回転させることはわかっており、すべてのいたずらする人が必ず1回のいたずらをすることがわかっている。

夜の前には0番目の羽根が必ず下を向くように設置し、朝起きたときにわかるのは風車のどの羽が下を向いているかである。

設置する風車と羽根の枚数をインプットし、朝起きたときどの羽が下を向いているかをアウトプットとしてもらったとき、いたずらしている人数を答える。

ざっと聞いた感じであまりやら結構面倒なことになるのは見えたが、実はVisibleのテストは非常に余裕がある。

ので、「高々100回しかいたずらされないので、1年間毎日18枚の風車を18個設置したらどこかで、いずれの風車も1周していない日があるだろう」という期待のもと試してみたらうまくいった。

Hiddenはまだ解説読んでないな、、

from sys import stderr, stdout


def solve(N, M):
    response = []
    out = " ".join(["18"] * 18)
    for _ in range(360):
        print(out, flush=True)
        stdout.flush()
        response.append(input())
    m = 0
    for line in response:
        m = max(m, sum(list(map(int, line.split(" ")))))

    print(m, flush=True)

    verdict = input()
    if verdict == "1":
        return True
    else:
        return False

T, N, M = tuple(map(int, input().split(" ")))
for case in range(1, T + 1):
    if not solve(N, M):
      break
exit()

Pylons は pythonでやったら、HiddenがどうもTLEになってしまったのでC++で書き直し中。。。

エンジニア。

Google Code Jam Round1A - Alien Rhyme / Golf Gophers

Alien Rhyme

Golf Gophers