Atcoder Beginner Contest #012

ABC過去問解きその3。#013、#014に比べてだいぶ簡単な問題セットだったので全問自力で解答できた。初心者向けの内容。問題はこちら。

A: スワップ

A と B が与えられるので、順番を入れ替え B, A の順番で出力する問題。

a,b = map(int,raw_input().split())
print b,a

B: 入浴

秒数 N が与えられるので、それを hh:mm:ss の形で出力する問題。hh,mm,ssの値が一桁の時は0詰めするのを忘れないようにする。

n = int(raw_input())
print "%02d:%02d:%02d"%(n//3600,n%3600//60,n%60)

C: 九九足し算

九九をすべて足しあわせたはずなのだが、1つだけ足すのを忘れてしまい値は N となってしまった。忘れてしまった可能性のある掛け算をすべて昇順に答えていく問題。答えは必ず1つ以上ある。

素因数分解をしてもいいのだが、面倒なので全探索をする。9x9 の81通りについて調べるだけなので計算時間的にも全く問題ない。i * j が足し忘れてしまった値に一致した時に i x j を出力すれば答えとなる。

n = int(raw_input())
m = 2025-n
for i in range(1,10):
    for j in range(1,10):
        if i*j == m: print i,"x",j

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

N 個のノードと M 本の重み付き無向辺が与えられる。あるノードから別のノードへは移動可能なことが保証されている。あるノードからの最も遠いノードへの距離について、その最小値を答える問題。

N が最大300なのでO(N³)のワーシャル・フロイド法で全点間距離を求めてやればいい。こうすれば、各点から見た最も遠い点の距離を比べることができ、答えを求めることができる。pythonだともう少しアルゴリズムの工夫をしないとTLEになってしまう。

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,a) FOR(i,0,a)
#define inf (1<<27)
using namespace std;

const int MAXN = 301;
int N,M,a,b,t;
int G[MAXN][MAXN];  // バス停間の移動時間を格納。

// 全点間の距離を求める
void warshall_floyd(){
    REP(k,N)
        REP(i,N)
            REP(j,N)
                G[i][j]= min(G[i][j], G[i][k]+G[k][j]);
}

int main(void){
    REP(i,MAXN) REP(j,MAXN) G[i][j] = (i == j ? 0:inf);  // Gの初期化
    cin >> N >> M;
    REP(i,M){
        cin >> a >> b >> t;
        a--; b--;
        G[a][b] = G[b][a] = t;
    }
    
    warshall_floyd();
    
    int ans = inf;
    REP(i,N){
        int tmp = 0;
        REP(j,N)
            tmp = max(tmp,G[i][j]);
        ans = min(ans,tmp);
    }
    cout << ans << endl;
    return 0;
}