2019-04-18

【codeFlyer】C - 徒歩圏内

AtCoder 二分探索累積和 codeFlyer

問題概要

N個の都市がそれぞれ座標X_iにある. 2つの都市間の距離がD以下であれば徒歩で, そうでなければ電車で移動する.

このとき, 3つの都市の組(i, j, k)であり, 以下の条件を満たすものの個数を求めよ.

i < j < k
都市iと都市j, 都市jと都市kを徒歩で移動する.
都市iと都市kを電車で移動する.

制約

3 <= N <= 10⁵
0 <= X_i <= 10⁹
0 <= D <= 10⁹

考察

二分探索がほのかに香ってきたのでその方針で考える.

都市iから都市j, 都市jから都市kまで徒歩で移動する場合の数から, 都市iから都市kまで徒歩で移動する場合の数を引けば良さそう. 前者をA, 後者をBと置いて求め方を考えていく.

Aについて

都市iを固定する. 都市iから徒歩で行ける都市j全てについて, さらにその都市jから徒歩で行ける都市kの数を数えれば良い.

それぞれの都市から徒歩で行ける都市の数をあらかじめ数えておく. これはそれぞれの都市について, どの都市まで徒歩で行けるかを二分探索することで求められる(O(NlogN)). (変数名はwalk)

次に, それぞれの都市から徒歩で行ける都市について, walkの和を順に足していきたい. 徒歩で行ける都市はもちろん並んでいるので, walkの累積和を取ることでオーダーを落とせる.

よって, どの都市まで徒歩で行けるかを二分探索で調べ, そのwalkの区間和を累積和で求めることによりAが求められた(O(NlogN)).

Bについて

都市iを固定する. そこから徒歩で行ける都市の数を二分探索で求める. それらの都市から適当に2つ選べばBの条件を必ず満たすので, Bが求められた(O(NlogN)).

【ABC041】D - 徒競走

AtCoder ABC-D DP bitDP

問題概要

$N$ 匹のうさぎがいる. $M$ 人の観客から, うさぎ $x_i$ がうさぎ $y_i$ よりも先にゴールしたという情報を得た. これら全ての情報に合致する着順が何通りあるかを求めよ.

制約

$2\leq N\leq 16$
$1\leq M\leq \frac{N(N - 1)}{2}$

考察

bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかを $N$ bitの状態として持つ(bitが立っていればすでにゴールしているとする).

遷移

dp[n][stat]からの遷移を考える. 次に遷移する候補は, statのbitが立っていないものから選ぶ.

候補のうさぎを $p$ とすると, 情報と照らし合わせたとき

$x_i=p$ なら, $y_i$ はまだゴールしていないはず.
$y_i=p$ なら, $x_i$ はすでにゴールしているはず.

この2つの条件を満たしていないと, 情報に合致していないと分かり, 遷移を行わない.

満たしているときは, dp[n+1][stat+(1<<p)] += dp[n][stat]として配っていけば良い.

よって遷移に $O(M)$ かかって, 全体の計算量は, $O(MN^{2}2^{N})$ .

ただ, 現状この計算量だと最悪で $10^{9}$ を超えてしまうので, 遷移する際に無駄な情報を見ない(うさぎ $p$ に関する情報だけを集約する)ようにしてごまかした().

【ABC115】D - Christmas

AtCoder ABC-D

問題概要

レベルLのバーガーを以下のように定義する.

レベル0のバーガーは, 'P'.
レベルLのバーガー(L>=1)は, 'B' + (レベルL-1のバーガー) + 'P' + (レベルL-1のバーガー) + 'B'.

このとき, レベルNのバーガーの下からX層までに'P'は何個あるか求めよ.

制約

1 <= N <= 50
1 <= X <= (レベルNのバーガーの層の総数)

考察

Nがもっと小さければ単純に再帰書いて文字列作っていけばいいけど, Nが50まで行くから無理(最低2⁵⁰文字). 徐々に問題のサイズを小さくしていけば良さそう.

以下, レベルLのときのバーガーの層の総数をl[L], 'P'の個数をp[L]とする.

N=2のとき, BBPPPBPBPPPBB.

Xが赤い文字に対応するときは, バーガーを完全に包含してるか, もしくは完全に含んでいないときなので, 再帰を終了.
Xが青い文字に対応するときは, レベルN-1のバーガーの途中だから, レベルを1つ下げて再帰.

こんな感じのイメージで再帰を回す.

実装

Xは予め1引いて0から始まるようにした(なんかそっちのほうが単純そうだったので).

レベルNのとき, 赤い文字に対応するっていうことは, Xは0, l[N]/2, l[N]-1.

X = 0のとき, 何も含んでないので何もせずに終了.
X = l[N]/2のとき, レベルN-1のバーガーを1つ含んでいるので, res += p[N-1]+1をして終了(この+1は中心の'P').
X = l[N]-1のとき, レベルNのバーガーを1つ含んでいるので, res += p[N]をして終了.

青い文字に対応するっていうことは, X > l[N]/2 と X < l[N]/2.

X > l[N]/2のとき, レベルN-1のバーガーを1つ含んでいるため, まずそれを上のX=l[N]/2みたいに足して, X -= l[N-1]+2 (この括弧内の分: [BBPPPBP]BPPPBB).
X < l[N]/2のとき, 何も含んでいないので何もせずに, X -= 1 (頭の'B'の分).

レベル0になったら, もうそれ以上分けられないから, res += 1して終了.

【ARC071】E - TrBBnsformBBtion

AtCoder ARC-E 文字列

問題概要

'A', 'B'のみからなる文字列S, Tが与えられる. Sの部分文字列sについて, 以下の4つの操作を好きなだけ行ってよいとき, Tの部分文字列tに変換することは出来るかという判定クエリにq個答えなさい.

'A'を'BB'にする.
'B'を'AA'にする.
'AAA'を消す.
'BBB'を消す.

制約

1 <= |S|, |T|, q <= 10⁵
s, tはそれぞれS, Tの部分文字列.

考察

制約ををざっと見てみると, クエリの数が最大10⁵個と多すぎる. 判定に使えるオーダーは高々O(log|S|)程度だけど, logのオーダーで文字列処理するアルゴリズムなんてあるのか...? O(1)臭が凄いから, 諸々証明出来るか試してみる.

仮説1. 操作は可逆である.

真だったら, それぞれの文字の個数をmod 3で考えることにより, 操作3,4とその逆は考慮に入れる必要が無くなる.

操作1,2について, BB → AAAA → A 操作3,4については, 操作後に1文字は必ず残っているため, その1文字がAの場合とBの場合に分けて考える.

A → BB → AAAA
B → AA → ABB → AAAB
B → AA → BBA → BAAA

よって, 全ての操作が可逆であると分かった.

仮説2. s, tの並びは結果に影響しない.

真だったら, それぞれの文字の個数について考えるだけで良くなる. (偽だったら, s, tについて走査しなきゃいけないからO(1)じゃない.) 以下, 便宜上, 文字'A'がn個並んだ文字列を, [A,n]のように表記する.

自然数a,bについて, [A,a]+[B,b]になんらかの操作をすることにより[B,1]+[A,a]+[B,b-1]に変換できたなら, 各操作におけるA, Bの対称性より, その操作を繰り返すと任意の並びにできる(はず).

実際に, 以下のように操作が行える.

[A,a]+[B,b] → [A,a]+[B,1]+[B,b-1] → [A,a]+[A,2]+[B,b-1] → [A,1]+[A,1]+[A,a]+[B,b-1] → [B,2]+[B,2]+[A,a]+[B,b-1] → [B,3]+[B,1]+[A,a]+[B,b-1] → [B,1]+[A,a]+[B,b-1]

仮説1より, この逆の操作も行えるため, 示された(と思う).

最後の詰め

先ほど述べたように, 操作3,4とその逆は考える必要がなくなった(操作1,2を行って, 最後に差分が3の倍数であれば変換可能と分かるため).

sの中の'A', 'B'の個数をそれぞれa, b個, tの中のそれらの個数をそれぞれ(a+m), (b+n)個とする. 今, 操作1をp回, 操作2をq回行うと, 'A'は(q-p)個, 'B'は(p-q)個増えるため, (a+q-p), (b+p-q)個となる. よって, $a+m\equiv a+q-p,\ b+n\equiv b+p-q\ (\mathrm{mod}\ 3)$ を満たしていれば良い. ちょっと式変形して $-m\equiv n(\mathrm{mod}\ 3)$ ならば"YES", そうでないならば"NO"となる. ああ美しい😇

実装

いもす法で任意区間における'A'の個数をO(1)で取り出せるようにしておいて, あとは上の判定式に突っ込んで出力するだけ🙌

ACコード(C++🔆)

// 未整形より工事中

2018-12-02

【ABC114】D - 756

AtCoder ABC-D

問題概要

N!の約数のうち, 約数をちょうど75個持つものの個数を求めよ.

制約

1 <= N <= 100

考察

約数が75個ある整数を素因数分解したときどうなるか考えてみると,

a² * b⁴ * c⁴
a² * b²⁴
a⁴ * b¹⁴
a⁷⁴

の4通り. とりあえずN!の素因数がそれぞれ何個ずつあるのかを求めておいて, この4通りになりうるものが何個あるのかを足していけばいい.

指数が大きいものを決めてから、小さいものの帳尻を合わせれば数え漏れはないはず.

ACコード(C++🔆)

map<int,int> prime_factor(int n) {
  map<int,int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++ret[i];
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

vector<int> d(101,0);
int c_2, c_4, c_14, c_24, c_74;

signed main() {

  int N;
  cin >> N;

  for (int i = 1; i <= N; ++i) {
    auto p_f = prime_factor(i);
    for (auto itr=p_f.begin(); itr!=p_f.end(); ++itr) {
      d[itr->first] += itr->second;
    }
  }

  for (auto& e : d) {
    if (e >=  2)  c_2++;
    if (e >=  4)  c_4++;
    if (e >= 14) c_14++;
    if (e >= 24) c_24++;
    if (e >= 74) c_74++;
  }

  int res = 0;
  // a^2 * b^4 * c^4 -> C(c_4,2) * (c_2 - 2)
  res += max(0,c_4*(c_4-1)/2*(c_2-2));
  // a^2 * b^24 -> c_24 * (c_2 - 1)
  res += max(0,c_24*(c_2-1));
  // a^4 * b^14 -> c_14 * (c_4 - 1)
  res += max(0,c_14*(c_4-1));
  // a^74
  res += c_74;
  cout << res << endl;
}

2018-12-02

【ABC114】C - 755

AtCoder ABC-C

問題概要

1以上N以下の整数のうち, '7', '5', '3'が1回ずつ現れ, なおかつそれら以外の数字が現れないものの個数を求めよ.

制約

1 <= N < 10⁹

考察

bit全探索的なノリで数えるみたい. とりあえず3進法で書いてみたけど, 頭の0に対応するのめんどくさそうだったから4進法に書き直した.

おおまかな工程

ループ変数はi.

iを4進数に変換する(tobase4).
それが'1', '2', '3'を含んでおり, かつ'0'を含んでいなければ残りの処理を続行(check).
'1'を'3', '2'を'5', '3'を'7'に変えたとき(変換の順序に注意), それがNより大きいなら終了. そうでないならres++.

ACコード(Python3🐍)

n = int(input())

def tobase4(num):
    ans = ''
    while num>0:
        ans += str(num%4)
        num //= 4
    return ans[::-1]

def check(s):
    if '1' in s and '2' in s and '3' in s and '0' not in s:
        return True
    return False

def conv(s):
    s = s.replace('2','5')
    s = s.replace('3','7')
    s = s.replace('1','3')
    return s

res = 0
for i in range(10**9):
    s = tobase4(i)
    if not check(s):
        continue
    s = int(conv(s))
    if n < s:
        break
    res += 1
print(res)

別解1(DFS) 別解2(itertools.product) 別解3(桁DP) 別解4(†埋め込み†)

2018-11-03

【Tenka1 Programmer Contest】D - Crossing

AtCoder Tenka1 構築

問題概要

$\{1,2,\cdots ,N\}$ の部分集合の組 $(S_1,S_2,\cdots ,S_k)$ について, 以下の条件を満たすものがあれば構築せよ.

[条件1] $1,2,\cdots ,N$ のうちどの整数も, $S_1,S_2,\cdots ,S_k$ のうちちょうど2つに含まれる.
[条件2] $S_1,S_2,\cdots ,S_k$ のうちどの2つの集合をとっても, その共通成分はちょうど1つである.

制約

$1\leq N\leq 10^{5}$

考察

とりあえず, $N=1$ について考えてみると, $S_1=S_2=\{1\}$ として構築できる.
この $S_1,S_2$ と共通成分を1つずつもつような $S_3$ を作りたい. ちょっと考えると, $S_1=\{1,\underline{2}\},S_2=\{1,\underline{3}\},S_3=\{\underline{2},\underline{3}\}$ のように, 要素 $2,3$ を追加すれば良いと分かる.
この $S_1,S_2,S_3$ と共通成分を1つずつもつような $S_4$ を作りたい. 同様にして, $S_1=\{1,2,\underline{4}\},S_2=\{1,3,\underline{5}\},S_3=\{2,3,\underline{6}\},S_4=\{\underline{4},\underline{5},\underline{6}\}$ のように, 要素 $4,5,6$ を追加すれば良い.
こんな感じで再帰的に構築できそうだという予想がつく. このとき, $\displaystyle N = 1+2+\cdots+k=\frac{k(k+1)}{2}$ より, 三角数でなければならない.

f:id:morio_prog:20181103194020p:plain:w300

ACコード(Python3🐍)

n = int(input())
r = int((n*2)**.5)
if r*(r+1)!=n*2:
    print('No')
    exit()
# nは三角数
res = [[] for i in range(r+1)]
tmp = 0
for i in range(r-1):
    for k in range(tmp,r-i+tmp):
        res[i].append(k+1)
        res[i+k-tmp+1].append(k+1)
    tmp += r - i
res[-2].append(n)
res[-1].append(n)
print('Yes')
print(len(res))
for l in res:
    print(len(l),*l)