[PYTHON] yukicoder contest 263 Review
result
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
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