ABC437の記録

AtCoderBeginnerContest437の感想と自分が解いたところまでの解説を書いていきます
今回はAをjava、A,Bをpython、A,B,DをC++で解きます。
AtCoder Beginner Contest 437
今回もちゃんと解説書きます

1.感想

A問題：
すごく簡単
B問題：
すごく簡単
C問題：
なにこれ
D問題：
まあ簡単
E問題：
多分グラフなんだろうな
前回のほうが簡単だった
F問題：
セグ木かな

2.結果

まあ耐えたほうかな

3.解説

A問題 Feet

AとBを入力してA*12+Bを出力するだけ

pyhonでの解法

A, B = map(int, input().split())
print(A*12+B)

C++での解法

#include <bits/stdc++.h>
using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    cout << A*12+B << endl;
    return 0;
}

B問題 Tombola

グリッドを入力した時にグリッドを全探索して何行目かを記録して最大値を出力する

pythonでの解法

H, W, N = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
count = [0]*H

for i in range(N):
    a = int(input())
    for j in range(H):
        for k in range(W):
            if A[j][k] == a:
                count[j] += 1

print(max(count))

C++での解法

#include <bits/stdc++.h>
using namespace std;

signed main(){
    int H, W, N;
    cin >> H >> W >> N;
    vector<vector<int>> A(H, vector<int>(W));
    vector<int> count(H);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];

    while (N--){
        int a;
        cin >> a;
        for (int i = 0; i < H; i++) for (int j = 0; j < W; j++){
            if (A[i][j] == a) count[i]++;
        }
    }

    cout << *max_element(count.begin(), count.end()) << endl;
    return 0;
}

D問題 Sum of Differences

まずはBを昇順にソートしておいて累積はを作ります
そしたらA[i] < B[j]となるjを二分探索で見つけてそれの前ではA[i]との差を引、その後はA[i]との差を足します
最後にこれを998244353で割ったあまりを出力します

C++での解法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

signed main(){
    const ll mod = 998244353;
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M);
    for (ll &i : A) cin >> i;
    for (ll &i : B) cin >> i;
    sort(B.begin(), B.end());
    vector<ll> sum(M+1, 0);
    for (int i = 0; i < M; i++) sum[i+1] = sum[i]+B[i];

    ll ans = 0;
    for (int i = 0; i < N; i++){
        ll idx = upper_bound(B.begin(), B.end(), A[i])-B.begin();
        ll count_lower = idx, sum_lower = sum[idx]%mod;
        ll count_upper = M-idx, sum_upper = (sum[M]-sum[idx]+mod)%mod;
        ll res = (count_lower*A[i]%mod-sum_lower+sum_upper-count_upper*A[i]%mod+mod+mod)%mod;
        ans = (ans+res)%mod;
    }

    cout << ans << endl;
    return 0;
}