正月もABC埋めを進めていきます。
A – Pair
ちょっと難しめ、計算でも奇数偶数個の個数は求められそうだけど、WAが怖いのでfor文で愚直にカウントしました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int K;
cin>>K;
int g=0,k=0;
for(int i=1;i<=K;i++){
if(i%2==0) g++;
else k++;
}
cout<<g*k<<endl;
}
B – Ruined Square
B – Ruined Square (atcoder.jp)
ちょっと難しめ。行列とかベクトルに詳しいと簡単に解けそうです。
初めの二点は、下から上、右から左、上から下、左から右の4パターンです。
この4パターンのどれかによって、3点目4点目の位置関係が変わってきます。この辺りを丁寧に場合分けします。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int dx=abs(x1-x2);
int dy=abs(y1-y2);
int pat=0;
if(x1<=x2&&y1<=y2) pat=0;
if(x1>=x2&&y1<=y2) pat=1;
if(x1>=x2&&y1>=y2) pat=2;
if(x1<=x2&&y1>=y2) pat=3;
int c=2;
while(c-->0){
swap(dx,dy);
if(pat==0) x2-=dx,y2+=dy;
if(pat==1) x2-=dx,y2-=dy;
if(pat==2) x2+=dx,y2-=dy;
if(pat==3) x2+=dx,y2+=dy;
cout<<x2<<" "<<y2<<(c==0?"\n":" ");
pat=(pat+1)%4;
}
}
計算式は紙に、三平方の定理の証明で使われる、三角形4つと四角形1つの図を書いて調べました。
C – Triangular Relationship
C – Triangular Relationship (atcoder.jp)
a+bがKの倍数は、a+b=0 mod Kと言い換えられます。
a+c=b+c mod Kから、a=b mod Kと言えます。
上記2つから、a,bで考えられるパターンは、
a=b=0 mod K
a=b=K/2 mod K
のどちらかであると言えます。
これらは、a,cやb,cにも言えるため
N mod Kが0となるような数の個数の3乗 N mod KがK/2となるような数の個数の3乗 (a,b,cも整数のため、K/2が割り切れないなら0)
の2つを足し合わせた数が答えとなります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
long long N,K;
cin>>N>>K;
long long ans=0;
//K/2+K/2
if(K%2==0){
long long n=N-K/2;
if(n>=0){
long long c=n/K+1;
ans+=c*c*c;
}
}
//0+0
long long c2=N/K;
ans+=c2*c2*c2;
cout<<ans<<endl;
}
D – All Your Paths are Different Lengths
D – All Your Paths are Different Lengths (atcoder.jp)
制約から、log10^6が20くらいになるので、2進とか二分木とかで見ていきたい気持ちになります。
この気持ちは正解で、二進数を基準に考えると正解になります。
例えば13の場合、
1→2 0
1→2 1
2→3 0
2→3 2
3→4 0
3→4 4
と張り、0～7の8個を満たすグラフを作ります。
次に9～を作ることを考えると、1+8=9,2+8=10.1+2+8=11なので2->4に8を張ると9～11が一気にできそうです。
次に12を作ることを考えると、1+11=12なので1->4に11を張ると作れそう…と、次の数字をたくさん作れる位置に辺を張るということを、L-1のルートができるまで繰り返しました。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int L;
cin>>L;
vector<int> vi,vj,vk;
int keta=0;
while(pow(2,keta)<=L) keta++;
keta--;
for(int i=1;i<=keta;i++){
vi.push_back(i);
vj.push_back(i+1);
vk.push_back(0);
vi.push_back(i);
vj.push_back(i+1);
vk.push_back(pow(2,i-1));
}
int nx=pow(2,keta);
for(int i=keta;i>=1;i--){
int n=nx+pow(2,i-1)-1;
if(n<L){
vi.push_back(i);
vj.push_back(keta+1);
vk.push_back(nx);
nx=n+1;
}
}
cout<<keta+1<<" "<<vi.size()<<endl;
for(int i=0;i<(int)vi.size();i++){
cout<<vi[i]<<" "<<vj[i]<<" "<<vk[i]<<endl;
}
}
めちゃくちゃ難しいと思ったら700点問題だったのですね…。ABCで700とか怖い。
コメント