B - 格子点と整数: AtCoder Regular Contest 018

問題文
諸君、私は整数が好きだ。 私は格子点が好きだ。 私は面積が好きだ。 私は三角形が好きだ。 私は座標平面上の、頂点が全て格子点上にある、面積が整数の三角形が大好きだ。 格子点の集合をみたとき、その中の任意の 3 点を選んで作ることができる面積が整数の三角形の個数を数えるときは心が踊る。 心が踊るが、格子点が多いと数えるのが面倒臭い。 ぜひ有能なプログラマーである諸君に私の代わりに数えてほしい。 N 個の格子点を与えるので、その中の任意の 3 点を選んで作ることができる、面積が整数の三角形の個数を数えるプログラムを作って欲しい。面積が 0 の>三角形は三角形とは認めん! ちなみに、格子点というのは座標平面上の点 (x,y) のうち x も y も整数である点のことである。 atcoder

結果: WA

#include <iostream>
#include <cstdlib>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;

const int NMAX = 100;
typedef pair<int, int> pii;
vector<pii> xy;

int main(){
    int N;
    int num = 0;
    for (int i =0; i <N; ++i) {
        int x, y;
        cin >> x >> y;
        xy.push_back(make_pair(x, y));
    }
    sort(xy.begin(), xy.end());

    for (int i =0; i <N; ++i) {
        for (int j =i+1; j <N; ++j) {
            for (int k =j+1; k <N; ++k) {
                int area = abs( (xy[j].first-xy[i].first)*(xy[j].second-xy[i].second) - (xy[k].first-xy[i].first)*(xy[k].second-xy[i].second) );
                if ( area != 0 && area %2 ==0 ) {
                    num += 1;
                }
            }
        }
    }
    cout << num << endl;
    
    return 0;
}

A - 深さ優先探索: AtCoder Typical Contest 001

問題文

この問題は、講座用問題です。ページ下部に解説が掲載されています。 高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。 高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。 atcoder

結果: WA

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
const int MAX = 50;
bool reacable[MAX][MAX] = {};

void search(int x, int y);
int R, C;

int main(){
    int sx, sy;
    int gx, gy;
    
    cin >> R >> C;

    for (int i =0; i <R; ++i) {
        for (int j =0; j <C; ++j) {
            cin >> map[i][j];
            if (map[i][j] == 's') {
                sx = i;
                sy = j;
            } else if (map[i][j] == 'g'){
                gx = i;
                gy = j;
            }
        }
    }
    
    search(sx, sy);
    
    if ( reacable[gx][gy] ) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

void search(int x, int y){
    if ( x <0 || y <0 || x >=R || y >=C || map[x][y] == '#') {
        return;
    }
    if ( reacable[x][y]) {
        return;
    }
    
    reacable[x][y] = true;
    
    search(x+1, y); //right
    search(x-1, y); //left
    search(x, y+1); //up
    search(x, y-1); //down
}

C - Reconciled?: AtCoder Beginner Contest 065

問題文

すぬけ君は、犬を N 匹と猿を M 匹飼っています。すぬけ君は、この N+M 匹を一列に並べようと思っています。 文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。 このような並べ方は何通りあるでしょうか。犬と猿は 109+7以上の数を理解できないので、並べ方の個数を109+7で割ったあまりを求めてください。 ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

制約

1≦N,M≦105

結果: WA

#include <iostream>
#include <cstdlib>
 
using namespace std;
typedef long long ll;
const ll NUM = 1000000007;
 
int main(){
    int N, M;
    cin >> N >> M;
    ll result = 1;
 
    if ( abs(N-M) >1) {
        cout << 0 << endl;
        return 0;
    } else if ( N == M){
        for (int i =0; i <N; ++i) {
            if (i =0) {
                result *= ( (N+M) % NUM);
            }
            result *= ( (N-i) % NUM);
        }
        for (int i =0; i <M; ++i) {
            result *= ( (M-i) % NUM);
        }
    } else {
        for (int i =0; i <N; ++i) {
            result *= ( (N-i) % NUM);
        }
        for (int i =0; i <M; ++i) {
            result *= ( (M-i) % NUM);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

B - Trained?: AtCoder Beginner Contest 065

問題文

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。 AtCoder 社のトレーニング設備には N 個のボタンがついており、ちょうど 1 個のボタンが光っています。 ボタンには、1 から N までの番号がついています。 ボタン i が光っているときにそのボタンを押すと、ボタン i の明かりが消え、その後ボタン a_i が光ります。i=a_i であることもあります。 光っていないボタンを押しても、何も起こりません。 最初、ボタン 1 が光っています。高橋君は、ボタン 2 が光っている状態で、トレーニングをやめたいと思っています。 そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

制約

2≦N≦105

1≦a_i≦N

結果:TLE

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
const int NMAX = 100000;
int main(){
    int N;
    vector<int> a;
    vector<int> passed;
    int button = 0;
    cin >> N;
    for (int i =0; i <N; ++i) {
        int input;
        cin >> input;
        a.push_back(input);
    }
    
    int on_now = 1;
    passed.push_back(on_now);
    for (int i =0; i <NMAX; ++i) { //pressing i-th button
        on_now = a[on_now-1];
        auto itr = std::find(passed.begin(), passed.end(), on_now);
        if( itr != passed.end() ) {
            cout << -1 << endl;
            break;
        }
        
        passed.push_back(on_now);
        button += 1;
        if (on_now == 2) {
            cout << button << endl;
            break;
        }
        
    }
    
    return 0;
}