Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1796-3be90727
この記事にトラックバックする(FC2ブログユーザー)

Testing Round #1 B問題 - Right Triangles (この記事を編集する[管理者用])

Source

Codeforces Testing Round #1 B問題
Problem description

問題概要

.または*からなる1000*1000以下のグリッドが与えられる.
*を3つ選んで,斜辺以外の2辺がx軸y軸に平行な直角三角形を作る方法は何通りあるかを求める問題.

解法

各*に対してそれを直角の角となるような直角三角形が何通りできるかを計算して足していく.
直角三角形の作り方は,同じ行から他の*を選ぶ選び方と同じ列から他の*を選ぶ選び方の積.

C言語のスパゲッティなコード
#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

char mp[1010][1010];

int main(){
  int i, j;
  int x, y, sum_x[1010] = {}, sum_y[1010] = {};
  long long res = 0;

  scanf("%d%d",&x,&y);
  rep(i,x) scanf("%s",mp[i]);
  rep(i,x) rep(j,y) if(mp[i][j]=='*') sum_x[i]++, sum_y[j]++;
  rep(i,x) rep(j,y) if(mp[i][j]=='*') res += (sum_x[i]-1) * (sum_y[j]-1);

  printf("%I64d\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1796-3be90727
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。