Codeforces Round #710 (Div. 3) A, C

A. Strange Table

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        ll n, m, x;
        cin >> n >> m >> x;
        if(x%n == 0) cout << (n-1)*m + (ll)ceil((double)x/n) << "\n";
        else cout << (x%n-1)*m + (ll)ceil((double)x/n) << "\n";
    }
    return 0;
}

n 행 m 열로 이루어진 테이블에 숫자를 채우려고 한다. 세로로 숫자를 매겨 나가면 by columns, 가로로 숫자를 매겨 나가면 by rows 라고 할 때, by columns 에서의 x 값 위치가 by rows 에서 어떤 값인지를 묻는 문제이다.

by columns 는 세로로 값을 매겨 나가므로 x 는 x%n 행, x/n 열에 존재한다. (x%n == 0 일 경우는 n 행, x/n-1 열)
알아낸 x 값의 행, 열 정보를 이용해 by rows 의 값 (행번호 - 1) * m + (열번호) 을 구할 수 있다.

C. Double-ended Strings

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        string a, b;
        cin >> a >> b;
        int n = a.size();
        int m = b.size();
        a = ' ' + a;
        b = ' ' + b;
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        int ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(a[i] == b[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        cout << n+m-2*ans << "\n";
    }
    return 0;
}

Longest Common Substring 을 구하는 문제이다. 문자열 a, b 의 길이가 최대 20 뿐이라 모든 부분 문자열을 확인 O(n²m) 하는 방법으로도 통과할 수 있지만 O(nm) 복잡도가 나오는 dp 로 풀이하였다.

후기

b 번이 조금 까다롭게 나온 것 같다. div.3 이라 세문제는 풀고 싶었는데 아쉽다.