ABC199 参戦記録 p.44
itsukiです。
AtCoder Beginner Contest 199 に参戦した様子です。解説記事ではありません。
結果は A, B, C の 3完でした。ついにレート色が茶色になりました。
回答時間合計：71分08秒
パフォーマンス：714
考察の流れ
A - Square Inequality
最近 少し考えさせる A問題が多かった？ので、本当にそのまま書けばいいだろうか とちょっと戸惑う
素直にそのまま書く
#include <stdio.h>
#define Yes() printf("Yes\n")
#define No() printf("No\n")
int main(){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if( a*a + b*b < c*c ){ Yes(); }
else{ No(); }
return 0;
}B - Intersection
ぱっと解法が思いつかなくて焦る
適当な配列 tmp[] を用意して、A_i ～ B_i について各要素をインクリメントする
( A_1, B_1 ) ～ ( A_N, B_N ) まで処理した結果、tmp[i] == N となる要素の個数をカウントする
下図は、入力例3 ( N=3 ) の様子
#include <stdio.h>
int main(){
int n,a[105]={0},b[105]={0},tmp[1005]={0};
scanf("%d",&n);
for(int i=0; i<n; i++){ scanf("%d",&a[i]); }
for(int i=0; i<n; i++){ scanf("%d",&b[i]); }
int cnt=0;
for(int i=0; i<n; i++){
for(int j=a[i]; j<=b[i]; j++){
tmp[j]++;
}
}
for(int i=0; i<1005; i++){
if( tmp[i]==n ){ cnt++; }
}
printf("%d\n",cnt);
return 0;
}コンテスト後：
今回は制約が N <= 100, A_i <= B_i <= 1000 だったので この解き方で良かったが、もし「2重ループにすると計算が間に合わない」とか「tmp[]配列の要素数が大きくなりすぎる」ような制約だったらダメだった
もし N <= 10^5, A_i <= B_i <= 10^9 という制約であっても、A_i の最大値 ～ B_i の最小値 を調べておけば間に合う（はず）
#include <stdio.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
int main(){
int i,n,a,b,maxa=0,minb=1001;
scanf("%d",&n);
for(i=0; i<n; i++){ scanf("%d",&a); maxa = MAX(maxa,a); }
for(i=0; i<n; i++){ scanf("%d",&b); minb = MIN(minb,b); }
printf("%d\n",MAX(0,minb-maxa+1));
return 0;
}C - IPFL
以前、似たような問題を見たような気がする（ABC158-Dだった）
各クエリをそのまま処理すると、例えばすべてのクエリが T_i = 2 だったら間に合わないので、T_i = 2 の処理をどうにかして簡単にしたい
最初、下図のように 文字列S をふたつ並べて、T_i = 2 のクエリが来たら上下切り替える…ようなことを考えたが…
それなら 前半部分 と 後半部分 とで別の配列にして、入れ替えた振りだけしながらアクセスする先を変えれば良さそう
前後逆転モード中かどうかの変数（例えば mode）を用意し、T_i = 2 の処理が来たら 0, 1 を切り替えることにする
mode の状態により、T_i = 1 の処理でアクセスする先を変える
最後、mode==0 なら 前後 の順に、mode==1 なら 後前 の順に出力する
#include <stdio.h>
#include <string.h>
void char_swap(char*a, char*b){ char tmp=(*a); (*a)=(*b); (*b)=tmp;}
int main(){
int n,q,mode=0;
char s[400005]={0}, s1[200005]={0}, s2[200005]={0};
char s[40]={0}, s1[20]={0}, s2[20]={0};
scanf("%d%s%d",&n,s,&q);
for(int i=0; i<n; i++){ s1[i]=s[i]; }
for(int i=n; i<2*n; i++){ s2[i-n]=s[i]; }
while(q){
int t,a,b;
scanf("%d%d%d",&t,&a,&b); a--; b--;
if( t==1 ){
// 後半分の話
if( a>=n ){
if( !mode ){ char_swap( &s2[a-n], &s2[b-n] ); }
else { char_swap( &s1[a-n], &s1[b-n] ); }
// 前半分の話
}else if( b<n ){
if( !mode ){ char_swap( &s1[a], &s1[b] ); }
else { char_swap( &s2[a], &s2[b] ); }
// 前後にまたがる話
}else{
if( !mode ){ char_swap( &s1[a], &s2[b-n] ); }
else { char_swap( &s1[b-n], &s2[a] ); }
}
}
else{ mode ^= 1; } // 前後逆転モードを切り替える
q--;
}
if( !mode ){ printf("%s%s\n",s1,s2); }
else{ printf("%s%s\n",s2,s1); }
return 0;
}他の方々の回答を見たら、もっとスマートできれいだった！
まとめ
・今回の B問題 のように、難しく考えすぎてしまう癖を直したい
・考察するときに図を書くこと！！横着しない
・ペナなく解けたのは良かった
・諦めないで解ききれる精神状態のとき、自分は良い結果を出せるらしい
先にも書きましたが、ついにレート色が茶色になりました！数学嫌いですが、プログラミングが好きなので諦めずに続けてて良かったです。しばらくは茶色と灰色を行き来すると思いますが、競プロというネトゲをこれからも楽しみたいと思います。
引き続き、のんびり精進します。
この記事が気に入ったらサポートをしてみませんか？