Quantifier Question - #639 div2 e

解法

同じ path 上に 2 つ A が存在することはできない
任意の実数 xi に対し, ..., 任意の実数 xj が, となるから

また, ある path 上で, A になれるのは index が一番小さいのだけ
ある xi が存在し, それに対して..., 任意の xj が, とはできないから

また, 違う path 上の頂点で, 片方が A であっても, 他方に影響しない
A になったら, その path 上の他の頂点はすべて E
A であるかに, path 上の頂点が E であることは関係ない
index が path 上で一番小さくさえあれば, A になれる

することは, path 上で一番小さい頂点か確かめること
topological sort をすればいい

ソースコード
https://codeforces.com/contest/1345/submission/79269866

テストケース
5 4
3 5
5 4
5 2
2 1

1
AEEEE

5 4
3 1
3 5
5 4
4 2

2
AAEEE

Three Variables Game - abc 166 f

.#構築 #ゲーム

問題
https://atcoder.jp/contests/abc166/tasks/abc166_f

正解

具体例で Yes にし続ける方法を考える

例 1
100 100 100
常に, 少ない方に +1 するようにすればよさそう
同じ値の場合でも, 99 未満にはならないし, どっちでもいい

99 未満にならないこと
最初の状態 100 100 100 (1).
AB で 99 101 100 (2) になったとする.
BC が来たら, 99 100 101 で (2) と同様の状態
BC でなく AB だとすると, 100 100 100 で (1) と同様の状態
どちらとも違って AC だとすると, 100 101 99 で, (2).

例 2
0 1 0 (1)
AC なら終わり

AB とする.
1 0 1 で, (1).
AB でなく, BC とすると, 0 1 0 から 0 0 1 で, (1).

要は, 常に 1 つ終わりの選択肢があり, 2 つは生き残れる.

例 3
0 2 0 (1)
AB
1 1 0 (2)
実は, もう No にならないことが確定した

2 つを 0 にするため, AB が次に来るのを考える
どっちを 0 にするかは, 次 C と組で出る文字次第.

1 1 0 から, AB, AC とする
2 0 0
1 0 1
これは (2) と同様の状態であり, 後は繰り返し

間違いの考え

AB, AC, BC に対して各々最初に操作を決めれば, 以降 1 つ前の同じ文字列のときと逆の操作をする
そうすれば, だいたいもとの A, B, C の値に落ち着きそう

ケース
4 1 0 1
AB
AC
AB
BC

Yes

AB で 0 1 1 になるしかない (A -1, B +1)
AC で 1 1 0 になるしかない
もとの A, B, C に近づけようと, 前の AB の逆をやる (A +1, B -1)
2 0 0
(ここで, 0 2 0 ともできた)
次, BC がきて, 2 0 0 から負の数が出る

テスターのふっぴーさん - yukicoder No. 1034

ソースコード
https://yukicoder.me/submissions/469576

n = , y = , x = とする

何周したかは, mi = min({y, n - 1- y, x, n - 1 - x})

その分のマス数は
a(k) = 2 * k + 2 * (k - 2) : 1 辺の長さが k のときの 1 周のマス数
として,
a(n) + a(n - 2) + ... + a(n - 2 * (mi - 1))

a(i) - a(i - 1) = 4 より, 等差数列の和
(項数) / 2 * (初項 + 末項)

あとは 4 回以内残った外周を動けば見つかる

別解 (公式解説)

ソースコード
https://yukicoder.me/submissions/468887

k 周したとして, そのマス数を求める

上に書いた等差数列の和
k / 2 * ( a(n) + a(n - 2 * (k - 1)) )

a(n) = 2 * n + 2 * (n - 2) = 2 * (2n - 2)
a(n - 2 * (k - 1)) = 2 * (n - 2 * (k - 1)) + 2 * (n - 2 * (k - 1) - 2))
= 2 * (n - 2 * (k - 1) + n - 2 * (k - 1) - 2)
= 2 * (2n - 4(k - 1) - 2)

(1) = k * (2n - 2 + 2n - 4(k - 1) - 2)
= k * (4n - 4(k - 1) - 4)
= 4k(n - k)

そのあと残ったマスの外周に沿って右下のマスに行く
今左上にいるから, 右に行って下に行く

1 辺の長さは n - 2k
n - 2k - 1 動くから, 2 * (n - 2k - 1)

そっから戻るか進むか

y = x の線より右上 (y < x) なら戻る

何周かした分を除いた外周なので, 単純に座標の差を見ればいい
((n - 1 - k) - y) + ((n - 1 - k) - x)

Robots in a Grid - #634 div3 f

#cycle 復元 #pair #pii #ダブリング

各頂点出次数 1 より, cycle から外に矢印は出ない
連結成分ごとに考える
各連結成分に cycle は 1 つ

まず, black 関係ない答え

cycle のサイズの合計

それだけ求めるコード

map<pii, pii> G;
vector<vector<char> > table;
map<pii, int> seen;
pii pos = pii(-1, -1); // cycle 中に含まれる頂点 pos
stack<pii> hist; // 訪問履歴

void dfs(pii v, pii p) {
  seen[v] = 1;
  hist.push(v);
  pii nv = G[v];
  if (seen[nv] == 2) return;
  if (seen[nv] == 1) { // cycle を検出
    pos = nv;
    return;
  }
  dfs(nv, v);
  if (pos != pii(-1, -1)) return;
  hist.pop();
  seen[v] = 2;
}

void solve() {
  G.clear();
  seen.clear();

  int n, m;
  cin >> n >> m;

  table = c = vector<vector<char> >(n, vector<char>(m));
  rep(i, n) rep(j, m) cin >> table[i][j];
  rep(i, n) rep(j, m) cin >> c[i][j];

  // U, R, D, L
  int dy[] = {-1, 0, 1, 0};
  int dx[] = {0, 1, 0, -1};
  char ch[] = {'U', 'R', 'D', 'L'};
  rep(i, n) rep(j, m) {
    rep(k, 4) {
      if (ch[k] == c[i][j]) {
        G[pii(i, j)] = pii(i + dy[k], j + dx[k]);
      }
    }
  }

  int ans = 0;
  rep(i, n) rep(j, m) {
    pos = pii(-1, -1);
    dfs(pii(i, j), pii(-1, -1));
    vector<pii> cycle;
    while (!hist.empty()) {
      pii t = hist.top();
      cycle.eb(t);
      hist.pop();
      if (t == pos) { // cycle にはまった
        ans += sz(cycle);
        // break しない, cycle の外の経路も
      }
    }
  }
  cout << ans << '\n';
}

black 関係なく最大にした上で black を最大にする

各 cycle 上の頂点に 0 から番号をつける
cycle の外の頂点には, cycle から近い方から -1 mod (cycle のサイズ) の番号をつけていく

黒だけで, 数字が何種類あるか求めればいい

ソースコード
有向辺である
https://codeforces.com/contest/1335/submission/76933542

十分時間がたった後どこにいるか見る方が楽
https://codeforces.com/contest/1335/submission/76926285

Xenia and Colorful Gems - #635 div2 d

#探索

ソースコード
https://codeforces.com/contest/1337/submission/76924920

g に関して全探索するとする
r は, g の値に近いものをいくつか二分探索で出す

b は, (g + r) / 2 に近いものをいくつか二分探索で出す
ただし, b が g と r の間であることが前提になっているので, 全探索を r, b に関してもする

Cell Distance - abc 127 e

#組合せ

ソースコード
https://atcoder.jp/contests/abc127/submissions/11155856

ずっと考えて AC できた

具体例で説明する

X, Y, K = 2, 3, 3
答えは 100

まず, x, y を分けて考える

x = 1 が何回足されて何回引かれるか考える

マス (1, 1) の x = 1 が何回出るか

マス (1, 1) は他の 5 マスと組みになれる
他の 5 マスから K-1 個選ぶ

そして, 10 組の中で, 2 つとペアになる
10 * 2 = 20

(1, 1), (1, 2), (2, 1)
(1, 1), (1, 2), (2, 2)
(1, 1), (1, 2), (3, 1)
(1, 1), (1, 2), (3, 2)

(1, 1), (2, 1), (2, 2)
(1, 1), (2, 1), (3, 1)
(1, 1), (2, 1), (3, 2)
(1, 1), (2, 2), (3, 1)
(1, 1), (2, 2), (3, 2)
(1, 1), (3, 1), (3, 2)

同じ x である (1, 2) も考えると,
20 * 2 = 40

これだけ x = 1 が出る
このうち, 何回足されて何回引かれて何回何もしないのか

まず, 何もしない分を引く

これは, x = 1 が K 個選ぶうちに何個出るかを探索して求める
i 個 x = 1 が出るとする

x = 1 は N 個ある
x = 1 でないのは NM - N 個ある
よって,

このうち, x = 1 どうしがペアになるのは 組みあり, 2 重になっているので *2 を引く

あとは, 足すか引くか

相手が自分より大きいと引くことになり, 自分より小さいと足すことになる

これは, 自分より大きいもの, 小さいものの割合を考えればいい

abc129 F - Takahashi's Basics in Education and Learning

#数式変形 #二分累乗法

youtube editorial の解読

数列の, k 桁の数の数列を考える
A, A + B, A + 2B
A は入力の A とは別で, k 桁の数列の初項

3 項だけだとすると
A + 2B はそのまま足され, A + B は 10^k されて足され,
A は されて足される
(実際は, k + 1 桁以降の分も 10 倍されて足される)

l - i - 1 は i と変えても同じ

分解

上から考える
A は外に出して,

を考える
f(l) を計算量 log l で求めるには
f(l + 1), f(2 * l) と f(l) の関係が求められたらいい

k = 2 とすると,
f(2) = 1 + 100
f(3) = 1 + 100 + 10000 = 1 + (1 + 100) 100

f(6) = 1 + 10^2 + 10^4 + 10^6 + 10^8 + 10^{10}
f(2) から 2l - l = l 項増えてる

次に,

を考える

B = 4, k = 2 とする
g(2) = 00 04
g(3) = 00 04 08

g(6) = 00 04 08 12 16 20
g(3) = 00 04 08 からどう作るか
2l - l = 3 項分 g(3) が 10^2 倍される
g(3) * 10^6 + g(3) = 00 04 08 00 04 08

これで g(6) との差は 12 12 12

あとは, 桁ごとに独立して解いたのをつなげる

youtube editorial
https://www.youtube.com/watch?v=L8grWxBlIZ4

code reading

コード
Submission #5861224 - AtCoder Beginner Contest 129

ans の計算の流れ
sample1
3, 7, 11, 15, 19
37 (1 桁)
37111519 (2 桁)
となる
37 の次, 37 を111519 の分 10 倍して 111519 を足す

ll b, ten;
 
// x^t
mint pow_(mint x, ll t) { 
  if (t == 0) return 1;
  if (t%2 == 1) {
    return pow_(x, t - 1) * x;
  } else {
    mint y = pow_(x, t / 2);
    return y * y;
  }
}
 
mint f(ll l) {
  if (l == 0) return 0;
  if (l % 2 == 1) {
    ll pl = l - 1;
    return f(pl) * ten + 1;
  } else {
    ll pl = l / 2;
    mint x = f(pl);
    return x * pow_(ten, pl) + x;
  }
}

mint g(ll l) {
  if (l == 0) return 0;
  if (l%2 == 1) {
    ll pl = l-1;
    mint x = g(pl);
    return x*ten + mint(b) * pl;
  } else {
    ll pl = l / 2;
    mint x = g(pl);
    return x * pow_(ten, pl) + x + mint(b) * pl * f(pl);
  }
}
 
int main() {
  ll L, a;
  cin >> L >> a >> b >> mod;
  ll last = a + b * (L - 1); // 数列の末項
  mint ans = 0;
  ten = 10;
  /* 数列における, 各桁の数の初項と末項を求める
  その桁の数列の数の個数も自動的に求まる */
  for (int i = 1; i <= 18; ++i, ten *= 10) {
    ll l = ten / 10, r = ten - 1;
    if (last < l) continue; // 数列自体の末項が左端より小さい
    if (a > r) continue;
    ll na = 0; // [l, r] における初項
    ll nl = 0; // [l, r] における数列の数の個数
    {
      if (a >= l) na = a;
      /* continue されてない中で数列自体の初項が左端以上なら, 
          [l, r] における数列の初項は数列自体の初項 */
      else {
      /* 数列の項だから a + b * i の形でかける
          前提として, a < l (else より) */
      /* l 以降の最初の要素
          l = a + b * i から i を求め, 切り上げ */
      na = (l - a + (b - 1)) / b * b + a; 
    }
    {
      ll nlast = 0;
      /* 数列自体の末項が右端以下なら, 
          [l, r] における末項は数列自体の末項 */
      if (last <= r) nlast = last;
      else {
      /* 前提として r < last
          ([l, r] の末項は数列自体の末項より小さい) */
        nlast = (r - a) / b * b + a;
      }
      nl = (nlast - na) / b + 1; // [l, r] の数列の項数
    }
    ans *= pow_(ten, nl); // 最初 0 にかけても 0
    ans += f(nl) * na;
    ans += g(nl);
  }
  cout << ans.x << endl;
  return 0;
}