AtCoder Regular Contest #018 oxo-

AtCoderのコンテストに久しぶりに参加(現実逃避
A,C問題を解けたのにB問題を解けずorz
131/339位でした

• 順位表 - AtCoder Regular Contest #018 | AtCoder

C問題をPythonで正解した人の中では最速だったみたいです(そもそもPythonでやっている人があまりいない

AtCoderでコンテストあったらしいのでAtCoder Statistics更新しました URL

2014-03-01 22:38:33 via web

AtCoderの方の解説

みんなが嵌ってそうなところをざっくり説明すると、Ｂ：数字が大きいよ！int型だと上手くいかないかも！Ｃ：乱数生成式に注目！全部の数字が違う数字か、先頭除いて全部同じ、の２パターンしかないよ！Ｄ：行列木定理を覚えよう！って感じです。きちんとした解説は後日出します！

2014-03-01 22:36:33 via web

AtCoder Regular Contest 018解説のアップロードしました！　URL

2014-03-02 12:57:27 via web

A: BMI - AtCoder Regular Contest #018 | AtCoder

身長とBMIの値を読み込んで、体重を計算するだけ

H, B = map(float, raw_input().split())

print B * H * H / 10000

B: 格子点と整数 - AtCoder Regular Contest #018 | AtCoder

二次元空間上の格子点(座標が整数の点)が複数与えられるので、それらを使って面積が整数の三角形がいくつ作れるかを答える
個人的にはB問題にしては難しいような……

時間中は何故か動かなかった
以下正解する版

import itertools
import collections

P = collections.namedtuple('Point', 'x y')

def area2(p1, p2, p3):
    return abs((p1.x - p3.x) * (p2.y - p1.y) - (p1.x - p2.x) * (p3.y - p1.y))

N = int(raw_input())

v = [P(*map(int, raw_input().split())) for i in xrange(N)]

count = 0
for c in itertools.combinations(v, 3):
    a = area2(*c)
    
    if a != 0 and a % 2 == 0:
        count += 1
print count

C: 席替え - AtCoder Regular Contest #018 | AtCoder

学生の成績と位置が与えられる。
前の列は後ろの列よりも成績が低いという制約のもとで並び替えた時、学生の移動したマンハッタン距離を最小にする。
C問題なので貪欲にやれば通るかな？と思って何も考えずに適当にソートしたら通ってしまった……

N, M = map(int, raw_input().split())
x, a, p = map(int, raw_input().split())

candidate = []
for i in xrange(N):
    for j in xrange(M):
        candidate.append((x, i, j))
        x = (x + a) % p

candidate.sort()

cost = 0
for i in xrange(N):
    row = candidate[i*M:(i+1)*M]
    row.sort(key=lambda x:x[2])
    for j, r in enumerate(row):
        cost += abs(i - r[1]) + abs(j - r[2])
print cost