AtCoder Beginner Contest 182 by C
AtCoder Beginner Contest 182 について
C言語での回答
できたもの
A
B
C
できなかったもの
D以降
問題A
#include <stdio.h> int main(void){ int a,b; scanf("%d %d", &a,&b); printf("%d\n", (2*a+100)-b); return 0; }
方針
フォローの上限から今のフォローを引けばそれが答え。
問題B
#include <stdio.h> int main(void){ int n,i,j; int a; int count[1001]={0}; scanf("%d", &n); int maxnum = 0; for(i=0;i<n;i++){ scanf("%d", &a); for(j=2;j<=a;j++){ if(a%j==0){ count[j]++; } } if(a>maxnum){ maxnum = a; } } int max = 0; for(i=2;i<=maxnum;i++){ //printf("i:%d %d\n", i,count[i]); if(count[i]>max){ max = count[i]; j = i; } } printf("%d\n", j); return 0; }
方針
Nの数が100、Aの上限値が1000と小さいので全探索が利用できます。
Aiまでのすべてのiについて割り切れるかどうかをそれぞれカウントし、カウントが1番多いものが答え。
最大のものが複数ある場合にはどれを出力してもいいので最小の値、つまりmaxの時のiを使いました。
0で割らないようforの始まりは1以上にしましょう!!(本日2回目)
問題C
#include <stdio.h> #include <stdlib.h> int main(void){ int i; long long n; int s[20],mod[20]={0}; scanf("%lld", &n); int num; while(n>0){ s[num] = n%10; mod[s[num]%3]++; n /= 10; num++; } int sum = 0; for(i=0;i<num;i++){ sum += s[i]; } if(sum%3==0){ printf("0\n"); } else if(sum%3==2){ if(mod[2]>0&&num>1){ printf("1\n"); } else if(mod[1]>1&&num>2){ printf("2\n"); } else{ printf("-1\n"); } } else { if(mod[1]>0&&num>1){ printf("1\n"); } else if(mod[2]>1&&num>2){ printf("2\n"); } else{ printf("-1\n"); } } return 0; }
方針
ある数が3で割れるというのは、その数の桁をすべて足して得られる数が3で割りきれることと同じです。
まずはそれを用いて操作しなくても割り切れるかどうかをチェック。
1e18なのでint型では足りないためlong long型を使用します。
10で割ったあまりを随時受け取れば各桁の数字が得られます。
ちなみにここで得た各桁の数字を3で割ったあまりも保持しておき、下の場合分けを満たすか否かで用います。
それらの総和が元の数の全ての桁を足した数になります。
①総和を3で割ったあまりが0
何も消す必要がないので0を出力。
②総和を3で割ったあまりが1
あまりが1の数字を一つ消すか、あまりが2の数字を二つ消せば3で割り切れるようになります。
③総和を3で割ったあまりが2
あまりが2の数字を一つ消すか、あまりが1の数字を一つ消せば3で割り切れるようになります。
ただし、②と③において元々の数の桁数が消す数と同じであれば問題文の条件に反するのでNG。
以下は最初の入力を文字列で受け取るパターン。
後半の処理は同じです。
数値として足すためにintへ変換する事を忘れずに。
#include <stdio.h> #include <string.h> int main(void){ int i; char s[20]; int mod[5]={0}; scanf("%s", s); int size = strlen(s); int sum = 0; for(i=0;i<size;i++){ sum += (int)s[i]; mod[s[i]%3]++; } if(sum%3==0){ printf("0\n"); } else if(sum%3==2){ if(mod[2]>0&&size>1){ printf("1\n"); } else if(mod[1]>1&&size>2){ printf("2\n"); } else{ printf("-1\n"); } } else{ if(mod[1]>0&&size>1){ printf("1\n"); } else if(mod[2]>1&&size>2){ printf("2\n"); } else{ printf("-1\n"); } } return 0; }
問題D
ナイーブなやりかたは思いついたけどまあ当然TLEだな......というところ
#include <stdio.h> long long max(long long a, long long b){ return a > b ? a : b; } int main(void){ int n,i,j; long long a[200001]; scanf("%d", &n); for(i=0;i<n;i++){ scanf("%lld", &a[i]); } long long p = 0; //初めの座標を0とした時の座標 long long q = 0; //動作i中における最大の座標 long long r = 0; //全体での最大の座標 long long x = 0; //一つ移動したあとの座標 for(i=0;i<n;i++){ p += a[i]; q = max(q,p); r = max(r,x+q); x += p; } printf("%lld\n",r); return 0; }
方針
a1からaiまで足す動作を動作iとし、その中で値を随時更新。
やっぱり型には注意。
問題E
まだ