2010年04月20日

code golf その14

ニン。続いてはTotal Triangles
数値で構成された三角形の頂点から下辺までのルート(位置的に下になる数値2つのみを通ることが可能)で最大となる値を求めればよい。
例えば、入力が下記の通りである場合、
   4
  4 1
 1 4 1
1 4 1 1
最大となるルートは
   4
  4 1
 1 4 1
1 4 1 1
となるので、求める答えは16となる。なお、実際の入力値は左詰した状態となっている。
4
4 1
1 4 1
1 4 1 1
こんな感じ。では第一弾。
import sys
I=[map(int, x.split())for x in sys.stdin]
T=[0]*99
for v in I:
	q=[0]*99
	i=0
	for c in v:
		q[i]=max(T[i],T[i-1])+c
		i+=1
	T=q
print max(T)
例によって99という数値に根拠はない、ということもない。最大で50行との事なので十分。これで152byte。pythonのトップは、99byte。まさに桁違い。

import sys
T=[0]
for l in sys.stdin:
	q=[0]*99;i=0
	for c in l.split():q[i]=max(T[i],T[i-1])+int(c);i+=1
	T=q
print max(T)
入力周りを刷新。122byte。まだか。

import sys
T=[0]*99
for l in sys.stdin:T=map(lambda x,i:max(T[i],T[i-1])+int(x or 0),l.split(),range(99))
print max(T)
ループを1つ消してみる。これで118byte。maxの引数をどうにか出来そうな気がするのだが、どうにもこうにも。

posted by s.s.s.r at 21:08| Comment(0) | TrackBack(0) | python | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック