naoya_t@hatenablog

いわゆるチラシノウラであります

SRM735

6/26 20:00JST〜

起きてたのでSRMに参加
(今回は、追加開催が決まったTCO18 Algo Round2CがこのSRMと同時開催)
touristと同じroom3だった
→2完409.95点で37位

1491→1611 (+120) 黄色ワーイヽ(`▽´)/
f:id:n4_t:20180627224645p:plain:w500

Easy - PalindromeSubsequence (250)

  • とりあえずa,b別々に見て
  • どこを中心にするかで、あるいはどことどこを端にするかで洗い出して
  • 組み合わせ可能なものを...
  • とか難しく考えてたんだけど、ああ、aaaa, bbbb みたいなのでいいじゃん、これなら2組だ、もともとpalindromeなら1組だし、そのどちらかでは
  • コード書くか
  • あれ?マウス動かない。キー入力が反応しない
  • Mac落ちてる><
  • 再起動(こういう時に限ってまた時間がかかる)
  • コード書いて
  • Arena再起動…
  • submitした (22'37'')
  • 落ちる前の(固まった画面上での)提出状況から見て10分程度はロスしてる…
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define rep(var, n) for (int var = 0; var < (n); ++var)

class PalindromeSubsequence {
 public:
  vector<int> optimalPartition(string s) {
    int k = s.size();
    int bad = 0;
    vi ans1(k, 1), ans2(k);
    rep(i, k) {
      ans2[i] = (s[i] == 'a') ? 1 : 2;
      if (s[i] != s[k - 1 - i]) ++bad;
    }
    if (bad)
      return ans2;
    else
      return ans1;
  }
};

Medium - QuadraticIdentity (500)

まだまだ時間あるし。気を取り直してMediumを開く

  • 数学ゲーだ
  • x^2 = x + cm なので x(x-1) = cm
  • c=kl, m=ab として
    • x(x-1) = (kl)(ab) = (ka)(lb)
    • x=ka, x-1=lb(あるいは x-1=ka,x=lb、だけどそれはa,bを入れ替えただけの話なのでa,bを入れ替えて考えればいい)
    • x=ka=lb+1
    • a,bが与えられたとき、ka-lb=1 を満たすk,lがあれば行ける(なければa,bでは無理)。要するにgcd(a,b)=1に限るということ。そこからはextgcdの仕事
    • (extgcdの結果を補正するのにmod b取って負なら+bすればいいんだけどいつも負の数のmodが怖くてできないやつ)
    • x=kaってオーバーフローしたりしない?と心配(kが[0,b)ならするわけないんだけど)
    • m=ab、すなわちmの全ての約数aについて試したら…というかすべての正の整数について約数かどうか(mを割り切れるかどうか)チェックしながらやったとしても2√m で6.3e7ぐらいだし間に合いそうな制約だ
  • 結果が500個を超えるときは半分に減らして、それでも500個を超えるならさらに半分、…で500個以内に収めたものを返す
  • 提出 39'20''
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define IN(x, a, b) ((a) <= (x) && (x) <= (b))

ll gcd(ll a, ll b) {
  while (a) swap(a, b %= a);
  return b;
}

template <class T>
T extgcd(T a, T b, T &x, T &y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}

class QuadraticIdentity {
  ll sub(ll a, ll b) {
    // about 1e15
    ll x, y;
    extgcd(a, b, x, y);
    if (x < 0) {
      ll negs = (-x) / b;
      x += b * negs;
      y -= a * negs;
      if (x < 0) {
        x += b;
        y -= a;
      }
    }
    if (x >= b) {
      ll poss = x / b;
      x -= b * poss;
      y += a * poss;
    }
    // now a*x == -b*y+1
    return x;
  }

 public:
  vector<long long> getFixedPoints(long long m) {
    set<ll> s;
    ll sq = sqrt(m);
    for (ll a = 1; a <= sq; ++a) {
      if (m % a) continue;
      ll b = m / a;
      ll g = gcd(a, b);
      if (g != 1) {
        continue;
      }
      ll x = sub(a, b);
      if (IN(x, 0LL, b) && IN(a * x, 0LL, m - 1)) s.insert(a * x);
      if (a != b) {
        x = sub(b, a);
        if (IN(x, 0LL, a) && IN(b * x, 0LL, m - 1)) s.insert(b * x);
      }
    }
    vector<ll> tmp(ALL(s));
    int L = tmp.size();
    int sh = 0;
    while ((L >> sh) > 500) ++sh;
    int step = 1 << sh;
    vector<ll> ans;
    ans.reserve(500);
    for (int i = 0; i < L; i += step) ans.pb(tmp[i]);
    return ans;
  }
};

Hard - MaxSquare (1000)

まだ12分ちょい残ってたので開いた
疑似乱数生成のコードを書いて終わった

Challenge phase

  • 人がchallengeしてくるのを横目で見つつ、上位陣のコードを鑑賞
  • touristが500のコードを開いてそっ閉じしてくれる実績解除

f:id:n4_t:20180626233537p:plain:w500

  • 生き残った(部屋8位)

System Test

  • 生き残った!(37位)
    • 500通したの39人とか
    • これは黄色に戻れそう→戻れた(1611)ワーイヽ(`▽´)/

f:id:n4_t:20180626234022p:plain:w500
f:id:n4_t:20180626234034p:plain:w500

after

診断人さんのYouTubeライブを観戦&解法ヒント提供。


x=ka, x-1=lb、というのをそれぞれmod a, mod bして

  • x≡0 (mod a)
  • x-1≡0 (mod b) なので x≡1 (mod b)

この2つからxを求める(aで割ると余りが0で、bで割ると余りが1になるxってなーんだ)という視点で解いたら中国剰余定理。
(see also: けんちょん先生のブログ