AtCoder Beginner Contest 030

[TakefumiYamamura]

http://abc030.contest.atcoder.jp/

[TakefumiYamamura]

C - 飛行機乗り

時間制限 : 2sec / メモリ制限 : 256MB

問題文

ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。

空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 空港Aから空港Bへの飛行機は N 本あり、i 番目の便は ai 時に出発します。 空港Bから空港Aへの飛行機は M 本あり、j 番目の便は bj 時に出発します。

ある飛行機には、出発する空港に出発する時刻以前にいれば乗ることができます。出発する時刻ちょうどに到着した場合も、すぐに飛行機に乗って出発できます。 高橋くんははじめ空港Aに 0 時にいます。 空港Aと空港Bの間を最大何往復できるか調べてください。

note

今の時間から乗れる飛行機があるかを2分探索するだけ

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

using namespace std;

int main(){
    long long n, m;
    long long x, y;
    cin >> n >> m;
    cin >> x >> y;

    vector<long long> a;
    vector<long long> b; 

    for (int i = 0; i < n; ++i)
    {
        long long tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    for (int i = 0; i < m; ++i)
    {
        long long tmp;
        cin >> tmp;
        b.push_back(tmp);
    }

    long long cur_time = 0;
    long long count = 0;

    vector<long long>::iterator a_index = a.begin();
    vector<long long>::iterator b_index = b.begin();

    while(*a_index != 0 && *b_index != 0){
        //while(!*a_index && !*b_index ){ why is this error?
        if (count % 2 == 0){
            a_index = lower_bound(a_index, a.end(), cur_time);
            if(!*a_index) break;
            count++;
            cur_time = *a_index + x;        
        }else{
            b_index = lower_bound(b_index, b.end(), cur_time);
            if(!*b_index) break;
            count++;
            cur_time = *b_index + y;
        }
    }

    cout << count / 2 << endl;
}

[TakefumiYamamura]

D - へんてこ辞書

時間制限 : 2sec / メモリ制限 : 256MB

問題文

ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 bi と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語も知らないので、単語 i の意味を調べようとしたとき、単語 bi の意味を調べようとします。ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。 しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。 ある単語 i を調べようとして、単語帳を参照し、単語 bi を調べようとするまでを1ステップとします。

ミカミくんが単語 i を調べようとして、k ステップ経ったとき、ミカミくんはどの単語を調べようとしているでしょうか？

note

kがおおきすぎて c++だと　unsigned long long におさまりきらないからjavaのbigInteger に逃げる。 ループしてる閉路をみつけてやればよい

import java.util.Scanner;
import java.math.BigInteger;
import java.util.Arrays;

class Node{

    int value;
    int parent;

    public Node(int value, int parent){
        this.value = value;
        this.parent = parent;
    }
}

public class abc30d {
    public static void main(String[] args) {
        StragneDictionary sd = new StragneDictionary();
        sd.exec();
    }
}

class StragneDictionary {

    int N;
    int A;
    BigInteger K;
    Node[] board;
    int startLoopPoint;
    int startLoopPointCount;
    int loopLength;

    public StragneDictionary() {
        Scanner cin = new Scanner(System.in);
        this.N = cin.nextInt();
        this.A = cin.nextInt() - 1;
        this.K = new BigInteger(cin.next());

        this.board = new Node[N];
        for (int i = 0; i < N ; i++) {
            board[i] = new Node(i, cin.nextInt() - 1);    
        }

    }

    void exec() {
        findLoop();

        int ans = this.A;

        if(K.compareTo( BigInteger.valueOf(startLoopPointCount) )  > 0) {
            K = K.subtract(BigInteger.valueOf(startLoopPointCount));
            K = K.remainder(BigInteger.valueOf(loopLength) );
            ans = startLoopPoint;
        }
        int sK =  K.intValue();

        for (int i = 0; i < sK ; ++i) {
            ans = board[ans].parent;
        }

        System.out.println(ans + 1);
    }

    void findLoop(){
        int count = 0;
        int cur = this.A;

        int hashTable[] = new int [100001];
        Arrays.fill(hashTable, -1);
        hashTable[cur] = 0;

        while(true){
            count++;
            cur = board[cur].parent;
            if(hashTable[cur] != -1) break;
            hashTable[cur] = count;
        }
        this.loopLength = count - hashTable[cur];
        this.startLoopPointCount = hashTable[cur];
        this.startLoopPoint = cur;
    }

}