AtCoder Regular Contest 091

This past March I have been busy with graduation matters, defense, various forms, hospitals, visas, etc. After all this is over, this issue of AtCoder is finally completed. Tough face^-^

If there is no need to say anything about C and D, then there are only two questions in total. . .

Update: [2018-06-17] It has been delayed until now. . .

Title link

C - Flip, Flip, and Flip…

The meaning of the question is that $n*m$ grids are given, and then each grid must be flipped, and the eight surrounding grids must also be flipped. Ask how many squares are tailed in the end.

ll n, m;
void solve()
{
	cin >> n >> m;
	ll ans = n*m;
	int f = 0;
	if (m >= 2)
	{
		f++;
		ans -= 2 * n;
	}
	if (n >= 2)
	{
		f++;
		ans -= 2 * m;
	}
	if(f==2)ans += 4;
	cout << ans << endl;
}

D Remainder Reminder

Find out how many pairs of $(a,b)$ there are in no more than $n$ such that $a%b >= k$

Enum $b$.

ll n, k;
void solve()
{
	slla(n), slla(k);
	ll ans = 0;
	repp(x, k + 1, n)
	{
		ll f = n / x;
		ll num = x - k;
		ans += num*f;
		ll sur = n%x + 1;
		ans += max(sur - k, 0LL);
	}
	if (!k)ans = n*n;
	cout << ans << endl;
}

E LISDL

gives $n，a，b$. Construct a sequence of length $n$, the elements are $1$ to $n$. Let the longest increasing subsequence length be a, and the longest decreasing subsequence length be $b$.

This question is more interesting. . . You can first satisfy the longest increasing subsequence as $a$, and then construct the longest decreasing subsequence in segments. At this time, you can find out what the conditions are.

ll n,a,b;
void solve()
{
    slla(n),slla(a),slla(b);
    if(a+b-1>n || a*b<n)
    {
        cout<<-1<<endl;
        return;
    }
    while(n>0)
    {
        int x = min(a,n-b+1);
 
        for(int i = n-x+1;i<=n;i++)
        {
            cout<<i<<" ";
        }
        n-=x;
        b--;
    }
}

F - Strange Nim

There are $n$ piles of stones, the number of stones in each pile is $A_i$, and each pile of stones has a parameter $k_i$. Existing a and b, perform the following operations respectively:

Select a pile of stones. If there are currently $x$ stones in the pile, remove $[1, floor(x/k)]$.

Those who cannot perform the operation will lose. Both sides are the best choices. Ask about winning or losing.

sg looks for patterns. . .

If $n$ divides $k$, then sg(n,k)=n/k

It is found that g(1,k), g(2,k), g(3,k)…. Remove g(k,k) g(2*k,k), g(3*k,k)… from g(n,k) and there is no change in the sequence.

If $n$ does not divide $k$, then assuming n=k*x+b, there is sg(x*k+b,k) = sg((x-1)*k+(b-1),k).

It can be found that it was originally x*k+b, and now it will become x*k+b-(x+1). Optimization is needed here to calculate how many x’s are constant. A total of ceil(b/(x+1)) times must be subtracted, so it is (b+x)/(x+1).

int SG(int a,int k)
{
    int x=a/k,b=a%k;
    if(!b) return x;
    int t=(b+x)/(x+1);
    return SG(a-t*(x+1),k);
}

int n;
 
int cal(int x,int y)
{
    if(x%y==0)
    {
        return x/y;
    } else{
        return cal(x - max(x%y/(x/y+1),1)*(x/y+1),y);
    }
}
 
void solve()
{
    sa(n);
    int ans = 0;
    repp(i,1,n)
    {
        int x,y;
        sa(x),sa(y);
        ans ^= cal(x,y);
    }
    if(ans)
    {
        puts("Takahashi");
    }
    else
    {
        puts("Aoki");
    }
}