読者です 読者をやめる 読者になる 読者になる

Yandex.Algorithm Round 2

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

A

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

概要

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

解法

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

3以上のパターン\2の個数 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が1マス進む
・カエルi-1が今までに踏んだマスの値の合計がmの倍数になったらカエルiは1マスだけ進む
・カエル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マス進めば必ず1周期するので、そこまでの「あるマスに到達するまでに累積和がmの倍数になる回数」を前計算で全部求めておく。
こうすると、カエルiがマスXにいるときのカエルi+1の位置がO(1)で求まるようになるので、あとはカエル1の位置で2分探索すればよい。

#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つ選んで3角形を作る時の面積の期待値は?
3 <= N <= 2000

解法

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

D

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

概要

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

解法

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

E

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

概要

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

解法

とりあえずBFSとかをして最短路木にすると1-2-3と繋がってる時に1-3にも辺があるというケースを無視できるので吉。あとは葉から貪欲にサイズ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を2で割ったあまりとかでぜんぶ3以下(コード書いて実験すると分かるのですがこれが下限)にして、てきとうにシミュレーション。不安ならもっと大きくしてメモ化とかすれば良い。