AtCoder ABC #012 : Python練習編

すいません、DはPythonでTLE起こして解ききれていません。

ABC012は順調に解いて好順位に終わった。
あと30秒速めるにはどうしたらよかったのだろう。
http://abc012.contest.atcoder.jp/assignments

A - スワップ

2つの数値A,Bが与えられるので逆順で出力せよ。

一旦splitして逆順で連結。

import sys

a,b=raw_input().strip().split(" ")
print "%s %s" % (b,a)

B - 入浴時間

N秒をhh:mm:ssの形で出力せよ。

3600で割ったもの、60で割ったもの、その残りを順に表示する。

import sys

N=input()

h = N/3600
m = N/60%60
s = N%60

print "%02d:%02d:%02d" % (h,m,s)

C - 九九足し算

1*1～9*9の和をすべて足した際、１個式を足し忘れたところ和がNになった。
Nの候補を列挙せよ。

1*1～9*9の和を総当たりで一旦求める。その和をSとする。
再度1*1～9*9を総当たりし、その値がS-Nと一致するなら出力する。

1*1～9*9の和が2025になることは問題文から推測できるね。

import sys

N=input()
tot=0
for i in range(1,10):
	for j in range(1,10):
		tot+=i*j

for i in range(1,10):
	for j in range(1,10):
		if N+i*j == tot:
			print "%d x %d" % (i,j)

D - バスと避けられない運命

N頂点M距離付無向辺の連結グラフが与えられる。
ある頂点sを始点としたとき、そこから各頂点に最短経路で移動する際、最遠頂点までの移動距離をその頂点sのコストとする。
コストが最小となる始点sを選び、そのコストを答えよ。

Warshall-Floydで２点間の最短距離を列挙した上で、各頂点のコストを求めればよい。
残念ながら、PythonだとN<=100位まででないと間に合わない。
よって今回はC++のコードを記載する。

int N,M;
int mat[1000][1000];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	FOR(x,1000) FOR(y,1000) mat[x][y]=1<<25;
	FOR(x,1000) mat[x][x]=0;
	FOR(i,M) {
		cin>>x>>y>>j;
		mat[x-1][y-1]=mat[y-1][x-1]=j;
	}
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
	
	int mi=10000000;
	FOR(i,N) {
		x=0;
		FOR(j,N) x=max(x,mat[i][j]);
		mi=min(x,mi);
	}
	cout << mi << endl;
}

まとめ

初心者向けというなら、一般的なLLで通る制限にしてほしいかも。
それともDはO(N^3)より効率的な解法があるのだろうか。