ABC183 参戦記録 p.28

itsuki

2020年11月16日 20:26

itsukiです。
AtCoder Beginner Contest 183 に参戦した様子です。解説記事ではありません。

結果は A, B, C の 3完でした。

考察の流れ

A - ReLU

「関数の定義」を見て一瞬怯む

普通にif文だった

#include <stdio.h>
int main(){
   int x;
   scanf("%d",&x);
   if(x<0){ printf("0\n"); }
   else{ printf("%d\n",x); }
   return 0;
}

B - Billiards

もしかして一次関数？（苦手）
最近解いた ABC181-C を思い出す

一次関数のグラフだとすると、
「跳ね返る前の傾きの -1 倍」＝「跳ね返った後の傾き」になる

入力例1 で考えると、
　前：y = - (1/2)*x + 3/2
　後：y = (1/2)*x - 3/2
というグラフになる（上図は脳内イメージ）

点 (S_x, S_y) と点 (X, 0) を通るグラフの傾きと、
点 (G_x, G_y) と点 (X, 0) を通るグラフの傾きを考える

(S_y - 0) / (S_x - X) = -1 * (G_y - 0) / (G_x - X) を X について解くと
X = (S_y*G_x + G_y*S_x) / (S_y + G_y) になる

#include <stdio.h>
typedef long long ll;
int main(){
   ll sx, sy, gx, gy;
   double ans;
   scanf("%lld%lld%lld%lld",&sx, &sy, &gx, &gy);
   ans = (double)(sy*gx + gy*sx) / (double)(sy+gy);
   printf("%.10lf\n",ans);
   return 0;
}

C - Travel

最初と最後は「都市1」と固定されているため、
他の全ての都市の順列を考える

最近 ABC150-C を解くために、next_permutation を自作した！これだ！！

本番で next_permutation を使うのが初めてということもあり
非常に手間取るも、なんとか一発AC（この問題だけで1時間超…）

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
void int_swap(int*a, int*b){ int tmp=(*a); (*a)=(*b); (*b)=tmp; }

void sw_int(int* intgr, int dig){
	int tmp={0},i,j;
	for(i=0, j=dig-1; i<dig/2; i++, j--){
		tmp = intgr[i];
		intgr[i] = intgr[j];
		intgr[j] = tmp;
	}	
}

int next_int_permutation(int arr[], unsigned int n){
	for(int i=n-2; i>=0; i--){
		if( arr[i] < arr[i+1] ){
			int j = n;
			do{
				j--;
			}while( arr[i] >= arr[j] );

			int_swap( &arr[i], &arr[j] );
			sw_int( arr+i+1, n-i-1 );
			return 1;
		}
		if( i==-1 ){
			sw_int( arr, n );	// arr配列を逆順に並び替える
		}
	}
	return 0;
}

int main(){
   int n;
   ll k,cnt=0;
   scanf("%d%lld",&n,&k);
   ll t[10][10]={0};
   for(int i=0; i<n; i++){
       for(int j=0; j<n; j++){
           scanf("%lld", &t[i][j]);
       }
   }
   // 初期順列生成（最初と最後を除く）
   int arr[10]={0};
   for(int i=0; i<n-1; i++){ arr[i]=i+1; }
   //
	do{
       ll sum=0;
       for(int i=0; i<n-1; i++){
           if(i==0){
               sum += t[ 0 ][ arr[i] ];
               sum += t[ arr[i] ][ arr[i+1] ];
           }else if(i==n-1){
               sum += t[ arr[i] ][ 0 ];
           }else{
               sum += t[ arr[i] ][ arr[i+1] ];
           }
       }
       if( sum==k ){ cnt++; }
	}while(next_int_permutation(arr, n-1));	  // 次の順列を生成
	printf("%lld\n", cnt);
	return 0;
}

D - Water Heater

着手した時点で残り時間 10分… imos 法か？と気づく

最近解いた ABC014-C を思い出すも、実装力が足りず時間切れ

コンテスト後：

#include <stdio.h>
#define Yes()       printf("Yes\n")
#define No()        printf("No\n")
typedef long long ll;
int main(){
	ll i,n,w,s,t,p,max=200005,table[200010]={0};
   scanf("%lld%lld",&n,&w);
   for(i=0; i<n; i++){
       scanf("%lld%lld%lld",&s,&t,&p);
       table[s]+=p;
       table[t]-=p;
   }
   for(i=0; i<max; i++){
       table[i+1] += table[i];
       if( table[i] > w ){ No(); return 0; }
   }
   Yes();
   return 0;
}

そのまま imos 法…！ AC したかった…

まとめ

・過去に解いた問題に助けられた
・実装力＆早解き力が足りず時間切れで悔しい…早解きの練習をする
・本番で自作 next_permutation を使って AC できたのは嬉しい
・本文中で言及した「ABC181-C」「ABC014-C」については後ほど記事化（記事化したので追記：2021.05.02）

引き続き、のんびり精進します。

#note初心者 #備忘録 #参戦記録 #AtCoder #ABC #プログラミング #競プロ #C言語 #一次関数 #順列 #imos #累積和

この記事が気に入ったらサポートをしてみませんか？