ABC178の解答

AtCoder Beginner Contest 178の自分なりの解答を書いていきます。自分なりとは言いましたが、公式の解説を含め、様々な方の解説を参考にしてしています。

問題はこちらから。
https://atcoder.jp/contests/abc178/tasks

A Not

0か1が入力されるので、0なら1を1なら0を出力するという問題。値を取得して少しいじって出力をするという、基礎の問題。

様々な手法で解けますのでお好きな方法で、、

私はboolの反転を使いました。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
int main()
{
 bool x;
 cin >> x;
 
 cout << !x << endl;
 return 0;
}

公式解説では排他的論理和にて x ^ 1 (^はxor)としており、この問題一つとっても、センスの良さを感じました。

B Product Max

整数a, b, c, dが与えられます。条件は

-10^9<=a<=b<=10^9
-10^9<=c<=d<=10^9
a<=x<=b
c<=y<=d

です。このときに、x*yの積の最大値を求めます。

数字を全部試そうとするO(N^2)で時間が足りません。
しかし、答えとなり得るx, y は、各区間の端a, b, c, dのみとなります。これは、xかyのどちらかを固定した、x * yは単調増加、減少になることから分かります。

ということで、4つの値（a*c, a*d, b*c, c*d）の値を比較すれば答えが出ます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;

int main()
{
 vector<ll> a(4);
 rep(i,4) cin >> a[i];
 
 vector<ll> pro;
 rep(i,2)rep(j,2) pro.emplace_back(a[i]*a[j+2]);
 
 ll ans = LLONG_MIN;
 rep(i,4) ans = max(ans, pro[i]);
 cout << ans << endl;
}

C Ubiquity

n個の整数(0~9)で順列を構成したときに0と9を両方含む順列の数を求めます。ただし答えは大きくなるので、10^9+7で割った余りで出力します。

条件を整理するためにベン図で考えます。

求めるべき範囲は緑色で示された部分となります。

これを求めやすい部分を足したり引いたりすることで間接的に求めていきます。使用する範囲は以下の通りです。それぞれ

a 全事象 10^n
b 0を含まない 9^n
c 9を含まない 9^n
d 0も9も含まない 8^n

以上の範囲を使うと答えとなる範囲は

a - b - c + d

と表現されます。これをプログラムで表します。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
const int mod = pow(10,9) + 7;
int main()
{
 int n;
 cin >> n;   
 ll a = 1, b = 1, d = 1;
 rep(i,n){
   a = (a*10) % mod;
   b = (b*9) % mod;
   d = (d*8) % mod;
 }
 ll ans = (a -2*b + d) % mod;
 if(ans < 0) ans += mod;
 
 cout << ans << endl;
 return 0;
}

累乗の計算をC++で書く場合にpowで書くとオーバーフローしてしまいます。そのため、for文を回してその都度modで押さえつけてあげます。また、答えの出力の際にansが負であると%dによって負の剰余が出力されます。これだと誤りとなってしまうのでif文にて正の剰余に戻します。

D Redistribution

整数sが与えられます。全ての項が3以上で、その総和がsであるような数列の数を求めます。このとき、10^9+7で割った余りを出力します。

まず、全ての項が3以上という条件を無視した場合の解について考えます。
s=3としましょう。答えとなるのは

{1,1,1}, {2,1}, {1,2}, {3}

の4種類です。これをどうやって求めるかというと、数Aでよく使った〇と｜を用いて行います。まず、〇と｜を交互に並べます。その後、任意の地点の棒を撤去すれば様々な数列が実現されます。

〇　｜　〇　｜　〇　→ {1, 1, 1}
〇　｜ 　〇　   　〇   →  {1, 2}
〇　    　〇　｜　〇　→ {2, 1}
〇　   　〇　      〇　→ {1, 1, 1}

したがって、数列数はn-1地点において｜がある、ないの2通りなので

2^(3-1) = 4 

通りとなります。

次にこれを動的計画法により解くことをします。少し数を増やして6としまして、｜も少し増やして両端にも設置できるようにします。そして、最も右に｜を置いた地点を考えていきます。これにより、｜よりも右側は考える必要がなくなります。

｜を置く場所に数字をつけます。

0 〇 1 〇 2 〇 3 〇 4 〇 5 〇 6

最も右の｜が0（｜〇 〇 〇 〇 〇 〇：{6} )のときをdp[0]とします。dp[0]は{6}の1通りしか存在しないため、dp[0] = 1です。dp[1]では{1,5}のみですので、dp[1]=1。このとき、｜よりも左側には

0 〇

のみが存在する。そのため、最も右の｜が0のときの数と一致します。

dp[2]では、｜の左側は

0 〇 1 〇

です。この状態は2つに分岐します。といっても、先に求めた、

最も右の｜が0にある（dp[0]）
最も右の｜が1にある（dp[1]）

です。そのため、

dp[2] = dp[0] + dp[1] = 2

と求められます。あとはこれを端まで繰り返すだけです。やってみます。

dp[3] = dp[0] + dp[1] + dp[2] = 1 + 1 + 2 = 4
dp[4] = dp[0] + dp[1] + dp[2] + dp[3]  = 1 + 1 + 2 + 4 = 8 
dp[5] = dp[0] + dp[1] + dp[2] + dp[3] + dp[4]  = 16
dp[6] = dp[0] + dp[1] + dp[2] + dp[3] + dp[4] + dp[5]  = 32

これは、先に述べた方法の2^(6-1)=32と一致してますね。

後は各項3以上の条件を追加するだけです。ここまでできれば簡単で、右端の｜から2個以内には｜が入らないことを導入するだけです。dp[5]の場合を考えると、3,4には｜が入らないので次のようになります。

0 〇 1 〇 2 〇 × 〇 × 〇 5 ｜ 6 〇

dp[5] = dp[0] + dp[1] + dp[2]

この条件のもと0からsまで回してあげれば答えになります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
const int mod = pow(10,9) + 7;
int main(){
 int s;
 cin >> s;
 
 vector<int> dp(s+1);
 dp[0] = 1;
 rep(i, s+1){
   rep(j, i-2){
     dp[i] = (dp[i] + dp[j]) % mod;
   }
 }
 cout << dp[s] << endl;
 return 0;
}

dp[1] = dp[0], dp[2] = dp[1] + dp[0]となることから、dp[i]は、これまでの総和にdp[i-1]を加えた数になります。そのため、その地点での総和を保持しておけば、for文を一つ減らすことができます。

E Dist Max

ｎ個の点が与えられます。2点選んだときのマンハッタン距離が最大のものを出力します。また、マンハッタン距離というのは2点の座標が
(x1, x2), (y1, y2)の場合

|x1 - x2| + |y2 - y2|

となります。

愚直にやるとTLEするので簡単に解ける方法を考えます。

まず、xy座標にて等しいマンハッタン距離を持つ点をプロットしていくと、45°傾いた正方形が出来上がります。(45°傾こうが正方形なのですが、、)
ということで、思い切って座標系自体を45°傾けてしまいます。傾けたのちの座標をu, v座標とします。

u, v座標は

u = x - y
v = x + y

と表されます。なぜこうなるかは様々考えられますが、π/4回転

とすると、わかりやすいのでしょうか。大きさの1/√2については後で言及します。

u, v 座標系ではマンハッタン距離は軸に平行な正方形で表されます。この正方形は等しいマンハッタン距離を結んだものでしたので、1辺の長さの半分がその距離に対応します。そして、その長さはuとvの大きい方になります。

図の場合、原点からのマンハッタン距離が３のものが緑の正方形を形成します。この正方形の1辺の長さは原点（0,0）と(-1,3)のu軸、v軸上の距離の大きい方と対応します。

また、図で示された2点のマンハッタン距離を求めたいなら、(3-(-1))と(3-3)の大きい方の４になります。(｜u1 - u2｜と｜v1 - v2｜の大きい方)

ここまでできると何が嬉しいかというと、xとyに関して独立に考えることが可能となります。そのため、計算量がO(n^2)からO(2*n)に落とすことができます。

以上より、アルゴリズムは

１、各地点に関してxi - yi と xi + yiにてu, v座標に変換する。
２、uの最大値と最小値の差、vの最大値と最小値の差を計算する。
３、uの差とvの差の大きい方が最大のマンハッタン距離となる。

となります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
const int inf = 2e9;
int main(){
 int n;
 cin >> n;
 int umax = -inf, umin = inf;
 int vmax = -inf, vmin = inf;
 
 rep(i, n){
   int x, y;
   cin >> x >> y;
   int u = x - y;
   int v = x + y;
   umax = max(umax, u);
   umin = min(umin, u);
   vmax = max(vmax, v);
   vmin = min(vmin, v);
 }
 
 int ans = max(umax - umin, vmax - vmin);
 cout << ans << endl;
 return 0;
}

大きさについて少し触れます。座標変換をした時に、1/√2が出てきました。これを無視しているのでこの変形は等積変形とはなりません。ヤコビアンからもわかる通り正方形の面積は2倍に、緑の辺は√2倍になります。

ただし、今回注目しているのはマンハッタン距離であるので、u, v座標のユークリッド距離は考える必要がありません。正方形上の点のマンハッタン距離は座標変換後も不変です。

一度u,v上にてどの2点が最大値を取るかという候補のみを求めて、そのマンハッタン距離をx, y座標にて求めてみると、同じ結果が得られることが確認できます。

F Contrast

長さnの数列aとbが与えられる。a, bはそれぞれ昇順にソートされている。bを好きなように並べ替えて、aのi番目とbのi番目がすべて異なるような数列ができるかどうかを判定して、もしできるのであればbの並べ方を一つ示すという問題。

まず、できるかどうかを判定します。

n = 5 で aのなかに2が3個あるとします。そのとき、bのうちに2が配置できるのは 5 - 3=2箇所となります。そのため、bに含まれる2の数が2以下であれば、2に関して条件を満たせます。

a : 2 2 2 * *
b : × × × 〇 〇
〇のところに2を配置できる。

これがnまでの全ての数で成り立てば良いです。〇（n - aの数）が （bの数）以上であればよいので、条件は次になります。

数列a b の最頻値の出現回数 <= n

次に条件を満たす場合に並び替えることを考えます。様々な方法が考えられますが、今回は昇順に並んでいることを利用して、bの数列を逆順にすることにより解きます。

まず、bの配列を逆順にソートします。この処理が非常に賢いです。

逆順にソートされた b を rb とします。a と rb にてai == bi となっている数字は最大で1種類しかありません。言い換えると、2種類以上の数字が被ることはないということです。これを説明します。

0種類のときは省略します。

1種類（s）がi番目で一致しているとします。aは昇順のため i+1 番目以降は s 以上の数のみ出現しますが、一方、rbは降順のためのi+1番目以降には s 以下の数しか出現しません。そのため、i+1番目以降で一致する可能性がある数字は s のみです。i - 1以前も同様に s のみ一致する可能性があります。

一致する数は s のみであるとわかったので、あとは愚直に入れ替えていきます。

まず、a と br をみて sを入れ替えてもよい場所を検索します。
（a[i] != s && rb[i] != s） 

その後、入れ替える必要がある場所と先の入れ替えてもよい場所を入れ替えていきます。
（a[i] == s && rb[i] == s）

これにより、条件を満たす数列が完成します。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main(){
 int n;
 cin >> n;
 vector<int> a(n);
 vector<int> b(n);
 rep(i,n) cin >> a[i];
 rep(i,n) cin >> b[i];
 
 vector<int> hab(n+1,0);
 rep(i,n+1) ++hab[a[i]], ++hab[b[i]];
 
 int mst = 0;
 rep(i, n+1) mst = max(mst, hab[i]);
 
 if(mst > n){
   cout << "No" << endl;
   return 0;
 }
 //降順にそーｔ
 sort(b.begin(),b.end(),greater<int>());
 //かぶっている文字を求める
 int same;
 rep(i,n){
   if(a[i] == b[i]){
     same = a[i];
     break;
   }
 }
 
 //交換可能な場所を求める。
 vector<int> sw;
 rep(i,n){
   if(a[i] == same || b[i] == same) continue;
   sw.emplace_back(i);
 }
 
 //交換する.
 int idx = 0;
 rep(i,n){
   if(a[i] == same && b[i] == same){ 
     int p = sw[idx];
     swap(b[i],b[p]);
     ++idx;
   }
 }
 
 cout << "Yes"<< endl;
 rep(i,n) cout << b[i] << " ";
 cout << endl;
 
 return 0;
}

今回はbを降順にソートして解きましたが、様々な方法で解けます。

a, bの最頻値の回数 <= nを崩さないように、a, bからペアを取っていく手法であったり、a, bをくっつけ、ソートして真ん中で分ける、みたいな手法も紹介されていました。

いろいろな方がいろいろな手法を紹介していましたので、興味がありましたら、この問題の別の解法を調べてみると面白いと思います。