【abc-178】個人的ふりかえり（A〜E）

#ふりかえり
　ABCの３完。Dが何も思いつかなかった。個人的にはD飛ばしてEやればよかった気がする。Fは見てない。

#A問題
　0なら1を、1なら0を出力する。

```php
#include<bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  if(N == 0){
    cout << 1 << endl;
  }
  else{
    cout << 0 << endl;
  }
}
```


#B問題
　a,b,c,dがどんな値を取ろうとも、結局最大値になるのは a*c, a*d, b*c, b*d　のいずれかである（試せば分かる）。よってこの4つの最大値を求めればいい。これらの積は```int```に収まらない可能性があるので、```long long```で受け取った。

```php
#include<bits/stdc++.h>
using namespace std;

int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;

  ll A,B,C,D;
  A = a*c;
  B = a*d;
  C = b*c;
  D = b*d;
  
  cout << max(max(A,B), max(C,D)) << endl;  
}

```
#C問題
　長さNの数列の組み合わせは　10^N　通り　（各項0〜9の10通りの値を取りうるから）
　0である項が存在しないのは　9^N　通り　（各項9通り）
　9である項が存在しないのは　9^N　通り　（各項9通り）　
　0と9の項が存在しないのは　8^N　通り　（各項8通り）
　したがって求めるのは、10^N-9^N-9^N+8^N となる。N乗を計算する際、数が大きくなりすぎないように、適宜100000007で割ることを忘れずに。
　また、余りが負になる可能性があるときは、先に100000007を足してからmod(100000007)を求めるか、最後に100000007を足すかする。

```php
#include<bits/stdc++.h>
using namespace std;

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

int main(){
  int N;
  cin >> N;
  ll s,t,u;
  s=1;
  t=1;
  u=1;
  rep(i,N){
    s*=10;
    s%=1000000007;
  }
  rep(i,N){
    t*=9;
    t%=1000000007;
  }
  rep(i,N){
    u*=8;
    u%=1000000007;
  }
  
  ll ans;
  ans = (s-2*t+u)%1000000007;
  if(ans<0){
    ans = ans+1000000007;
  }
  cout << ans << endl;  
}
```
      
      
#D問題
　具体例で考えてみる。
　n=0　→　{}（※空集合として考える）
　n=1　→　
　n=2　→　
　n=3　→　{3}
　n=4　→　{4}
　n=5　→　{5}
　n=6　→　{6},{3,3}
　n=7　→　{7},{3,4},{4,3}
　n=8　→　{8},{3,5},{4,4},{5,3}
　n=9　→　{9}{3,6}{4,5}{5,4}{6,3}{3,3,3}
と続いていくわけだが、例えば**n=9のときの全組み合わせはn=0~n=6から導ける**のである。

　n=0~n=6のそれぞれ数列の末尾に、数列の和が9になる数を加えてみると、n=9のときの数列が全て現れることがわかる。
　n=0　→　{**9**}
　n=1　→　
　n=2　→　
　n=3　→　{3,**6**}
　n=4　→　{4,**5**}
　n=5　→　{5,**4**}
　n=6　→　{6,**3**},{3,3,**3**}

したがって、S=nのときの数列の個数をdp[n]とすると、
```dp[9]=dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5]+dp[6]```が成り立つ。
これを一般化すると、
```dp[n]=dp[0]+dp[1]+...+dp[n-4]+dp[n-3]  (dp[0]=1, dp[1]=0, dp[2]=0)```
となる（解法①）。
さらに、
　  dp[n+1]=dp[0]+dp[1]+...+dp[n-4]+dp[n-3]+dp[n-2]
　　　　　=dp[n]+dp[n-2]
であるから、
```dp[n]=dp[n-1]+dp[n-3]  (dp[0]=1, dp[1]=0, dp[2]=0)```
となる（解法②）。

以下、解法②の例。

```php
#include<bits/stdc++.h>
using namespace std;

int main(){
  int S;
  cin >> S;
  vector<int> dp(2010, 0);
  
  //初項、第2項、第3項の設定
  dp[0]=1;
  dp[1]=0;
  dp[2]=0;
  
  //DP(動的計画法)
  for(int i = 3; i<=2000; i++){
    dp[i] = dp[i-1]+dp[i-3];
    dp[i] %= 1000000007;
  }
  
  cout << dp[S] << endl; 
}
```

これ気づかなかったの悔しい。自分で気づきたかった。

#E問題

　２点(x1, y1),(x2, y2)のマンハッタン距離に対し、**|a|=max(a, -a)**を利用して以下の変形を行う。
　|x1-x2|+|y1-y2|
=max(x1-x2, -x1+x2)+max(y1-y2, -y1+y2)
=max(x1-x2+y1-y2, x1-x2-y1+y2, -x1+x2+y1-y2, -x1+x2-y1+y2)
=max{(x1+y1)-(x2+y2), (x1-y1)-(x2-y2), -(x1-y1)+(x2-y2), -(x1+y1)+(x2+y2)}
(**X1=x1+y1,Y1=x1-y1**とすると)
=max(X1-X2, Y1-Y2, -Y1+Y2, -X1+X2)


　ここで今回求めたいのは、|x1-x2|+|y1-y2|の最大値だから、
　max(|x1-x2|+|y1-y2|)
=max{max(X1-X2, Y1-Y2, -Y1+Y2, -X1+X2)}
=max{max(X1-X2), max(Y1-Y2), max(-Y1+Y2), max(-X1+X2)}
=max{max(X)-min(X), max(Y)-min(Y), -min(Y)+max(Y), -min(X)+max(X)}
=max(max(X)-min(X), max(Y)-min(Y))

　したがってx+yとx-yの最大値と最小値を求めれば、上の式で答えが求まる。

```php
#include<bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  int max_X, min_X, max_Y, min_Y;
  max_X = 0;
  min_X = 2000000000;
  max_Y = -1000000000;
  min_Y = 1000000000;
  
  int x,y;
  for(int i = 0; i<N; i++){
    cin >> x >> y;
    max_X = max(max_X, x+y);
    min_X = min(min_X, x+y);
    max_Y = max(max_Y, x-y);
    min_Y = min(min_Y, x-y);
  }
  
  cout << max(max_X-min_X, max_Y-min_Y);
  
}
```


F問題はいつかやります。