ABC068 メモ書き

A問題

Nをscanfで受け取ってABCの後にprintするだけ。1分で終わる

B問題

最初戸惑ったけど、与えられたNより大きい2^xをfor文で探せば2^x-1が答えになる。

1. #include<stdio.h>
2. int main(void){
3. int a,b=0,c=2;
4. scanf("%d",&a);
5. while(c<=a){
6. c=c*2;
7. }
8. printf("%d",c/2);
9. return 0;
10. }

C問題

問題文の解釈がここから難しくなってきた。

要するに船の出発と到着をx[i]、y[i]と置いた時に、x[i]=1となるy[i]が存在して、かつy[i]=Nが存在すれば可能であると考えた。

そういった解釈の下に描いたプログラムがこれ。

1. #include<stdio.h>
2. #include <stdlib.h>
3. int main(void){
4. long *x,*y,*n,*m;
5. long N,M,i,k;
6. int check = 0,breakflag=0;
7. int a=0,b=0;
8. scanf("%ld %ld",&N,&M);
9. x = (long *)malloc(M*sizeof(long));
10. y = (long *)malloc(M*sizeof(long));
11. n = (long *)malloc(M*sizeof(long));
12. m = (long *)malloc(M*sizeof(long));
13. for(i=0;i<M;i++){
14. scanf("%ld %ld",&x[i],&y[i]);
15. if(y[i]==N){
16. n[a]=x[i];
17. a=a+1;
18. }
19. if(x[i]==1){
20. m[b]=y[i];
21. b=b+1;
22. }
23. }
24. for(i=0;i<b;i++){
25. for(k=0;k<a;k++){
26. if(m[i]==n[k]){
27. check = 1;
28. breakflag=1;
29. break;
30. }
31. if(breakflag)break;
32. }
33. }
34. if(check) printf("POSSIBLE");
35. if(check == 0) printf("IMPOSSIBLE");
36. free(x);
37. free(y);
39. return 0;
40. }

当然のようにTLEになった。(計算量を減らす工夫は割と施したがダメだった)

初心者特有の、データを全て配列に入れて吟味するというやり方からはそろそろ卒業する必要がある。