AtCoder Beginner Contest 275

## [A - Find Takahashi](https://atcoder.jp/contests/abc275/tasks/abc275_a)

O(N)
最も値の大きい要素のindexを表示する。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    map<int, int> mp;
    rep(i, N){
        int h;
        cin >> h;
        mp[h] = i+1;
    }
    cout << mp.rbegin()->second << endl;
    return 0;
} 
```

## [B - ABC-DEF](https://atcoder.jp/contests/abc275/tasks/abc275_b)

O(1)
modに関する問題です。
「998244353」は9桁です。
「998244353 * 998244353」は18桁以内に収まります。
A,B,C,D,E,Fのmodを取り、-,*の計算毎にmodをとる事で良さそうです。
ただし,-の計算時に答えが負の値になった際、998244353を加算する必要があります。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

ll mod = 998244353;

int main() {
    ll A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    A %= mod;
    B %= mod;
    C %= mod;
    D %= mod;
    E %= mod;
    F %= mod;
    ll res = (A * B % mod * C % mod) - (D * E % mod * F % mod);
    if(res<0) res += mod;
    cout << res << endl;
    return 0;
} 
```

## [C - Counting Squares](https://atcoder.jp/contests/abc275/tasks/abc275_c)

O(81^4*5)
正方形の条件は、全ての辺の長さが等しい、２つの対角線の長さが等しい事です。
'#'の座標を全て管理し、４点の組み合わせが正方形か判定します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int H = 9;
int W = 9;
vector<P> graph;

bool isSquare(vector<int>& x, vector<int>& y){
	vector<int> v;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++) {
			int dx = x[i] - x[j], dy = y[i] - y[j];
			v.push_back(dx * dx + dy * dy);
		}
	sort(v.begin(), v.end());
	int l = v[0];
	if (l == 0) return false; 
	return v[0]==l && v[1]==l && v[2]==l && v[3]==l && v[4]==l*2 && v[5]==l*2;
}

void solve(vector<string> S){
    rep(i, H){
        rep(j, W){
            if(S[i][j] == '#') graph.push_back(P(i+1, j+1));
        }
    }

    int n = graph.size();
    int res = 0;
    repx(i, 0, n){
        repx(j, i, n){
            repx(k, j, n){
                repx(l, k, n){
                    vector<int> x({graph[i].first, graph[j].first, graph[k].first, graph[l].first});
                    vector<int> y({graph[i].second, graph[j].second, graph[k].second, graph[l].second});
                    if(isSquare(x, y)){
                        res++;
                    }
                }
            }
        }
    }
    cout << res << endl;
}

int main() {
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    solve(S);
    return 0;
} 
```

## [D - Yet Another Recursive Function](https://atcoder.jp/contests/abc275/tasks/abc275_d)

O(logN)
DFS、メモ化再帰です。
10^18の配列は確保できません。
map（ハッシュ）使いましょう。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

map<ll, ll> mp;

ll dfs(ll K){
    if(mp.find(K) != mp.end()) return mp[K];
    if(K==0) return 1;
    ll res = dfs(K/2) + dfs(K/3);
    mp[K] = res;
    return res;
}

int main() {
    ll N;
    cin >> N;
    cout << dfs(N) << endl;
    return 0;
} 
```

## まとめ
ABCDの４問の早解のコンテストでした。