Codeforces Round #663 (Div. 2) ABC

from sys import stdin
def input(): return stdin.readline().rstrip()
 
for i in range(int(input())):
    n=int(input())
    for _ in range(1,n+1):
        print(_,end=" ")
    print()

 

A - Suborrays

 

0분에 제출한 사람이 너무 많아서 단순히 n까지 출력하는 도박을 했고 AC를 받았다.

 

 

from sys import stdin
def input(): return stdin.readline().rstrip()

T=int(input())
for i in range(T):
    res=0
    r,c=map(int,input().split())
    for j in range(r):
        line=input()
        if j==r-1:
            res+=line.count("D")
        else:
            res+=int(line[-1]=="R")
    print(res)

 

B - Fix You

 

마지막 줄은 모든 D를 R로 바꾸고, 그 이전까지의 모든 줄은 맨 마지막 문자가 R이라면 D로 바꾸면 된다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
unsigned long long f = 1;
unsigned long long g = 2;
int t;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        f *= i;
        f %= 1000000007;
        if (i < t-1) {
            g *= 2;
            g %= 1000000007;
        }
    }
    cout << (f + 1000000007 - g) % 1000000007;
    return 0;
}

 

C - Cyclic Permutations

 

문제는 그래프에 대한 것이었지만 모든 permutations에 대한 그래프를 만들 수 없다고 판단하여 공식을 찾기로 했다.

 

from itertools import permutations
for X in range(1,12):
    n=X
    per = list(permutations([i for i in range(1,n+1)]))
    xnt=0
    li=[]
    for p in per:
        del li[:]
        for i in range(len(p)):
            largestj=-1
            smallestj=n+1
            for j in range(len(p)):
                if j<i and p[j]>p[i]:
                    largestj=max(j,largestj)
                if j>i and p[j]>p[i]:
                    smallestj=min(j,smallestj)
            if largestj!=-1:
                li.append(sorted([i+1,largestj+1]))
            if smallestj!=n+1:
                li.append(sorted([i+1,smallestj+1]))
        if(len(li)>=n):
            xnt+=1
    print(X,":",xnt)

 

파이썬으로 12까지의 정답을 출력하는 프로그램을 작성하였다.

 

3부터 9까지 순서대로 2 16 104 688 4976 40192 362624를 얻었고, a(n) = n! - pow(2, n-1) 라는 공식을 발견하였다.

 

처음엔 단순히 f - g를 출력하였다가 WA를 받았었다.