唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Codeforces Round #168 (Div. 2) oxo-- 1665->1588

Cで時間を使いまくるミスをした上に、BはSystem testで落ちてしまった。

Problem - A - Codeforces

あるボタンを押した時、そのボタンと周囲のボタンの状態が反転する。
各ボタンについて押した回数が与えられた時に最終状態を求める。

単純にやるだけ。

import sys

push = [[0 for i in xrange(5)] for j in xrange(5)]

for i in xrange(3):
    temp = map(int, raw_input().split())
    for j in xrange(3):
        push[i + 1][j + 1] += temp[j]
        push[i][j + 1] += temp[j]
        push[i + 1][j] += temp[j]
        push[i + 2][j + 1] += temp[j]
        push[i + 1][j + 2] += temp[j]

result = []
for i in xrange(3):
    temp = ''
    for j in xrange(3):
        if push[i + 1][j + 1] % 2 == 1:
            temp += '0'
        else:
            temp += '1'
    result.append(temp)

for r in result:
    print r

Problem - B - Codeforces

白と黒のタイルがあるときにすべての黒いタイルのペアについて隣接した黒の地点だけを、最大1回曲がるだけで到達できるか調べる。

タイルの最大数が50\times50=250なので、すべての始点と終点のペアについて実際に到達可能か全探索するだけで良いっぽい。

Problem - C - Codeforces

与えられた異なった数値の集合に対して、ある要素が別の要素のk倍したものになっていない最大の部分集合を求める。

要素を大きい方から見ていって、要素をkで割ったものがあったら取り除いていけば良い。
k=1のときの場合分けを忘れていて大幅にタイムロス。

import sys
import collections
import bisect

n, k = map(int, sys.stdin.readline().split())
seq = map(int, sys.stdin.readline().split())

seq.sort(reverse=True)
cand = set(seq)
if k == 1:
    print len(cand)
    sys.exit(0)
for s in seq:
    if s / k <= 0:
        break
    if s not in cand:
        continue
    if s % k == 0 and s / k in cand:
        cand.remove(s / k)
print len(cand)