codeforces R698 D2

solved: 2 out of 6

 

A,B 두 문제를 40분이 안되는 시간안에 삽질 없이 해결하여(WA없이) 오늘 드디어 색을 바꾸는구나 했는데 C,D가 수학이라 좌절한 라운드입니다.

C번은 오늘 자고 일어나서 다시 에디토리얼을 읽는데도 도통 이해가 가지 않아 우선 풀이를 보류합니다.

 

A. Nezzar and Colorful Balls

N이 정말 너무너무 작아서 $O\left ( N^2 \right )$풀이로 AC를 받았습니다.

길이 N짜리 배열을 돌면서 색을 그냥 칠해주면 됩니다.

	int n;read(n);
        int A[n];
        rep(i, n) {
            int tmp;read(tmp);
            A[i]=tmp;
        }
        int painted[n];
        fill(painted, painted+n, -1);
        int color = 1;
        rep(i, n) {
            int pre = -1;
            rep(j, n) {
                if (painted[j]==-1) {
                    if (pre==-1 || pre<A[j])  {
                        painted[j]=color;
                        pre=A[j];
                    }
                }
            }
            color++;
        }
        int ans = 1;
        rep(i, n)
            if (painted[i]>ans) ans++;

 

B. Nezzar and Lucky Number

이번에도 N이 1만으로 $O\left ( N^2 \right )$풀이가 가능합니다.

주어진 정수에서 d를 계속 빼주면서 이때의 결과값이 lucky number인지 확인해주면 쉽게 해결 할 수 있습니다.

 

	 bool f = false;
         for (int j = tmp; j>0; j-=d) {
             string s = to_string(j);
             if (hasD(s, dd)) {
                 cout << "yes" << endl;
                 f=true;
                 break;
             }
         }
         if (!f) cout << "no" << endl;