問題 A

解法の考え方

入力値7個が全て{1,2,3,5,6}のいずれかであるかを検証する。無効な値が1つでもあれば即時判定する。

コード例

#include <iostream>
using namespace std;

bool isValid(int val) {
    return val == 1 || val == 2 || val == 3 || val == 5 || val == 6;
}

int main() {
    int tmp;
    for (int i = 0; i < 7; i++) {
        cin >> tmp;
        if (!isValid(tmp)) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

問題 B

解法の考え方

配列を昇順ソート後、中央位置の要素を取得しその値から1を減算した結果を出力する。

コード例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int num;
    cin >> num;
    vector<int> arr(num);
    for (auto &elem : arr) cin >> elem;
    sort(arr.begin(), arr.end());
    cout << arr[num/2] - 1 << endl;
    return 0;
}

問題 C

解法の考え方

長さnの文字列で長さmの部分列を含まない文字列を構築する。周期(n-m)の文字パターンを使用し、条件を満たさない場合は存在不可と判定。

コード例

#include <iostream>
using namespace std;

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        int n, m;
        cin >> n >> m;
        if (n == m || n - m > 26) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        for (int i = 0; i < n; i++) 
            cout << (char)('a' + i % (n - m));
        cout << endl;
    }
}

問題 D

解法の考え方

各文字の最終出現位置を記録し、順方向・逆方向に走査して「次に同じ文字が存在する」最大位置を求める。

コード例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int calcMaxPos(string s) {
    vector<int> lastPos(26, 0);
    for (int i = 0; i < s.size(); i++)
        lastPos[s[i]-'a'] = i;
    
    int result = 0;
    for (int i = 0; i < s.size(); i++)
        if (lastPos[s[i]-'a'] != i) 
            result = i + 1;
    return result;
}

int main() {
    int len;
    string seq;
    cin >> len >> seq;
    
    int ans = calcMaxPos(seq);
    reverse(seq.begin(), seq.end());
    ans = max(ans, calcMaxPos(seq));
    
    cout << ans << endl;
    return 0;
}

問題 E

解法の考え方

累積和配列を構築し、RMQで区間最小値を効率的に取得。クエリ毎に前処理済みデータから結果を算出。

コード例

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

struct RangeMinQuery {
    vector<vector<ll>> st;
    int sz;
    
    RangeMinQuery(vector<ll> data, int n) : sz(n) {
        st.resize(n+1, vector<ll>(21));
        for (int i=1; i<=n; i++) st[i][0] = data[i];
        for (int j=1; (1<<j) <= n; j++) {
            int w = 1 << j;
            for (int i=1; i+w-1<=n; i++) 
                st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
    
    ll query(int l, int r) {
        int k = log2(r-l+1);
        return min(st[l][k], st[r-(1<<k)+1][k]);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n+1), sum(n+1,0);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }
    
    vector<ll> tmp(n+1);
    for (int i=1; i<=n; i++) 
        tmp[i] = sum[i-1] - a[i];
    
    RangeMinQuery rmq(tmp, n);
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l == r) {
            cout << 0 << endl;
            continue;
        }
        ll base = sum[l-1];
        ll minVal = rmq.query(l+1, r);
        cout << abs(min(0LL, minVal - base)) << endl;
    }
}

問題 F

解法の考え方

ビット単位の分析により(x AND y)+(x OR y)=x+yを証明。条件を満たすペア数は区間長と等しい。

コード例

#include <iostream>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        long long L, R;
        cin >> L >> R;
        cout << R - L + 1 << endl;
    }
    return 0;
}

問題 G

解法の考え方

冪乗計算を反復的に行い、基準値との差分が最小となる指数を探索する。

コード例

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        long long base, mult;
        cin >> base >> mult;
        long long cur = mult;
        int cnt = 1;
        while (abs(base - cur * mult) < abs(base - cur)) {
            cur *= mult;
            cnt++;
        }
        cout << cnt << endl;
    }
}

問題 H

解法の考え方

矩形の辺長を比較し、より長い辺方向に三角形の頂点を配置して最大面積を達成。

コード例

#include <iostream>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        if (b-a < d-c) {
            cout << a << " " << c << endl;
            cout << a << " " << c+1 << endl;
            cout << a+1 << " " << d << endl;
        }
        else {
            cout << a << " " << d << endl;
            cout << a+1 << " " << d << endl;
            cout << b << " " << d-1 << endl;
        }
    }
}

問題 J

解法の考え方

入力データを指定年月でフィルタリング後、時間帯別にユーザーを分類して重複排除した計数を出力。

コード例

#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

int main() {
    int n, year, month;
    cin >> n >> year >> month;
    
    vector<set<string>> res(3);
    
    for (int i=0; i<n; i++) {
        string user, date, time;
        cin >> user >> date >> time;
        
        int y = stoi(date.substr(0,4));
        int m = stoi(date.substr(5,2));
        if (y != year || m != month) continue;
        
        int h = stoi(time.substr(0,2));
        int totalSec = h*3600 + stoi(time.substr(3,2))*60 + stoi(time.substr(6,2));
        
        if ((totalSec >= 25200 && totalSec <= 32400) || 
            (totalSec >= 64800 && totalSec <= 72000)) 
            res[0].insert(user);
        else if (totalSec >= 39600 && totalSec <= 46800)
            res[1].insert(user);
        else if (totalSec <= 3600 || totalSec >= 79200)
            res[2].insert(user);
    }
    
    for (int i=0; i<3; i++) 
        cout << res[i].size() << " ";
    cout << endl;
}

問題 K

解法の考え方

グリッド上の連結成分をBFSで探索し、各成分に隣接する空白セルの最小数を算出する。

コード例

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (auto &row : grid) cin >> row;
    
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<vector<int>> compID(rows, vector<int>(cols, 0));
    int minBlank = INT_MAX;
    int compCount = 0;
    
    for (int i=0; i<rows; i++) {
        for (int j=0; j<cols; j++) {
            if (visited[i][j] || grid[i][j] != '1') continue;
            
            compCount++;
            queue<pair<int,int>> q;
            q.push({i,j});
            visited[i][j] = true;
            int blankCount = 0;
            
            while (!q.empty()) {
                auto [x,y] = q.front();
                q.pop();
                
                for (int k=0; k<4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx<0 || nx>=rows || ny<0 || ny>=cols) continue;
                    
                    if (grid[nx][ny]=='1' && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.push({nx,ny});
                    }
                    else if (grid[nx][ny]=='0') {
                        if (compID[nx][ny] != compCount) {
                            blankCount++;
                            compID[nx][ny] = compCount;
                        }
                    }
                }
            }
            minBlank = min(minBlank, blankCount);
        }
    }
    cout << minBlank << endl;
}