はじめに
A～Eを0WAで解いて384位でした。
青パフォ(1900)出たので、かなり満足です。
A – twiblr
入力例 1 の下に書いてある文章が分かりやすいです。
フォロー数は 2×200+100=500 まで増やせるので、あと 200 増やせます。
A=200,B=300なので、
2×A+100が最大で、そこからBを引く
だということが分かりますね。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int A,B;
cin>>A>>B;
int mx=2*A+100;
cout<<mx-B<<endl;
}
B – Almost GCD
Bにしては問題分が難しいです。
制約が弱いので愚直にGCD度を求めて、最大を取ればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
int A[N];
int cnt[1001]={0};
for(int i=0;i<N;i++){
cin>>A[i];
}
for(int i=2;i<=1000;i++){
for(int j=0;j<N;j++){
if(A[j]%i==0) cnt[i]++;
}
}
int mx=-1,mxi=-1;
for(int i=0;i<1001;i++){
if(mx<cnt[i]){
mx=cnt[i];
mxi=i;
}
}
cout<<mxi<<endl;
}
Aiのmaxが1000なので、1001以上はAiの値に限らずGCD度は0になります。
そのため1000までの範囲で問題ありません。
C – To 3
3で割れる数の特徴として、
各桁の和が3で割れること
というものがあります。
この問題はその特徴を使います。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
string S;
cin>>S;
long long cnt[3]={0};
long long sum=0;
for(int i=0;i<S.size();i++){
int a=S[i]-'0';
cnt[a%3]++;
sum+=a;
sum%=3;
}
if(sum==0){
cout<<"0"<<endl;
return 0;
}
if(sum==1){
if(cnt[1]>0&&S.size()>1){
cout<<"1"<<endl;
return 0;
}
if(cnt[2]>1&&S.size()>2){
cout<<"2"<<endl;
return 0;
}
}
if(sum==2){
if(cnt[2]>0&&S.size()>1){
cout<<"1"<<endl;
return 0;
}
if(cnt[1]>1&&S.size()>2){
cout<<"2"<<endl;
return 0;
}
}
cout<<"-1"<<endl;
}
mod 3同士の引き算の答えは以下のようになります。
mod 0 - mod 0 = mod 0 mod 0 - mod 1 = mod 2 mod 0 - mod 2 = mod 1 mod 1 - mod 0 = mod 1 mod 1 - mod 1 = mod 0 mod 1 - mod 2 = mod 2 mod 2 - mod 0 = mod 2 mod 2 - mod 1 = mod 1 mod 2 - mod 2 = mod 0
mod 1からは、mod 1を消すか、mod 2を2回消すことでmod 0にできます。
mod 2からは、mod 2を消すか、mod 1を2回消すことでmod 0にできます。
このパターンで消せるかどうかを見ました。
ただ、2桁以下の場合、消した後のmod 0が=0(何も数字が残らない)場合があります。
そういった場合は例外処理として除くようにしましょう。
D – Wandering
問題文のリストの各点を1セットと考えると、
iセット目の移動は、A1進み、A2進み、A3進み…Ai進むとなります。
この時、i-1セット終了時のx座標をsumとしたとき、
sum+A1
sum+A1+A2
sum+A1+A2+A3
sum+A1+A2+A3+….+AN
と遷移します。
つまり、sumにA1までの累積、A2までの累積、A3までの累積…ANまでの累積を足すことになります。
なので、1セット目から見ていくついでに、そのセットまでの累積の最大とそのセットまでの累積を更新していくことで、各セットのx座標の最大と、各セット終了後のx座標がO(1)で計算でき、全体の計算量をO(N)にすることができます。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
long long N;
cin>>N;
long long A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
long long ans=max(0ll,A[0]);
long long sumz=A[0];
long long sum=A[0];
long long sumx=A[0];
for(int i=1;i<N;i++){
long long a=sumx+sumz;
ans=max(a,ans);
sumx+=sum+A[i];
ans=max(sumx,ans);
sum+=A[i];
if(sum>sumz) sumz=sum;
}
cout<<ans<<endl;
}
ansがx座標の最大、sumがiセット目までの累積、sumzがiセット目までの累積の最大、sumxがiセット目までのx座標位置になります。
for内の変数aは、iセット目でのx座標の最大ですね。
変数名が分かりにくいと思いますが、競プロ以外でこんなことしちゃダメですよ！というか、競プロでもダメです。
早解きのために適当な変数で実装していますが、バグ等が出たときのデバッグやバグ取りが地獄になります。(今回はバグなしで実装できたため、問題なかったのですが…危険です)
E – Akari
競プロよくある問題ですね。
電球1個1個に対して愚直にシミュレーションせずに、4方向から全電球に対して一気に見ていくことでO(HW)で解くことができます。
具体的には、
- 左から右に見るを、全行に対して行う。
- 右から左に見るを、全行に対して行う。
- 上から下に見るを、全列に対して行う。
- 下から上に見るを、全列に対して行う。
の4つを見ていきます。光源があればフラグを1にし、ブロックがあるならフラグを0にするなどして、4方向に分けて光を伸ばしていきます。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
long long H,W,N,M;
cin>>H>>W>>N>>M;
long long data[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
data[i][j]=0;
}
}
for(int i=0;i<N;i++){
int A,B;
cin>>A>>B;
A--;
B--;
data[A][B]=1;
}
for(int i=0;i<M;i++){
int C,D;
cin>>C>>D;
C--;
D--;
data[C][D]=2;
}
int ans[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
ans[i][j]=0;
}
}
for(int i=0;i<H;i++){
int light=0;
for(int j=0;j<W;j++){
if(data[i][j]==1) light=1;
if(data[i][j]==2) light=0;
ans[i][j]=max(ans[i][j],light);
}
}
for(int i=0;i<H;i++){
int light=0;
for(int j=W-1;j>=0;j--){
if(data[i][j]==1) light=1;
if(data[i][j]==2) light=0;
ans[i][j]=max(ans[i][j],light);
}
}
for(int j=0;j<W;j++){
int light=0;
for(int i=0;i<H;i++){
if(data[i][j]==1) light=1;
if(data[i][j]==2) light=0;
ans[i][j]=max(ans[i][j],light);
}
}
for(int j=0;j<W;j++){
int light=0;
for(int i=H-1;i>=0;i--){
if(data[i][j]==1) light=1;
if(data[i][j]==2) light=0;
ans[i][j]=max(ans[i][j],light);
}
}
long long ct=0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
//cout<<ans[i][j];
ct+=ans[i][j];
}
//cout<<endl;
}
cout<<ct<<endl;
}
競プロで過去に見すぎた問題のため、他に制約や条件がないか無駄に探してしまいました。
典型っぽくない問題を典型と感じるのってこういうことなんでしょう。問題をたくさん解くことは、やっぱり重要ですね。
おわりに
コンテスト参加前の直前まで、エーペックスレジェンズのフレンド戦をやっていたため、参加するか迷ったのですが、結果として参加してよかったですね。
今のところ、やりたいことが少しづつ増えてきているため、時間をなんとか上手いこと使いたいです。
目覚まし掛けずに雑に寝ると、12時間寝ている癖を直したいです。
コメント