問題 A - Codeforces

入力された四つの座標から、正方形の面積を求める問題です。各辺が軸に平行な正方形かどうかを判定し、辺の長さを計算して面積を求めます。

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

int main()
{
    int cases;
    cin >> cases;
    
    while(cases--)
    {
        int x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        
        if(x1 == x2)
        {
            int side = abs(y2 - y1);
            cout << side * side << endl;
        }
        else if(x2 == x3)
        {
            int side = abs(y2 - y3);
            cout << side * side << endl;
        }
        else if(x3 == x4)
        {
            int side = abs(y3 - y4);
            cout << side * side << endl;
        }
        else if(x4 == x1)
        {
            int side = abs(y4 - y1);
            cout << side * side << endl;
        }
        else if(x1 == x3)
        {
            int side = abs(y3 - y1);
            cout << side * side << endl;
        }
        else if(x2 == x4)
        {
            int side = abs(y2 - y4);
            cout << side * side << endl;
        }
        else if(y1 == y2)
        {
            int side = abs(x2 - x1);
            cout << side * side << endl;
        }
        else if(y2 == y3)
        {
            int side = abs(x2 - x3);
            cout << side * side << endl;
        }
        else if(y3 == y4)
        {
            int side = abs(x3 - x4);
            cout << side * side << endl;
        }
        else if(y4 == y1)
        {
            int side = abs(x4 - x1);
            cout << side * side << endl;
        }
        else if(y1 == y3)
        {
            int side = abs(x3 - x1);
            cout << side * side << endl;
        }
        else if(y2 == y4)
        {
            int side = abs(x2 - x4);
            cout << side * side << endl;
        }
    }
    
    return 0;
}

問題 B - Codeforces

文字列の比較と操作回数の最小化に関する問題です。一致していない位置にある0と1のペアを交換することで最適な状態に近づけます。

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

int main()
{
    int cases;
    cin >> cases;
    
    while(cases--)
    {
        int length;
        cin >> length;
        string source, target;
        cin >> source >> target;
        
        if(source == target) 
        {
            cout << 0 << endl;
        }
        else 
        {
            int ones = 0, zeros = 0;
            for(int i = 0; i < source.length(); i++)
            {
                if(source[i] == '1' && source[i] != target[i]) ones++;
                if(source[i] == '0' && source[i] != target[i]) zeros++;
            }
            
            int result = 0;
            if(ones > zeros)
            {
                result += zeros;
                ones -= zeros;
                result += ones;
                cout << result << endl;
            }
            else if(ones < zeros) 
            {
                result += ones;
                zeros -= ones;
                result += zeros;
                cout << result << endl;
            }
            else if(ones == zeros) 
            {
                result = ones;
                cout << result << endl;
            } 
        }
    }
    
    return 0;
}

問題 C - Codeforces

電池の残量と通信のタイミングを考慮した貪欲法の問題です。電池が十分にある限り、次のメッセージ送信までに必要な電力量を計算し、必要に応じてスリープまたは電源オフを選択します。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 10;
typedef long long LL;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int cases;
    cin >> cases;
    
    while(cases--)
    {
        LL messages, battery, standby, poweroff;
        cin >> messages >> battery >> standby >> poweroff;
        LL times[MAX_N];
        for(int i = 1; i <= messages; i++) 
            cin >> times[i];

        for(int i = 1; i <= messages; i++)
        {
            if(battery <= 0) 
                break;
            battery -= min((times[i]-times[i-1])*(LL)standby, poweroff);
        }
        
        if(battery > 0) 
            cout << "YES" << endl;
        else 
            cout << "NO" << endl;
    }
    
    return 0;
}

問題 D - Codeforces

二つの配列の要素を組み合わせて絶対値の差を最大化する問題です。各配列をソートし、最大と最小の要素を比較して貪欲に選択します。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 10;
typedef long long LL;
int array_a[MAX_N], array_b[MAX_N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int cases;
    cin >> cases;
    
    while(cases--)
    {
        int size_a, size_b;
        cin >> size_a >> size_b;
        
        for(int i = 1; i <= size_a; i++) 
            cin >> array_a[i];
        for(int i = 1; i <= size_b; i++) 
            cin >> array_b[i];
        
        sort(array_a + 1, array_a + 1 + size_a);
        sort(array_b + 1, array_b + 1 + size_b);
        
        LL total = 0;
        int start1 = 1, end1 = size_b;
        int start2 = 1, end2 = size_a;
        
        for(int i = 1; i <= size_a; i++)
        {
            if(abs(array_a[start1] - array_b[end1]) >= abs(array_a[end2] - array_b[start2]))
            {
                total += abs(array_a[start1] - array_b[end1]);
                start1++;
                end1--;
            }
            else 
            {
                total += abs(array_a[end2] - array_b[start2]);
                start2++;
                end2--;
            }
        }
        cout << total << endl;
    }
    
    return 0;
}