yukicoder contest 263 Review

result

スクリーンショット 2020-08-29 12.03.11.png

Impressions

I died like last time. It's a problem that should be solved when I always die, and I feel like I've forgotten the corner case or bugged it in the implementation **. ** When will it be possible to calmly analyze the cause during the contest?

Problem A

A^2 -B^2 =N \leftrightarrow (A-B)(A+B)=N

Since the formula can be transformed as above and ** $ AB $ and $ A + B $ match even and odd , $ (AB, A + B) = $ (even, even), (odd, odd) It should be. Also, at this time, the former must be a multiple of 4 and the latter must be an odd number. Also, since $ A-B <A + B $, if $ N = 4,1 $ does not hold ( corner case! **), it will be as follows.

A.py


n=int(input())
if n%2==1:
    if n==1:
        print(-1)
    else:
        print(1)
elif n%4==0:
    if n==4:
        print(-1)
    else:
        print(1)
else:
    print(-1)

Problem B

I've solved a lot of DP problems in the last few days, so I was able to solve them pretty quickly. However, it is a reflection that I made a mistake in the ** index and became WA **.

For this problem, you can see that you should look at the sweets ** in order **. However, ** cannot be done by the greedy algorithm **, so the following DP is set.

$ dp [i] [j]: = $ (Maximum happiness when selecting odd (or even) sweets when taking $ i $ th sweets)

However, when $ j = 0 $, the number is odd, and when $ j = 1 $, the number is odd.

At this time, the transition is not difficult and is as follows.

(1) Update $ dp [i + 1] [0] $

If you do not choose $ a [i + 1] $, $ dp [i] [0] $ When choosing $ a [i + 1] $, $ dp [i] [1] + a [i + 1] $

(2) Update $ dp [i + 1] [0] $

If you do not choose $ a [i + 1] $, $ dp [i] [1] $ When choosing $ a [i + 1] $, $ dp [i] [0]-a [i + 1] $

B.py


n,m=map(int,input().split())
a=[sum(list(map(int,input().split()))) for i in range(n)]
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
for i in range(n-1):
    #Eat or not
    dp[i+1][0]=max(dp[i][0],dp[i][1]+a[i+1])
    dp[i+1][1]=max(dp[i][1],dp[i][0]-a[i+1])
print(max(dp[n-1]))

C problem

I made the blunder of thinking about only one of the equations that came out first, and then I made the right policy, but I felt that ** implementation was troublesome **, and as a result ** messy implementation ** I couldn't get one case of WA.

I was so impatient at the beginning that I couldn't put together a policy, so I want to be ** calm down ** there. These days, my mentality is so terrible that I can't do it at all ...

First, if you put the problem into a mathematical formula, it will be $ A \ times B = X-C, A \ times C = Y-B $. When this is transformed, it becomes $ (A-1) (B-C) = X-Y, (A + 1) (B + C) = X + Y $. Also, to make the implementation easier, let's assume that $ X \ geqq Y $ holds, and if it doesn't hold, swap.

Focusing on $ (A-1) (BC) = XY $, $ A-1 $ is a divisor of $ XY $, so ** $ O (\ sqrt {X}) $ is $ A $. Candidates can be enumerated **. Also, when $ A $ is fixed, $ B-C = \ frac {X-Y} {A-1}, B + C = \ frac {X + Y} {A + 1} $ holds. Therefore, if you set $ v = \ frac {XY} {A-1}, w = \ frac {X + Y} {A + 1} $, then $ B = \ frac {v + w} {2}, C = \ frac {wv} {2} $ holds. At this time, $ B, C $ may not be an integer, but cast it to an integer type and find $ B, C $. For this $ B, C $, check if $ (A-1) (BC) = XY, (A + 1) (B + C) = X + Y $ holds, and count the number. ..

Also, since the discussion above assumes $ X \ neq Y $, it is necessary to consider the case of ** $ X = Y $ separately **. When $ X = Y $, from $ (A-1) (B-C) = 0 \ leftrightarrow A = 1 \ or \ B = C $, you can divide the cases as follows.

(1) When $ A = 1 $ From $ (A + 1) (B + C) = X + Y \ leftrightarrow B + C = X $, $ (B, C) = (1, X-1), (2, X-2),…, There are $ X-1 $ streets of (X-1,1) $.

(2) When $ B = C $ From $ (A + 1) (B + C) = X + Y \ leftrightarrow (A + 1) B = X $, $ A + 1 $ is a divisor of $ X $ and can be used in the previous discussion. .. However, when ** $ \ frac {X} {A + 1} $ becomes 1 or 2, it is necessary to carefully separate the cases **, but it was processed separately as a ** corner case **. ..

C.cc


//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair


ll check_divisors(ll x,ll y){
    ll ret=0;
    ll n=x-y;
    vector<ll> divisors;//Array to store divisors
    FOR(i,1,sqrt(n)){
        if(n%i==0){
            divisors.PB(i);
            if(i!=n/i){
                divisors.PB(n/i);
            }
        }
    }
    //a-Candidate for 1
    FORA(i,divisors){
        ll a,b,c;a=i+1;
        ll v,w;v=n/(a-1);w=(x+y)/(a+1);
        b=(v+w)/2;c=(w-v)/2;
        if(b>0 and c>0 and (a-1)*(b-c)==(x-y) and (a+1)*(b+c)==(x+y)){
            ret++;        
        }
    }
    return ret;
}

ll check_divisors2(ll x,ll y){
    ll ret=x-1;
    FOR(i,3,sqrt(x)){
        if(x%i==0){
            if(i!=ll(x/i)){
                ret+=2;
            }else{
                ret++;
            }
        }
    }
    if(x%2==0){
        if(2!=ll(x/2) and x!=2){
            ret++;
        }
    }
    if(x!=1 and x!=2)ret++;
    return ret;
}

signed main(){
    //Code for speeding up input
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll s;cin>>s;
    REP(i,s){
        ll x,y;cin>>x>>y;
        if(x<y)swap(x,y);
        if(x==y){
            cout<<check_divisors2(x,y)<<endl;
        }else{
            cout<<check_divisors(x,y)<<endl;
        }
    }
}

After D problem

I will not solve this time.

Recommended Posts

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
yukicoder contest 261 Participation record
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
yukicoder contest 278 Participation record
yukicoder contest 262 entry record
AtCoder Beginner Contest 165 Review