AtCoder Beginner Contest 073

atcoder

はい。
https://beta.atcoder.jp/contests/abc073

A - September 9

Python3

print("Yes" if "9" in input() else "No")

文字列で9が入ってるかを確認した。90で割り算して商が1か、余りが9かとかでも判定できそうな気がする。試してませんけど。

B - Theater

Pyhthon3

n=int(input())
ans=0
for i in range(n):
    l,r=map(int,input().split())
    ans+=r-l+1
print(ans)

l,rの差分+1が連続して座っている人数。それの和が劇場全体で座っている人数だと思う。

C - Write and Erase

Python3

n=int(input())
l=set()
for i in range(n):
    a=int(input())
    if a in l: l.remove(a)
    else: l.add(a)
print(len(l))

set型でaddしたりremoveしたりして、最後にlenで要素数を出力で大丈夫だと思う。

D - joisino's travel

C++

#include<bits/stdc++.h>
using namespace std;
#define inf 1<<29
 
int n,m,r;
int d[201][201];
int a,b,c;
int res;
 
void warshall_floyd(int n) {
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) d[j][k]=min(d[j][k], d[j][i]+d[i][k]);
}
 
int main(){
    scanf("%d %d %d",&n,&m,&r);
    vector<int> w(r);
    for (int i=0;i<r;i++) scanf("%d",&w[i]);
    sort(w.begin(),w.end());
    for (int i=0;i<201;i++) for (int j=0;j<201;j++) d[i][j]=inf;
    for (int i=0;i<m;i++) {
        scanf("%d %d %d",&a,&b,&c);
        d[a][b]=c;
        d[b][a]=c;
    }
    warshall_floyd(n+1);
    int ans=inf;
    do {
        int p,chk=0;
        for (int i=0;i<r;i++) {
            if (i==0) {
                p=w[i];
            } else {
                chk+=d[w[i]][p];
                p=w[i];
            }
        }
        ans=min(ans,chk);
    } while (next_permutation(w.begin(),w.end()));
    printf("%d\n",ans);
    return 0;
}

町A、町Bの距離がCなのを全て記録します。ワーシャルフロイドでそれぞれの町の間の最小移動距離を調べておきます。
R個の町をnext_permutationで全ての順序を試します。全ての順序を試すことで、サンプル1のような町1から町3に最小で移動するのには町2を通過しているような場合には移動順が1,2,3となる時に検出されるはずです。なのでワーシャルフロイドで距離を調べておいて、全移動順を試すことで解が見つかるはずです。多分。