AtCoder Beginner Contest 069 by C
AtCoder Beginner Contest 069 について
C言語での回答
できたもの
A
B
C
D
初めて全回答できました！
問題A
#include <stdio.h> int main(void){ int n,m; scanf("%d %d",&n,&m); printf("%d\n", (n-1)*(m-1)); return 0; }
方針
生まれる街区は線の数-1なので、縦横の数からそれぞれ1を引いてかければ答えです。
問題B
#include <stdio.h> #include <string.h> int main(void){ char s[101]; scanf("%s", s); int size = strlen(s); printf("%c", s[0]); printf("%d", size-2); printf("%c", s[size-1]); return 0; }
方針
2文字目からn-1文字目までの文字数が間に表示される数字の数なので、strlenで文字列の長さを取得し、2を引いた数になります。
後は前後に先頭の文字と最後尾の文字を表示すれば解。
問題C
#include <stdio.h> int main(void){ int n,i; int a[100001]; scanf("%d", &n); int count4 = 0,count2 = 0; for(i=0;i<n;i++){ scanf("%d", &a[i]); if(a[i]%4==0){ count4++; } if(a[i]%2==0){ count2++; } } count2 -= count4; if(count4>=n/2){ printf("Yes\n"); } else{ if(n-(count4*2)==count2){ printf("Yes\n"); } else{ printf("No\n"); } } return 0; }
方針
4の倍数であれば、隣の数がなんであれ「aiとai+1の積は4の倍数である」という条件を満たせます。
4の倍数を●として条件を満たせる配置の一つとして以下が挙げられます。
奇数：〇●〇●〇
偶数：〇●〇●〇●
つまり、N/2個以上の4の倍数があれば条件を満たせます。
次に4の倍数がN/2未満以下の場合を考えます。
4の倍数でなくても2の倍数同士の積であれば4の倍数になります。
そのため、条件を満たすためには4の倍数と隣合わない数は2の倍数をかけ合わせる必要があります。
〇●〇●〇〇〇
↑の場合には右の3つの積が条件を満たせません。
2の倍数を◎とし、以下の様にならべると条件を満たせます。
〇●〇●◎◎◎
この2の倍数の個数は4の倍数で条件を満たせる数、つまり4の倍数の数×2をNから引いた数と等しければ条件を満たせます。
上のどちらの条件も満たせない場合はNoを出力します。
問題D
#include <stdio.h> int main(void){ int h,w,n,i,j; int num,a[10001]; int table[101][101]; scanf("%d %d", &h,&w); scanf("%d", &n); int count1 = 0; for(i=0;i<n;i++){ scanf("%d", &num); for(j=0;j<num;j++){ a[count1] = i+1; count1++; } } int count2 = 0; for(i=0;i<h;i++){ if(i%2==0){ for(j=0;j<w;j++){ table[i][j] = a[count2]; count2++; } } else{ for(j=w-1;j>=0;j--){ table[i][j] = a[count2]; count2++; } } } for(i=0;i<h;i++){ for(j=0;j<w;j++){ printf("%d ", table[i][j]); } printf("\n"); } return 0; }
方針
一行に同じ数字を入れていき、列数を越えたら下の行に折り返して後ろから埋める、とジグザグに入れていきます。
例の2を例としてあげると、以下のような配置になります。
12233
44443
55555
解説の図が分かりやすいかと思います。
https://img.atcoder.jp/arc080/editorial.pdf
AtCoder Beginner Contest 204 by C
AtCoder Beginner Contest 204 について
C言語での回答
コンテスト参加3回目です
できたもの
Ａ
Ｂ
できなかったもの
Ｃ
Ｄ以降
問題A
#include <stdio.h> int main(void){ int x,y; scanf("%d %d", &x,&y); if(x==y){ printf("%d", x); } else{ if(x+y==1){ printf("2"); } else if(x+y==2){ printf("1"); } else{ printf("0"); } } return 0; }
方針
あいこになるように手を出す問題。
2人の手が同じであれば同じ手を、違えば残りの一つを出します。
違う手の組み合わせはグーとチョキ（0,1）チョキとパー（1,2）パーとグー（2,0）の3通りで、その和が3つとも異なるのでそれを利用して条件分岐します。
問題B
#include <stdio.h> int main(void){ int n,i; int a; scanf("%d", &n); int total = 0; for(i=0;i<n;i++){ scanf("%d", &a); if(a>10){ total += a-10; } else{ continue; } } printf("%d\n", total); return 0; }
方針
入力された木の実の数が10個以下であれば何もせず、10個以上であれば入力された値から10を引いた値を足して総和を出力します。
問題C
#include <stdio.h> #include <stdbool.h> int road[2001][2001]; bool visited[2001]; int num[2001]={0}; void dfs(int v){ int i; if(visited[v]){ return; } visited[v] = true; for(i=0;i<num[v];i++){ dfs(road[v][i]); } } int main(void){ int i,j,n,m; int a[2001],b[2001]; scanf("%d %d", &n,&m); for(i=0;i<m;i++){ scanf("%d %d", &a[i],&b[i]); a[i]--,b[i]--; } for(i=0;i<m;i++){ road[a[i]][num[a[i]]] = b[i]; num[a[i]]++; } int total = 0; for(i=0;i<n;i++){ for(j=0;j<n;j++){ visited[j] = false; } dfs(i); for(j=0;j<n;j++){ if(visited[j]){ total++; } } } printf("%d\n", total); return 0; }
方針
繋がっている道をDFSで調べ、i番目の町からたどり着ける町をカウントします。既に通った町はvisitedのtrueで判断します。
こっちはTLEになった回答。いまいちどこが原因なのかわからないところ。forで回してvisitedをfalseに初期化してるのは一緒なのでDFSだろうか？
#include <stdio.h> #include <stdbool.h> bool road[2001][2001]; bool visited[2001]; void reset(int n){ int i; for(i=0;i<n;i++){ visited[i] = false; } } int dfs(int v,int n,int c,bool visited[2001]){ int i; visited[v]=true; for(i=0;i<n;i++){ if(road[v][i]==false){ continue; } if(visited[i]==true){ continue; } c++; visited[i] = true; c = dfs(i,n,c,visited); } return c; } int main(void){ int i,j,n,m,a,b; scanf("%d %d", &n,&m); for(i=0;i<m;i++){ scanf("%d %d", &a,&b); a--,b--; road[a][b] = true; } reset(n); int count = 0; int total = 0; //i番目の町をスタートとする時にゴールできる町の数をカウント for(i=0;i<n;i++){ total += dfs(i,n,0,visited); total++; reset(n); } printf("%d\n", total); return 0; }
問題D
まだ
AtCoder Beginner Contest 067 by C
AtCoder Beginner Contest 067 について
C言語での回答
できたもの
A
B
C
できなかったもの
D
問題A
#include <stdio.h> int main(void){ int a,b; scanf("%d %d", &a,&b); if(a%3==0||b%3==0||(a+b)%3==0){ printf("Possible"); } else{ printf("Impossible"); } return 0; }
方針
AかBかA＋Bのいずれかの枚数のクッキーを3匹が同じ枚数食べられるように渡せるか
＝AまたはBまたはA＋Bを3で割ったあまりが０になれば可能
よってif文の条件をそのように書いてやればOK
問題B
#include <stdio.h> int main(void){ int k,n,i,j,tmp; int a[51]; scanf("%d %d", &n, &k); for(i=0;i<n;i++){ scanf("%d", &a[i]); } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(a[i] < a[j]){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } int sum = 0; for(i=0;i<k;i++){ sum += a[i]; } printf("%d\n", sum); return 0; }
問題C
#include <stdio.h> const long long inf = 1LL << 60; long long abs(long long a){ return a < 0 ? -a : a; } int main(void){ int n,i,j; long long tmp; long long a[200001]; scanf("%d", &n); long long sum = 0; for(i=0;i<n;i++){ scanf("%lld", &a[i]); sum += a[i]; } long long sunuke = 0, racoon = sum; long long min = inf; for(i=0;i<n-1;i++){ sunuke += a[i]; racoon -= a[i]; if(abs(sunuke-racoon)<min){ min = abs(sunuke-racoon); } } printf("%lld\n", min); return 0; }
方針
カードの山の上から何枚か取るというのがミソ。
つまり先頭から順番に値を取っていって、取った総和と残った総和の差の絶対値がもっとも小さくなればいいです。
aiを配列に入れ、最初にa1~aNまでの総和を取っておきます。
そこから順に一枚ずつsunukeに足し、racoonから引き、差の絶対値を見ます。
絶対値はabs関数を作り、値が負だった時には符号を逆転しています。
上手くいかなかった点はabs関数の型がintになっていたため、桁あふれしたことです。
あと最初山の上から取るということに気づかず、途中から抜き出す総和……？などといらんことを試案したのがロス。
問題D
#include <stdio.h> #include <stdlib.h> int **pass; int *a; int *b; int *c; int *fennec; int *sunuke; //深さ優先探索 t：距離を求める点、u：その親、v：マス1番かＮ番からの距離 void dfs_F(int t,int u,int v) { int i; fennec[t]=v; for(i=0;i<c[t];i++){ if(pass[t][i]!=u){ dfs_F(pass[t][i],t,v+1); } } } void dfs_S(int t,int u,int v) { int i; sunuke[t]=v; for(i=0;i<c[t];i++){ if(pass[t][i]!=u){ dfs_S(pass[t][i],t,v+1); } } } int main(void){ int n; int i; int ans = 0; scanf("%d", &n); a = (int *)malloc(sizeof(int)*(n-1)); b = (int *)malloc(sizeof(int)*(n-1)); c = (int *)malloc(sizeof(int)*n); sunuke = (int *)malloc(sizeof(int)*n); fennec = (int *)malloc(sizeof(int)*n); pass = (int **)malloc(sizeof(int*)*n); for(i=0;i<n-1;i++){ scanf("%d %d",&a[i],&b[i]); a[i]--,b[i]--; c[a[i]]++; c[b[i]]++; } for(i=0;i<n;i++){ pass[i]=(int *)malloc(sizeof(int)*c[i]); c[i]=0; } for(i=0;i<n-1;i++){ pass[a[i]][c[a[i]]]=b[i]; pass[b[i]][c[b[i]]]=a[i]; c[a[i]]++; c[b[i]]++; } dfs_F(0,-1,0); dfs_S(n-1,-1,0); for(i=0;i<n;i++){ ans += (fennec[i] <= sunuke[i]) ? 1 : -1 ; free(pass[i]); } free(pass); free(a); free(b); free(c); free(fennec); free(sunuke); printf("%s\n", ans > 0 ? "Fennec" : "Snuke"); return 0; }
方針
全ての点において1番のマスからの距離とN番のマスからの距離を計算すると、より距離が短いほうに塗られることになります。
つまり距離が近い点が相手より多ければ勝ちです。
C言語ではvector push_backなどという便利なものはないので代わりに二次元配列を作成。
当然要素数を10^5にすると大きすぎると言われたのでmalloc関数を用いて動的にメモリを確保。
コードについては似たようなことをしていた方の者を参考にしました。
二次元配列に入れたらあとは深さ優先探索でそれぞれの点までの距離を求めます。
今回勉強になったのはループのiはグローバル変数にするとTLEするということでした。
普通関数内で宣言するのでそんなのすることないんですが、まあ処理時間に大きな差が出るんだなあということで一つ。
AtCoder Beginner Contest 066 by C
AtCoder Beginner Contest 066 について
C言語での回答
できたもの
A
B
C
できなかったもの
D
問題A
#include <stdio.h> int max(int a, int b){ return a > b ? a : b; } int main(void){ int a,b,c; scanf("%d %d %d", &a,&b,&c); int max_num = max(a,max(b,c)); printf("%d",a+b+c-max_num); return 0; }
3つから2つ選んで足した時に合計額が一番小さい金額を答える問題。
1番大きい（高い）金額をmax関数を実装してやって求め、3つの合計から引くことで求まります。
逐一比較したり条件分岐するよりスマートだよね←
問題B
#include <stdio.h> #include <string.h> int main(void){ char s[201]; int i,j; scanf("%s", s); int size = strlen(s); int max; int k; for(i=size-1;i>0;i--){ int count = 0; if(i%2==1){ continue; } for(j=0;j<i/2;j++){ if(s[j]==s[j+(i/2)]){ count++; } } if(count==(i/2)){ max = i; break; } } printf("%d", max); return 0; }
iをsize-1から1ずつ減らすことは末尾の文字を消すことに相当します。
偶文字列となるのは当該の文字列の長さが偶数の時だけなので、偶数の時を考えます。
偶文字列であれば、文字列の前半分と後ろ半分が一致するはずなので、そこを比較します。
文字列の長さをi+1としたときに、前半分は0~(i/2)-1、後ろ半分はi/2~iなので、うまくループするように添え字を調整。
一致した時はcountを増やし、countの数と文字列の半分が一致した時が答え。
問題C
#include <stdio.h> int main(void){ int n,a,i,j; int b[200001],b_tmp[200001]; scanf("%d", &n); int k1 = 0, k2 = 0; for(i=0;i<n;i++){ scanf("%d", &a); if(n%2==0){ if(i%2==0){ b[(n/2)+k1] = a; k1++; } else{ b[(n/2)-(k2+1)] = a; k2++; } } else{ if(i%2==0){ b[(n/2)-k1] = a; k1++; } else{ b[(n/2)+(k2+1)] = a; k2++; } } } for(i=0;i<n-1;i++){ printf("%d ", b[i]); } printf("%d", b[n-1]); return 0; }
最初は配列に入れて、別の配列に移しなおしてまた逆に入れるという風にしてたんですが、まあTLE。
というわけで入力時に入る座標めがけて入れてしまえばO(n)なのででそうしました。
最後にいれた数字はb[0]、その一つ前はb[n-1]、更にその一つ前はb[1]…といった様に入るので、うまいこと添え字を変えて実装。
今回は入力時から決まった位置に入れてやりましたが、入力時は順番に受け取り、出力時に工夫するパターンもあるようです。
問題D
#include <stdio.h> #define MOD 1000000007 long long fac[100010],finv[100010],inv[100010]; void COMint(){ int i; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(i=2;i<100010;i++){ fac[i] = fac[i-1]*i%MOD; inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD; finv[i] = finv[i-1]*inv[i]%MOD; } } long long COM(long long n, long long k){ if(n<k){ return 0; } if(n<0||k<0){ return 0; } return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD; } int main(void){ COMint(); int n,i,l,x; int a[100010]={0}; scanf("%d", &n); for(i=1;i<=n+1;i++){ scanf("%d", &x); if(a[x]==0){ a[x]=i; } else{ l=i-a[x]-1; } } for(i=1;i<=n+1;i++){ long long ans = (COM(n-1,i)+2*COM(n-1,i-1)-COM(n-l-1,i-1)+COM(n-1,i-2)+MOD)%MOD; printf("%lld\n", ans); } return 0; }
なぜか答えが一致せず、かなり悩みましたが、原因はaの初期化忘れでした。
初期化大事。
解説からnCrを使うとのことだったので、例の関数を引っ張ってきました。
詳しくは042-D参照。
atcodeeeeer.hatenablog.com
後半の一致するものを調べる方法はまだちょっと理解してません。
ちなみに最初2重ループで重複を調べようとしたらn=10^5のO(n^2)なので当然TLEでした。
本日の教訓：初期化は大事（大事な事なので2回(ry）
解けなかった原因
重複する場合の除外方法が思い付かなかった（nCrともろもろの工夫）
AtCoder Beginner Contest 072 by C
AtCoder Beginner Contest 072 について
C言語での回答
できたもの
A
B
C
できなかったもの
D
問題A
#include <stdio.h> int main(void){ int x,t; scanf("%d %d", &x,&t); if(x>=t){ printf("%d\n",x-t); } else{ printf("0\n"); } return 0; }
最初X[g]で1秒に1g落ちるのでt秒後にはt[g]落ちます。よってX-t。
マイナスにはならないので、差が負になった場合にはif文で0にします。
問題B
#include <stdio.h> #include <string.h> int main(void){ char s[100001]; int i; scanf("%s", s); int size = strlen(s); for(i=0;i<size;i=i+2){ printf("%c", s[i]); } return 0; }
文字列から奇数番目を抜き出す、つまり文字配列の添え字を0→2→4...として出力すればいいです。
i=i+2；で２ずつ増えます。
問題C
#include <stdio.h> int main(void){ int n,i,j; int a; int count[100010]={0}; scanf("%d", &n); for(i=0;i<n;i++){ scanf("%d", &a); count[a-1]++; count[a]++; count[a+1]++; } int max = 0; for(i=0;i<100010;i++){ if(max<count[i]){ max = count[i]; } } printf("%d", max); return 0; }
入力された数字について、-1した値、+1した値、何もしなかった値の中でもっともカウントが多い値が答え。
値を配列で受け取った後、n^2で一致するかどうか確認するとTLEでした。
（N<=10^5なので当然）
しかし上の解法のきっかけになったのでやはりまずは総当たりは大事？
#include <stdio.h> int main(void){ int n,i,j; int a[100001]; int count[1000001]={0}; scanf("%d", &n); for(i=0;i<n;i++){ scanf("%d", &a[i]); } for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(a[j]==a[i]||a[j]==a[i]+1||a[j]==a[i]-1){ count[i]++; } } } int max = 0; for(i=0;i<n;i++){ if(max<count[i]){ max = count[i]; } } printf("%d", max); return 0; }
問題D
#include <stdio.h> int main(void){ int n,i; int p[100001] = {0}; int count = 0; scanf("%d", &n); for(i=0;i<n;i++){ scanf("%d", &p[i]); } for(i=0;i<n;i++){ if(p[i]==i+1){ count++; i++; } } printf("%d", count); return 0; }
pi==i+1の場合、i+1の値に関わらずiとi+1を交換。そうすれば異なります。
交換した場合、i++を付ければi+1を処理済みとしてi+2に移れるので重複しません。
解けなかった原因
i+1が0の場合と1の場合とでiの増加の値を変えていたため、添え字の変化やp[n-1]の扱いなどが分からなくなってしまった。
AtCoder Beginner Contest 057 by C
AtCoder Beginner Contest 057 について
C言語での回答
できたもの
A
B
できなかったもの
C
D
問題A
#include <stdio.h> int main(void){ int a,b; scanf("%d %d", &a, &b); if(a+b<24){ printf("%d\n", a+b); } else{ printf("%d\n", a+b-24); } return 0; }
合計が24以下であればそのまま、24以上であれば-24をすれば24時間表記になります。
問題B
#include <stdio.h> const long long inf = (long long)1 << 60; typedef struct{ int a; int b; }STUDENT; typedef struct{ int c; int d; }POINT; STUDENT stu[51]; POINT point[51]; //絶対値 long long neg(long long nn){ return nn < 0 ? -nn : nn ; } int main(void){ int n,m,i; int check[51]; scanf("%d %d", &n, &m); for(i=0;i<n;i++){ scanf("%d %d", &stu[i].a, &stu[i].b); } for(i=0;i<m;i++){ scanf("%d %d", &point[i].c, &point[i].d); } int j,ians; for(i=0;i<n;i++){ long long min = inf; for(j=0;j<m;j++){ long long cal = neg(stu[i].a-point[j].c)+neg(stu[i].b-point[j].d); if(min>cal){ min = cal; ians = j; } } printf("%d\n", ians+1); } return 0; }
差が負になったときは符号を逆にする関数を作り、あとは問題文中に示されたとおりにマンハッタン距離を計算、最小となるチェックポイントの番号を返します。
配列は0始まりなので出力時は+1を忘れずに。
問題C
#include <stdio.h> int max(int a, int b){ return a > b ? a : b; } int cnt_digits(long long N){ int digits = 0; while(N>0){ N/=10; digits++; } return digits; } int main(void){ long long N,i,j; scanf("%lld", &N); int ans = cnt_digits(N); for(i=1LL;i*i<=N;i++){ if(N%i!=0){ continue; } long long B = N/i; int cur = max(cnt_digits(i),cnt_digits(B)); if(ans>cur){ ans=cur; } } printf("%d\n", ans); return 0; }
Nを割れる数かどうかをチェック。
積の交換法則 A*B = B*AからA*A<=Nを満たすAまで全探索すればいいようです。
最初は素因数分解をすることでABの組み合わせをあげようとしましたが、それこそ10^10まで回す必要と非常に大きな配列が必要なことから無理でどうしたものか悩んでました。
解けなかった原因
10^10に影響されて全探索の可能性を排除していた。
→方針がたたなかった。
問題D
まだ
