Codeforces Round #846 (Div. 2)

Contest link

 

A, B는 쉬우니 생략한다.

C는 출제자의 풀이에 오류가 있었다. 그래서 contest가 unrated 되었는데, 그걸 모르고 끝까지 열심히 풀어버렸다.

unrated와는 별개로 D, E, F는 마음에 들었다. 안일하게 증명 없이 셋팅한 것도 아니고, 나름대로 증명을 했다는데... 안쓰럽다.

퍼포먼스가 오렌지가 떴는데, 이걸 오렌지 퍼포먼스를 내는 데 성공했다고 봐야 할 지 모르겠다...

 

Bit Guessing Game

• 최대 질의 횟수가 30이라는 점을 통해 binary notation에서 한 자리씩 찾아내면 되겠다는 생각이 든다.
• 만약 $1\cdots 1_{(2)}-1$을 한다면, 그 사이 digit들이 무엇이던 상관없이 $\mathrm{cnt}$가 $1$ 감소한다.
• 그렇지 않다면, $\mathrm{cnt}$가 $0$ 이상 증가한다.
• 따라서 여태까지 빼준 값을 이용해서 $2^k$씩 뺀 형태를 잘 파악하면 문제를 풀 수 있다.

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

void get(int &v) { cin >> v; if (v == -1) exit(0); }

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t; while (t--)
    {
        int cnt0, cnt;
        get(cnt0);
        ll s = 0, ans = 0;
        rep(k,0,29) {
            cout << "- " << (1LL<<k)+ans-s << endl;
            s = (1LL<<k)+ans;
            get(cnt);
            if (cnt == cnt0-1) {
                ans |= 1LL<<k;
                cnt0--;
            }
            if (cnt == 0) break;
        }
        assert(cnt == 0);
        cout << "! " << ans << endl;
    }
}

 

Josuke and Complete Graph

Observation

1. $a_j-a_i\le r-l\Rightarrow \gcd(a_i,a_j)\le r-l$
2. $[l,r]$ 중에서 $k$의 배수가 두 개 이상 존재 $\iff \left \lfloor \frac r k \right \rfloor - \left \lfloor \frac {l-1} k \right \rfloor \ge 2\iff$ 가중치 $k$인 간선이 존재
3. $\forall k\le \left \lfloor \frac {r-l+1} 2 \right \rfloor$는 항상 가중치로서 존재함

2번 관찰을 바탕으로 $k$를 blocking하자.

$B=4\times 10^4$이라고 하자.

 

Case 1.  $k\le B$

$k\le 10^3$ 중 $\left \lfloor \frac r k \right \rfloor - \left \lfloor \frac {l-1} k \right \rfloor \ge 2$를 만족하는 $k$의 개수를 답에 더하면 된다.

 

Case 2.  $k>B \to \left \lfloor \frac {l-1} k \right \rfloor < 2.5\times 10^4$

$i=1\ldots 2.5\times 10^4-1$에 대해, $i=\left \lfloor \frac {l-1} k \right \rfloor$인 경우들을 고려하게 된다.

$i \le \frac {l-1} k < i+1 \Rightarrow \frac {l-1} {i+1} < k \le \frac {l-1} i$이므로,

$i$에 대해 가능한 $k$의 범위는 $\left [\max \left (B+1, \left \lfloor \frac {l-1} {i+1}\right \rfloor+1\right ),\left \lfloor \frac {l-1} i\right \rfloor \right ]$가 된다. 보다시피, $i=0$일 경우에는 예외처리가 필요해진다.

또한, $\left \lfloor \frac r k \right \rfloor\ge i+2 \Rightarrow \left \lfloor \frac r {i+2} \right \rfloor\ge k$를 만족해야 하므로 $\left [\max \left (B, \left \lfloor \frac {l-1} {i+1}\right \rfloor\right ) + 1, \min\left (\left \lfloor \frac r {i+2} \right \rfloor,\left \lfloor \frac {l-1} i\right \rfloor \right ) \right ]$가 최종 범위이다.

따라서 $\max \left (0, \min\left (\left \lfloor \frac r {i+2} \right \rfloor,\left \lfloor \frac {l-1} i\right \rfloor \right ) - \max \left (B, \left \lfloor \frac {l-1} {i+1}\right \rfloor\right ) \right )$를 답에 더하면 된다.

 

$i=0$일 경우, $l\le k\le r$이므로, $2k\le r$이면 된다. 따라서 $\max (0, \lfloor r / 2 \rfloor - \max(B,l - 1))$를 답에 더하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const ll B1 = 4e4, B2 = 2.5e4;

int main() {
    int t; scanf("%d", &t); while (t--)
    {
        ll l, r, ans=0;
        scanf("%lld %lld", &l, &r);
        
        // Case 1. k <= B1
        rep(k,1,B1) if (r/k - (l-1)/k >= 2) ans++;
        
        // Case 2. k > B1 -> (l-1)/k < B2
        ans += max(0LL,r/2-max(B1,l-1)); // i = 0
        
        rep(i,1,B2-1) { // i > 0
            ans += max(0LL,min((l-1)/i,r/(i+2)) - max(B1,(l-1)/(i+1)));
        }
        
        printf("%lld\n", ans);
    }
}

 

Three Chairs