Codeforces Testing Round #1
はい。最終更新日:2014/05/16
codeforcesの致命的なエラーで吹っ飛んだ提出を書きなおして再提出したりしてます。
http://codeforces.com/contest/52
A. 123-sequence
implementation
ざっくりと大意
・全てが同じ数になるような最小の交換数?
方針のようなもの
・全体の要素数の中から最大の要素を抜けば必要な交換数じゃないかな。
n=int(raw_input()) l=[int(x) for x in raw_input().split()] print n-max(l.count(1),l.count(2),l.count(3))
通るけど他の人に比べるとすごい遅い。
n=int(raw_input()) l=raw_input().count print min(l('1')+l('2'),l('1')+l('3'),l('2')+l('3'))
何人かの回答を覗き見してこんな風にして時間を1/10くらいに短縮。。すげぇ。。。。以下コレは知らなかった、コレが時間短縮に繋がったなど
l=raw_input().count; l('1')
で入力受取処理しながらカウントして保存するらしい。ただ与えられるものが事前に明確で種類が少ない時じゃないと使いにくいかも。。。
どうしてもリスト形式出ないといけない訳でなかったら.split()しないほうが少しでも短縮できるっぽい
nからa,b,cいずれかの最大を引いて最小の数を求めるのはa,b,cから2つ選んだ和と同じだった。同じ結果になる式などは幾つか考えあげて一番処理しやすい方法から試すと複雑な問題も多少はやりやすくなるかもしれない
B. Right Triangles
combinatorics
ざっくりと大意
・最大で10001000の領域の中ので作られる直角三角形を数える
方針のようなもの
・縦列に何個があるかをメモしておき、横(底辺で想定?)の組合せでをメモした頂点の分だけ三角があるのでは?
n,m=map(int,raw_input().split()) l,chk=[],[] ans=0 for i in range(n): l.append(raw_input()) for i in range(m): cnt=0 for j in range(n): if l[j][i]=='*': cnt+=1 chk.append(cnt) for i in range(n): c=l[i].count('*') if c>1: for j in range(m): if l[i][j]=='*' and chk[j]>1: ans+=((chk[j]-1)*(c-1)) print ans
中々時間が短くならずTLEが続いた。。
TLE抜けだしたのはc=l[i].count('*')
countで数えた結果を保存せずに同じのでも毎回countしてたらデータの大きさによってはバカに出来ない差になるようだ><><
C. Circular RMQ
data structures
ざっくりと大意
・