Codeforces Beta Round #18 (Div. 2 Only)
はい。
http://codeforces.com/contest/18
A. Triangle
brute force,geometry
ざっくりと大意
・3点の座標が与えられる。
・既に直角三角形ならRIGHT、どれかの座標を1動かして作れればALMOST、それでも作れなければNEITHERを出力??
方針のようなもの
・直角三角形の判定に元々の座標、1動かした場合の全パターンを放り込んで調べる??
x1,y1,x2,y2,x3,y3=map(int,raw_input().split()) def len(a,b,c,d): length=abs(a-b)**2+abs(c-d)**2 return length def jg(e,f,g): l=[e,f,g] p=l.pop(l.index(max(l))) if p==l[0]+l[1] and min(l)!=0: return 1 else: return 0 x=len(x1,x2,y1,y2) y=len(x2,x3,y2,y3) z=len(x3,x1,y3,y1) if jg(x,y,z): print 'RIGHT' exit() chk=[x1,y1,x2,y2,x3,y3] for i in range(12): k=chk[:] if i<6: k[i]+=1 else: k[i%6]-=1 x=len(k[0],k[2],k[1],k[3]) y=len(k[2],k[4],k[3],k[5]) z=len(k[4],k[0],k[5],k[1]) if jg(x,y,z): print 'ALMOST' exit() print 'NEITHER'
後でもう少し綺麗に書ける気がする。。 三角比のa2+b2=c2なら直角三角形になるの判定方法に基づいて書きました。最初は座標をいじらずに各座標間での辺の長さから三角比の式が成立するか判定、成立がなかったら6点の座標をそれぞれ +1する場合と-1する場合で12回ループして成立すればALMOSTなければNEITHERになる。座標を動かして重なってしまうケースが有るらしいので要注意。
C. Stripe
data structures,implementation
ざっくりと大意
・Bobはなんか正方形の縞模様?か格子状?の紙を取り出す?
・その四角の中に負の数をふくむ数が入っている?
・どこかで2つに分けてそれぞれの和が等しくなるような区切り方がいくつあるか??
・サンプル1を見ると-6 7の間、-16 0の間、0 -2の間で区切るのがそれぞれ左右とも和が0になるパターンかな。
・サンプル2は和が等しくなる区切り方なしで0、サンプル3は2つしかない数の中央で区切って左右とも0で区切り方1つって感じかな?
方針のようなもの
・はじから全部計算で間に合うのか??
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() n=int(raw_input()) ans,l=0,[] l=map(int, raw_input().split()) x=n*-1 kari=sum(l) while 1: chk=set(l) if len(chk)==1 and sum(chk)==0: ans=n-1 break for j in range(-1,x,-1): ri=sum(l[j:]) if ri==(kari-ri): ans+=1 # if abs(kari-ri)-abs(ri)<0 and max(l[:j])<sum(l[j:]): # if abs(ri)-abs(kari-ri)<0: # break break print ans
TLEが解決できずで82416のkusanoさんの回答を見ました。。
n = input() s = [int(x) for x in raw_input().split()] c = 0 l,r = 0,sum(s) for i in xrange(n-1): l += s[i] r -= s[i] if l == r: c += 1 print c
入力の2行の受け取り方は特に時間の掛かる要因とはなっていなかったようです。 大きな分かれ目はlistの和を、sumをforで毎周計算するかforの外で一回だけかが大きかったかと。