ABC196 参戦記録 p.42
itsukiです。
AtCoder Beginner Contest 196 に参戦した様子です。解説記事ではありません。
結果は A, B, C の 3完でした。
回答時間合計：82分10秒（3ペナ15分を含む）
パフォーマンス：503
考察の流れ
A - Difference Max
最近よく見る(?)、それぞれに範囲が与えられた x, y を使って計算する問題
ABC178-B が頭をよぎったので、各範囲の境界を丁寧に調べる
プラスマイナスに関わらず、( x 最大値 ) - ( y 最小値 ) で良さそう
#include <stdio.h>
int main(){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",b-c);
return 0;
}B - Round Down
X は小数の可能性もあるので、文字列で扱う
まず値全体を取得してから、小数点の手前まで for 文で一文字ずつ表示する
提出したら RE になって叫んだ
文字列の長さを見誤っていた
#include <stdio.h>
#include <string.h>
int main(){
char s[100005]={0}; // 雑に増量
scanf("%s",s);
for(int i=0; i<strlen(s); i++){
if( s[i]=='.' ){ break; }
printf("%c",s[i]);
}
printf("\n");
return 0;
}C - Doubled
1 <= N < 10^12 という制約からすると、O(√N) のような気がする
まず、条件を満たす x の最小値と最大値を考えてみた
最小値：11（前半部分=1, 後半部分=1）
最大値：999999999999（前半部分=999999, 後半部分=999999）
つまり、11～999999 が前半部分に出現する可能性がある
N が一桁の場合は 前半後半に分けられないので、先に省いておく（パターン①）
入力例2 ( = 1333 ) のように N が偶数、かつ 前半部分=13 と 後半部分=33 のように「後半部分の方が大きい値」の場合、前半部分の値がそのまま答えになる（パターン②）
「前半部分と後半部分の値が等しい」場合も同上（パターン②）
例えば 9876 のように N が偶数、かつ 前半部分=98 と 後半部分=76 のように「後半部分の方が小さい値」の場合、「前半部分の値」を答えにしてしまうと x = 9898 となって Ｎを超えてしまうので、「前半部分の値 - 1」が答えになる（パターン③）
N が奇数の場合、一桁削って 9 で埋めた値を用意してパターン②とする（例えば N=1234567 なら 999999 で考える）（パターン④）
// コンテスト後に綺麗に書き直した
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
char s[20]={0},t[20]={0},u[20]={0};
scanf("%s",s);
int i,n=strlen(s);
if( n==1 ){ printf("0\n"); return 0; }
if( n%2 ){
for(i=0; i<n/2; i++){ t[i]='9'; }
for(i=0; i<n/2; i++){ u[i]='9'; }
}else{
for(i=0; i<n/2; i++){ t[i]=s[i]; }
for(i=0; i<n/2; i++){ u[i]=s[i+(n+1)/2]; }
}
int tnum = atoi(t), unum = atoi(u);
if( tnum > unum ){ tnum--; }
printf("%d\n",tnum);
return 0;
}WA1：前半部分と後半部分を比較して、小さい方の値を答えとしていた
WA2：前半部分と後半部分を比較して、後半部分がゼロ始まりだった場合(?)、後半部分の値を 9 で埋めた値に変換していた(?)
まとめ
・サンプルが通っただけで焦って提出しない！
・C は全探索も可能だったので、無理に場合分けせず全探索も試してみるべきだった
・C で 2WA した後も諦めなかったのはえらい
引き続き、のんびり精進します。
この記事が気に入ったらサポートをしてみませんか？