AtCoder Beginner Contest 224

##A - Tires

O(1)

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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() {
    string s;
    cin >> s;
 
    int n = s.size();
    if(s.size() >= 2 && s.substr(n-2, 2) == "er") cout << "er" << endl;
    if(s.size() >= 3 && s.substr(n-3, 3) == "ist") cout << "ist" << endl;
 
    return 0;
}

##B - Mongeness

O(N^4)
N<=50で6250000です。
間に合いますね。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 A[50][50];
 
int main() {
    int H, W;
    cin >> H >> W;
 
    rep(i, H) rep(j, W) cin >> A[i][j];
 
    int sum=0;
    int cnt=0;
    for(int i1=0; i1<H; i1++){
        for(int i2=i1+1; i2<H; i2++){
            for(int j1=0; j1<W; j1++){
                for(int j2=j1+1; j2<W; j2++){
                    if(A[i1][j1] + A[i2][j2] <= A[i2][j1] + A[i1][j2]) sum++;
                    cnt++;
                }
            }
        }
    }
 
    if(cnt == sum) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
}

##C - Triangle?

O(N^3)
N<=300で27000000です。
間に合いますね。

問題は座標の最大値が10^9であること。
doubleとか小数の計算を考えるより、python3のが分かりやすいかなと思いました。

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce
 
# main
def main():
    N = int(input())
    x = [0] * N
    y = [0] * N
    for i in range(0, N):
        x[i], y[i] = list(map(int, input().split()))
 
    res=0
    for p in range(0, N):
        for q in range(p+1, N):
            for r in range(q+1, N):
                x1 = x[q] - x[p] 
                x2 = x[r] - x[p] 
                y1 = y[q] - y[p] 
                y2 = y[r] - y[p]
 
                ans = abs((x1 * y2) - (x2 * y1)) / 2
                if ans>0:
                    res = res + 1
 
    print(res)
 
 
# エントリポイント
if __name__ == '__main__':
    main()