社会人エンジニアがatcoderで茶色を目指す#7

ABCの復習。

##[D - Teleporter](https://atcoder.jp/contests/abc167/tasks/abc167_d)
問題文はAtCoderを参照してください。
コンテスト中の考察は、

- 周期を計測するプログラムを組む
- 周期に入るまでの移動をbeginとして(Kーbegin)%周期を求める問題だと考察

```C++:C++
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N, 0);
    vector<int> r;
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    int begin=0;
    int end=0;
    int c=0;
    int now=1;
    r.push_back(1);
    while(c<N+1){
        now = A[now-1];
        c++;
        for(int i=0; i<r.size(); i++){
            if(r[i] == now){
                begin=i;
                end=c;
                goto END;
            }
        }
        r.push_back(now);
    }
    
    END:
    
    int cycle = end-begin;
    long long var = 0;
    
    if(cycle>=K) var = K;
    else var = (K-begin) % cycle;
    
    c=0;
    now=1;
    while(c<begin+var){
        now = A[now-1];
        c++;
    }
    
    cout << now << endl;
    return 0;
}

```

TLEとWAにて回答ならず。
ここからは解説を読み、復習したプログラム。
- そもそもO（N^2）ではACにならない。
- 移動量を記録する配列を用意し、O(N)にすることがこの問題の本質

```C++:C++
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N, 0);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    
    int now=1;
    vector<long long> ord(N+1, -1);
    vector<int> position;
    
    while(ord[now] == -1){
        ord[now] = position.size();
        position.push_back(now);
        now = A[now-1];
    }
    
    long long cycle = position.size() - ord[now];
    long long b = ord[now];
    
    if(K <= b) cout << position[K] << endl;
    else {
        K = K - b;
        K = K % cycle;
        cout << position[b+K] << endl;
    }
    
    return 0;
}
```

この問題の本質の部分は下記の部分です。
計算結果を全て保持しておき、O(N)にすることです。
D問題からは計算結果を全て保持して後の計算を減らす工夫が大事になってきます。

```C++:C++
    while(ord[now] == -1){
        ord[now] = position.size();
        position.push_back(now);
        now = A[now-1];
    }
```

##[E - This Message Will Self-Destruct in 5s](https://atcoder.jp/contests/abc166/tasks/abc166_e)
問題文はAtCoderを参照してください。

- とりあえず提出してABCに記念参加したかった。
- O(N＾２)ではなくO(N)にしないといけない問題
- しかし解法が分からず全探索

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    long long n;
    long long ans=0;
    
    cin >> n;
    
    vector<long long> A(n);
    
    for(long long i=0;i<n;i++){
        cin >> A[i];
    }
    
    for(long long i=0;i<n;i++){
        for(long long j=i+1;j<n;j++){
            if(abs(i-j)==A[i]+A[j]){
                ans++;
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}
```

ここから解説を読みました。
- j-i == A[i]+A[j]ではなく
- j-A[j] == A[i]+i
- と考えたとき、どうなるか

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> A(n);
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    
    long long ans=0;
    map<int, int> map;
    for(int i=0;i<n;i++){
        int s = i-A[i];
        ans += map[s];
        int w = i+A[i];
        map[w]++;
    }
    
    cout << ans << endl;
    
    return 0;
}

```

##[B - Ruined Square](https://atcoder.jp/contests/abc108/tasks/abc108_b)
問題文はAtCoderを参照してください。

- 最初は角度0度の正方形でプログラムをしてましたがWAになる。
- ３０度傾けた正方形で式を組み直しました。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;
 
int main(int argc, const char * argv[]) {
    
    vector<int> x(4, 0);
    vector<int> y(4, 0);
    
    for(int i=0; i<2; i++){
        cin >> x[i];
        cin >> y[i];
    }
    
    cout << x[1]-(y[1]-y[0]) << " ";
    cout << y[1]+(x[1]-x[0]) << " ";
    cout << x[0]-(y[1]-y[0]) << " ";
    cout << y[0]+(x[1]-x[0]) << endl;
    
    return 0;
}
```

##[B - Two Colors Card Game](https://atcoder.jp/contests/abc091/tasks/abc091_b)
問題文はAtCoderを参照してください。

- mapでkey毎にカウントをとる
- 青と赤の差分を出す

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int N, M;
    map<string, int> blue;
    map<string, int> red;
    
    cin >> N;
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        blue[s]++;
    }
    
    cin >> M;
    for(int i=0; i<M; i++){
        string s;
        cin >> s;
        red[s]++;
    }
    
    int m=0;
    for( auto i = blue.begin(); i != blue.end() ; ++i ) {
        int d=0;
        if(red.count(i->first) > 0) d=red[i->first];
        m = max(i->second-d, m);
    }
    
    cout << m << endl;
    
    return 0;
}
```