読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest #002 復習

はい。
http://abc002.contest.atcoder.jp/

A - 正直者

Python2

print max(map(int, raw_input().split()))

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int mod=1000000007;
    int x,y;
    scanf("%d %d",&x,&y);
    printf("%d\n",max(x,y));
    return 0;
}

max使って大きい方の値を出力すれば大丈夫そう。

B - 罠

Python2

w=raw_input()
print w.replace('a','').replace('i','').replace('u','').replace('e','').replace('o','')

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int mod=1000000007;
    char w[31];
    scanf("%s",w);
    int chk=strlen(w);
    for (int i=0;i<chk;i++){
        if (w[i]!='a' && w[i]!='i' && w[i]!='u' && w[i]!='e' && w[i]!='o') {
            printf("%c",w[i]);
        }
    }
    printf("\n");
    return 0;
}

Pythonだと .replace('a','').replace('i','')... のようにreplaceは2つ以上繋げて使って文字列を整形して?出力。C++だと1文字ずつ読んでaiueo以外なら出力を言う感じで処理した。なお、今回は関係ないですけどreplaceを繋げて使う場合は繋げ順や挙動に注意が必要。

他の人の解で全く未知の手法で http://abc002.contest.atcoder.jp/submissions/110826 にstring.maketransを利用しているものがあった。stringモジュールはよく見ておいたほうが良いかな。

C - 直訴

Python2

xa,ya,xb,yb,xc,yc=map(int,raw_input().split())
a=xb-xa
b=yb-ya
c=xc-xa
d=yc-ya
print abs(a*d-b*c)/2.0

符号付き面積の公式を使うのが便利っぽい |ad−bc|⁄2 3辺の長さから面積を求めるヘロンの公式でも可能ではあるが辺の長さを求める手間を省くべきなのでアレ。

D - 派閥

Python2

n,m=map(int,raw_input().split())
d=[[0]*n for i in range(n)]
ans=chk=1
for i in range(m):
    x,y=map(int,raw_input().split())
    d[x-1][y-1]=1
    d[y-1][x-1]=1
for i in range(1<<n):
    w=[]
    for j in range(n):
        if (i>>j&1):
            w.append(j)
    chk=1
    f=0
    for x in w:
        for y in w:
            if x!=y and d[x][y]==0:
                f=1
                break
        if f:
            break
    if f==0:
        ans=max(ans,len(w))

print ans

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int mod=1000000007;
    int n,m,x,y;
    scanf("%d %d",&n,&m);
    //bool c[n][n]={0};
    bool c[n][n];
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            c[i][j]=false;
        }
    }
    for (int i=0;i<m;i++) {
        scanf("%d %d",&x,&y);
        c[x-1][y-1]=true;
        c[y-1][x-1]=true;
    }
    int ans=1;
    for (int i=0;i<(1<<n);i++) {
        //bool d[n]={0};
        bool d[n];
        for (int a=0;a<n;a++) {
            d[a]=false;
        }
        for (int j=0;j<n;j++) {
            if (i>>j & 1) {
                d[j]=true;
            }
        }
        int f=0;
        for (int p=0;p<n;p++) {
            for (int q=p+1;q<n;q++) {
                if (d[p] && d[q]) {
                    if (c[p][q]==false) {
                        f=1;
                        break;
                    }
                }
            }
            if (f==1) break;
        }
        int chk=0;
        if (f==0) {
            for (int x=0;x<n;x++) {
                if (d[x]==true) chk++;
            }
        }

        ans=max(ans,chk);
    }
    printf("%d\n",ans);
    return 0;
}

bitで全探索をする手法。仮のグループを作成して、仮のグループのメンバーそれぞれを知り合いか調べて知り合いでなかったらフラグを立ててbreakで抜ける。仮のグループの調査を全員知り合いで完走出来たら、選んだ中で互いが全員知り合いのグループとなる。完走出来たもののうちで人数が最も多いものが解になる。pythonC++も大体同じ方針で書いてるはずです。