2020/11/02 2:17 F問題をSNSのヒントを見て通したため、追記しました。
はじめに
A,B,C,D,Eの5完でした。
一先ず5問は解けたので満足です。
算数ができないのでC問題で死んでました。
A – Heavy Rotation
白→黒→白→….
と長さ2の周期を繰り返すため、Nの偶奇によって白か黒かが判別できます。
問題文がちょっとややこしいので、偶奇のどっちが白か黒になるかがややこしいですが、Sample Inputを見て決めましょう。
入力例1: 2 → White
なので偶数が白だと分かります。
あと、出力の文字が少し長いので手打ちせずコピペしたほうが良いです。(タイポでWAはやる気がなくなります。)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
if(N%2==1) cout<<"Black"<<endl;
else cout<<"White"<<endl;
}
B – Trapezoid Sum
愚直にやると最大10^11の計算が発生するためTLEとなります。
Ai以上 Bi以下の整数すべてを 1 個ずつ、合計 Bi−Ai+1 個の整数を書きます。
上の記載は言い換えると、
初項Ai、末項Bi、公差1の等差数列を書く
と言い換えられます。
書いた文字の和を求めるため、それぞれの等差数列の和を和の公式で求めて足し合わせればOKです。
等差数列の和の公式は幾つかありますが、初項と末項が分かっている場合、
(初項+末項)*項数/2
が一番素直だと思います。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
long long ans=0;
for(int i=0;i<N;i++){
long long A,B;
cin>>A>>B;
ans+=(A+B)*(B-A+1)/2;
}
cout<<ans<<endl;
}
C – Collinearity
大人になったら3点の直線の式なんて使わない！！
と思いながら必死に調べてました。
何回か実装に事故ったのでDを解いてから戻ってきたのですが…。算数の弱さが露見しましたね…。
https://qiita.com/tydesign/items/ab8a5ae52eb9c50ad26a
この記事を参考にしました。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
long long x[N];
int y[N];
for(int i=0;i<N;i++){
cin>>x[i]>>y[i];
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
if(i==j) break;
if(i==k) break;
if(j==k) break;
int dx1=x[j]-x[i];
int dy1=y[j]-y[i];
int dx2=x[k]-x[i];
int dy2=y[k]-y[i];
if(dx2*dy1==dx1*dy2){
cout<<"Yes"<<endl;
return 0;
}
}
}
}
cout<<"No"<<endl;
return 0;
}
この式が何かって話ですが、恐らく
dx1/dy1=dy2/dx2
を式変形したもので、傾きが一致しているかどうかを求めているっぽいですね。
かなり賢い式です！
D – Hachi
入力された数字の各桁を並び替えて8の倍数が作れるかを求める問題。
8の倍数の性質として、
下3桁が8の倍数ならその数は8の倍数
というものがあります。
これは1000が8の倍数のため、4桁以上は必ず1000で割り切れる=必ず8で割り切れるため、考えなくてもよくなるからです。
実装としては、入力された数字を3つ取り出して並び替え、8の倍数が作れるかを判定すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
cin>>S;
int c[10]={0};
for(int i=0;i<S.size();i++){
c[S[i]-'0']++;
}
for(int i=8;i<1000;i+=8){
int c2[10]={0};
int n=i;
c2[n%10]++;
c2[n/10%10]++;
c2[n/10/10%10]++;
bool f=true;
for(int j=0;j<10;j++){
if(c2[j]>c[j]){
f=false;
}
}
if(f){
cout<<"Yes"<<endl;
return 0;
}
}
if(S=="8"){
cout<<"Yes"<<endl;
return 0;
}
for(int i=16;i<100;i+=8){
string tmp="";
tmp+=i%10+'0';
tmp+=i/10%10+'0';
if(S==tmp){
cout<<"Yes"<<endl;
return 0;
}
tmp="";
tmp+=i/10%10+'0';
tmp+=i%10+'0';
if(S==tmp){
cout<<"Yes"<<endl;
return 0;
}
}
cout<<"No"<<endl;
}
今回の実装として、
入力された数の各桁の数字を取り出し、0～9が何個あるかカウント
→1000未満の各8の倍数に対して、同じようにカウントする。
→2つのカウント結果から、8の倍数が作れるか判定。
としました。
なお、上記の実装では入力の桁数が2桁以下の場合の処理が上手くできなかったため、2桁以下の入力は特別に処理を書いています。(愚直解で求めています。)
E – Transformable Teacher
一直線上の点を結んだ場合の距離の最小
と考えると分かりやすいのですが、左端から愚直に右隣と結んでいく方法が最も良いです。
ただ、今回は身長が変えられる教師がいます。
これの扱いがやや面倒です。
今回、すべてのHに対して教師とペアと組んだ場合を計算し、それの最小を取るようにしました。
教師とペアと組んだ場合
冒頭に記載した通り、
一直線上の点を結んだ場合の距離の最小
となるため、入力値はあらかじめソートしておきます。
入力例2の場合、Hは
13 16 23 31 32 60 84
となります。ここで、各Hを教師とペアにした場合の、残りのペアを観察しています。
13と教師がペア → 16-23 31-32 60-84
16と教師がペア → 13-23 31-32 60-84
23と教師がペア → 13-16 31-32 60-84
31と教師がペア → 13-16 23-32 60-84
32と教師がペア → 13-16 23-31 60-84
60と教師がペア → 13-16 23-31 32-84
84と教師がペア → 13-16 23-31 32-60
ペアになった数字の周り以外は、そんなに変化がないことが分かるかと思います。
累積和何かを使って、左端からペアを組んだ場合、右端からペアを組んだ場合を事前計算し、
それを用いて何とかできそうですね。
一番差の小さい教師の変化はどれか
教師の高さWをソートすることで二部探索がつかえるようになります。
C++ならlower_bound辺りを使って上手いことすれば、最も差の小さい教師の変化が分かります。
2分探索ならO(logM)なので、各HごとにやってもO(NlogM)で問題ありません。
結果
こうなりました。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long N,M;
cin>>N>>M;
long long H[N],W[M];
for(int i=0;i<N;i++){
cin>>H[i];
}
for(int i=0;i<M;i++){
cin>>W[i];
}
if(N==1){
long long ans=LLONG_MAX;
for(int i=0;i<M;i++){
ans=min(ans,abs(W[i]-H[0]));
}
cout<<ans<<endl;
return 0;
}
sort(H,H+N);
sort(W,W+M);
long long wa1[N];
long long wa2[N];
wa1[0]=H[1]-H[0];
wa1[1]=H[1]-H[0];
wa1[N-1]=0;
for(int i=2;i<N-1;i+=2){
wa1[i]=H[i+1]-H[i]+wa1[i-1];
wa1[i+1]=H[i+1]-H[i]+wa1[i-1];
}
wa2[N-1]=H[N-1]-H[N-2];
wa2[N-2]=H[N-1]-H[N-2];
wa2[0]=0;
for(int i=N-3;i>0;i-=2){
wa2[i]=H[i]-H[i-1]+wa2[i+1];
wa2[i-1]=H[i]-H[i-1]+wa2[i+1];
}
/*for(int i=0;i<N;i++){
cout<<wa1[i]<<","<<wa2[i]<<endl;
}*/
long long ans=LLONG_MAX;
for(int i=0;i<N;i++){
auto W1=lower_bound(W,W+M,H[i]);
auto W2=W1-W;
int idx=W2;
if(W2!=0){
int W3=W2-1;
if(abs(H[i]-W[W3])<abs(H[i]-W[W2])){
idx=W3;
}
}
//cout<<H[i]<<","<<W[idx]<<endl;
long long nn=abs(H[i]-W[idx]);
if(i==0) nn+=wa2[1];
else if(i==N-1) nn+=wa1[N-2];
else if(i%2==0){
nn+=wa1[i-1]+wa2[i+1];
}
else {
nn+=H[i+1]-H[i-1];
if(i!=1) nn+=wa1[i-2];
if(i!=N-2) nn+=wa2[i+2];
}
//cout<<nn<<endl;
ans=min(ans,nn);
}
cout<<ans<<endl;
}
添え字と変数が入り乱れててよく分かりません。
私の実装ではN=1の時に上手く動かなかった(2WAした)ため、N=1は愚直解で求めています。
コードとしては説明に書いた通りです。
入力値をソートする
→左端と右端からの累積を求める
→各Hについて、教師とペアを組んだ際の最小を求める
→Hと教師の差の最小は2分探索を使う
→Hの位置ごとに場合分けして、累積の結果を使いながら最小を計算する
F – Silver Woods
SNSで以下のような発言を見かけました。
円を大きくするということは、障害物を大きくすることと同じ。 障害物を大きくして、上の壁と下の壁が繋がれば、その時の大きさが答え
賢すぎる…。この方法で実装しました。
障害物には、上の壁、下の壁、N本の釘があります。これらN+2個の互いの距離を計算、それをソートし小さい順に並べました。
続いてN+2を頂点に持つUnionFindを作成。
あとは、距離の小さい順にUnionFindの辺を張っていき、上の壁と下の壁が同じグラフに属したタイミングで、その時に張った辺の距離の長さを答えとしました。
#include<bits/stdc++.h>
using namespace std;
struct dsu {
public:
dsu() : _n(0) {}
dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int main(){
int N;
cin>>N;
int x[N],y[N];
for(int i=0;i<N;i++){
cin>>x[i]>>y[i];
}
int n=(N+2)*(N+2);
pair<int,pair<int,int>> dis[n];
for(int i=0;i<N+2;i++){
for(int j=0;j<N+2;j++){
int idx=j+i*(N+2);
if(i==j){
dis[idx]=make_pair(INT_MAX,make_pair(i,j));
}
else{
int x1,y1,x2,y2;
if(i==N){
if(j==N+1) x1=0;
else x1=x[j];
y1=-100;
}
else if(i==N+1){
if(j==N) x1=0;
else x1=x[j];
y1=100;
}
else{
x1=x[i];
y1=y[i];
}
if(j==N){
if(i==N+1) x2=0;
else x2=x[i];
y2=-100;
}
else if(j==N+1){
if(i==N) x2=0;
else x2=x[i];
y2=100;
}
else{
x2=x[j];
y2=y[j];
}
//cout<<i<<","<<j<<","<<x1<<","<<y1<<","<<x2<<","<<y2<<endl;
int di=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
dis[idx]=make_pair(di,make_pair(i,j));
}
}
}
sort(dis,dis+n);
dsu ds(N+2);
int ans=0;
for(int i=0;i<n;i++){
ans=dis[i].first;
ds.merge(dis[i].second.first,dis[i].second.second);
if(ds.same(N,N+1)){
break;
}
}
printf("%.10f\n",sqrt(ans)/2);
}
UnionFindはatcoderのライブラリからコピペしました。(こっちではdsuという名前です。)
幾何のややこしい問題かと思えばグラフ問題に帰着できる面白い問題でした。
この発想ができる人、ほんとうにすごいと思います。
おわりに
パフォーマンス1287で、レートは5下がって1329となりました。
E問題、かなり難しいと思うのですがあれが解けて水色ギリギリは中々厳しいですね…。
Atcoderのレベル、明らかに高くなっている気がします。
水色の求められているレベルがすごくしんどいです…。
コメント