Yandex.Algorithm Round 2

りんごさんと３問ずつwriterをしていました。ABDを書いてました。
Zebra Hyupoの元ネタについてはこちら。でもオーストラリアの横断歩道にはシマシマついてないのね・・・

A

いろんなケースを考えないと行けないので極めてWAしやすい、危険牌。

概要

配列が与えられるので、各頂点の次数がその配列に対応した木があるかどうか・一意であるかどうか。

解法

まず、次数の合計が2(V-1)でないならば木にならないのでNone。それ以外は次数が１のものを最も次数の大きいものに繋げて行くなどとすれば木にはなる。
一意かどうかの判定は、次数１の頂点・次数２の頂点・次数３以上の頂点に分けてやって、とりあえず次数１の頂点はどうでもいいので無視する。次数２の頂点の数と次数３以上の頂点のパターンで表を作ってみると間違いにくいかも。

３以上のパターン＼２の個数	0	1	2以上
なし	Unique	Unique	Unique
A	Unique	Unique	Multiple
AA	Unique	Multiple	Multiple
AAA	Unique	Multiple	Multiple
AAAA	Multiple	Multiple	Multiple
AB	Unique	Multiple	Multiple
AAB	Multiple	Multiple	Multiple

例えば "AAB" は「3,3,4」とか「10,10,5」とかです。

B

今日のセットの中ではボス問だったらしい。少しごつめだけどバグリにくいし、実装もそんなに重くない。

概要

i番目のマスにx^i mod p(pは素数)が書かれている。カエルk匹が0番目のマスにいる状態から、以下の操作を繰り返す。
・カエル1が１マス進む
・カエルi-1が今までに踏んだマスの値の合計がmの倍数になったらカエルiは１マスだけ進む
・カエル1とカエルkの距離がd以上になったら終了
最終的なカエル1の位置は？
1 <= x < p <= 10^5, 2 <= m <= 10, 2 <= k <= 10 (kは一応10^5とかでも大丈夫), 1 <= d <= 10^13

解法

x^iの周期はpが素数なのでp-1である。a*i mod mの周期はmである。つまり(p-1)*mマス進めば必ず１周期するので、そこまでの「あるマスに到達するまでに累積和がmの倍数になる回数」を前計算で全部求めておく。
こうすると、カエルiがマスXにいるときのカエルi+1の位置がO(1)で求まるようになるので、あとはカエル1の位置で２分探索すればよい。

#include<iostream>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;

const int MX = 100005;
const ll LINF = 1000000000000000000ll;

int n, p, k, m;

int a[MX*10];

ll pos(ll x){ return x/n*a[n-1] + a[x%n];}

ll f(ll x){
  ll y = x;
  rep(i,k-1) y = pos(y);
  return x-y;
}

int main(){
  ll x, d;
  cin >> x >> p >> k >> m >> d;
  n = (p-1)*m;
  
  a[0] = 1;
  rrep(i,n-1) a[i] = a[i-1]*x%p;
  rrep(i,n-1) a[i] = (a[i]+a[i-1])%m;
  rep(i,n) a[i] = !a[i];
  rrep(i,n-1) a[i] += a[i-1];
  
  ll l = -1, r = LINF, c;
  while(l+1<r){
    c = (l+r)/2;
    if(f(c) >= d) r = c; else l = c;
  }
  
  cout << r << endl;
  
  return 0;
}

案外短い。

C

緑三角。そんなに簡単ではない気がするのになぜか人気だった。

概要

点がN個あるので、その中から３つ選んで３角形を作る時の面積の期待値は？
3 <= N <= 2000

解法

外積の式が "x1*y2 - y1*x2" というかたちをしているので、２点を固定した時にO(1)とかで作れる三角形の面積の和を求められそうな気がしてくる。単にx座標とy座標の和をそれぞれ求めてかけ算して引いてとかすると、負の面積の三角形も数えてしまって相殺してしまう。正の面積の三角形だけ数えたいのだけど、それは反時計回りに180度の領域になっているので角度でソートとかして尺取みたいにやるといい。

D

簡単枠。だけどちょい危険。

概要

x op y = z を満たす四則演算子は？（ない/一意でないなら"Invalid"）

解法

全部試す。だけど割り算を「if(z*y==x)」とするとyが0のときに・・・

E

ちょいむずい。わりとWAしやすい。

概要

サイズ４以上のサイクルのない連結なグラフを良いグラフと呼ぶことにする。
良いグラフが与えられるので、良いグラフであることを保ったまま追加できる辺の最大本数は？
頂点数 <= 10^5

解法

とりあえずBFSとかをして最短路木にすると1-2-3と繋がってる時に1-3にも辺があるというケースを無視できるので吉。あとは葉から貪欲にサイズ３の閉路を作って行く。

F

わりと簡単だけどなめると痛い目にあう。

概要

s="RGB"という文字列に対して
swap(s[0],s[1]) をちょうど p回
swap(s[0],s[2]) をちょうど q回
swap(s[1],s[2]) をちょうど r回
行って文字列 t に出来るか。

解法

p,q,rを２で割ったあまりとかでぜんぶ3以下(コード書いて実験すると分かるのですがこれが下限)にして、てきとうにシミュレーション。不安ならもっと大きくしてメモ化とかすれば良い。