AtCoder 4 - 不定期プログラミング覚え書き

AtCoderが基本土日開催でおすすめ、という話を聞いて初参加。
A,B,Cを応えての30位でした。

ProblemA 2点間距離の最大値

問題

２次元座標が複数個（最大100くらい）与えられるので、二点間距離の最大値を返せ

考えたこと

やるだけ、100*100とか時間余裕だし。

コード

int main(){
   int n_case;
   cin >> n_case;
   vector<pair<int,int> > vec;
   for( int i = 0 ; i < n_case; i++ ){
      int a,b;
      cin >> a >> b;
      vec.push_back( make_pair(a,b));
   }
   int m = 0;
   for( int i = 0 ; i < n_case; i++ ){
    for( int j = i+1; j < n_case; j++ ){
      pair<int,int> p1 = vec[i];
      pair<int,int> p2 = vec[j];
      int dx = p1.first-p2.first;
      int dy = p2.second-p1.second;
      m=max(m, dx*dx+dy*dy );
    }
   }
    double dm =m;
    dm = sqrt(dm);
    cout << dm;
   return 0;
}

ProblemB 2点間距離の最大と最小

問題

n個の頂点がある。座標はわからないが、i番目の頂点〜i+1番目の頂点の距離（全部でn-1個）が与えられる。
最初の頂点と最後の頂点の距離で、起こりえる最大値・最小値を返せ

考えたこと

……えっ、なにこれいきなりむずい。最大値は楽勝だけど最小値どうしろと？
…………
……難問と思ったけどそんなことはなかったぜ。
0番目頂点とk番目頂点の距離の最小値dismin,最大値dismaxがあったとする。
k番目頂点とk+1番目頂点の距離dが与えられるとする。
すると、0番目頂点とk+1番目頂点の距離の最大値はdismax+d, 最小値はdismin<=d<=dismaxなら0。dismax

コード

int main(){
   int n_case;
   cin >> n_case;
   int ans1=0;
   int ans2=0;
   vector<int> dist;
   for( int i = 0 ; i < n_case; i++ ){
    int tmp;
    cin >> tmp;
    dist.push_back(tmp);
    if( ans1 >= tmp && ans2 <= tmp ) ans2 = 0;
    if( ans1 < tmp ){
      ans2 = tmp-ans1;
    }
    if( ans2 > tmp ){
      ans2 = ans2-tmp;
    }
    ans1 += tmp;
   }

   cout << ans1 << endl;
   cout << ans2 << endl;
   return 0;
}

ProblemC 平均値太郎の憂鬱

問題

1,2,...,N-1,Nまでの平均値を算出したつもりが
一つだけ値(M)を足し忘れたせいで、結果がX/Yになってしまった。
あり得るN,Mの組み合わせを返せ。

考えたこと

1,...,Nまでの平均値は $\frac{N+1}{2}$ であるから、
Mを覗いて算出された平均値というのは、
$\frac{N+1}{2}-\frac{M}{N} = \frac{X}{Y}$
ガリガリ式変形をすると
$M= N\times \left(\frac{N+1}{2}-\frac{X}{Y}\right)$
$M$ が1以上N以下の整数でなくてはいけないことから、 $0<\frac{1}{N}\leq \frac{N+1}{2}-\frac{X}{Y}\leq 1$
このことより、 $\frac{2X}{Y}-1 < N \leq\frac{2X}{Y}+1$
といったNの範囲が定まるので、この値に対してだけ、Mが整数になるかを検討すれば良い。

コード

long long gcd( long long X, long long Y ){
  if( X > Y ) return gcd( Y, X );
  if( Y%X==0) return X;
  else return gcd(Y%X, X );
}

int main(){
   long long X;
   char c;
   long long Y;
   cin >> X >> c >> Y;
   long long g = gcd(X,Y);
   X/=g;
   Y/=g;
   long long tmp = 2*X/Y-1;
   if( tmp*Y>= 2*X-Y ) tmp++;
   tmp = max( 1LL, tmp );
   bool flag = false;
   for( ; tmp <= 2*X/Y+1 ; tmp ++ ){
     //cout << tmp << endl;
     long long bunshi = Y*(tmp+1)-2*X;
     if( bunshi < 0 ) continue;
     long long bunbo = 2*Y;
     //cout << tmp<< "*" <<  bunshi << "/" << bunbo << endl;
     if( (tmp*bunshi)%bunbo== 0){
      cout << tmp <<" "<< (bunshi*tmp/bunbo) << endl;
      flag = true;
     }
   }
   if( flag == false ) cout << "Impossible" << endl;
   return 0;
}

個人的メモ

いまだに「A/Bよりも大きい最小の整数」の類をサクッと求められない癖を治したい。
簡単にシミュレートしてみた
B=5としてAを0から順に増やしていくとする。横軸はA/Bの値

コード	0/5	1/5	2/5	3/5	4/5	5/5	6/5	7/5	8/5	9/5	10/5
(A+B)/B	1	1	1	1	1	2	2	2	2	2	3
(A+B-1)/B	0	1	1	1	1	1	2	2	2	2	2
(A+1)/B	0	0	0	0	1	1	1	1	1	2	2
A/B	0	0	0	0	0	1	1	1	1	1	2
(A-1)/B	0	0	0	0	0	0	1	1	1	1	1
(A-B+1)/B	0	0	0	0	0	0	0	0	0	1	1
(A-B)/B	-1	0	0	0	0	0	0	0	0	0	1

まとめ

(A+B)/B： A/Bより大きい最小の整数
(A+B-1)/B： A/B以上の最小の整数(ceil)
A/B： A/B以下の最大の整数(floor)
(A-1)/B：だいたいは、A/Bより小さい最大の整数（ただしA=0の時は0が返る事に注意）
(A+B-1)/B-1： A/Bより小さい最大の整数(A=0の時も-1が返る)

Aの値に負の値が入るときとかは、この方法は使わないほうが無難な気がした。

ProblemD 表現の自由

整数 N と M が与えられる時、整数 N を M 個の整数の積で表す方法は何通りあるでしょうか。
その答えを 1,000,000,007 で割った余りを答えてください。

考えたこと

Nを素因数分解して、各素因数をM個のうち何処に配置するかってことですよね。
2^2とかになった時にどうするか、がポイントなのか？
と言うか組み合わせとかオーバーフローする香りしかしないんですけど。

復習

2^2とかについては冷静に考えたら全く問題なかった。ただの高校数学なのに何を悩んでいるのか。
K個の玉をM個のボックスにいれるパターン数は、
K個の玉と、M-1個の仕切りを並べる問題に帰着できるのだから、 ${}_{(K+M-1)} C_K$
しかし案の定combinationはカオスだった。蟻本とかに書いてある剰余の逆元とか使う臭いのだけれど、まだそこは理解していない。