@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

【ABC115】D - Christmas

問題概要

レベル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まで行くから無理(最低250文字). 徐々に問題のサイズを小さくしていけば良さそう.

以下, レベル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して終了.

ACコード(Python3🐍)

n,x = map(int,input().split())
x -= 1

p = [1]
l = [1]
for i in range(n):
    p.append(p[-1]*2+1)
    l.append(l[-1]*2+3)

res = 0
while n >= 0:
    if n == 0:                 # レベル0のバーガーはこれ以上細分化できない
        res += 1
        break
    elif x == 0:               # 左端
        break
    elif x == l[n] - 1:        # 右端
        res += p[n]
        break
    elif x == l[n] // 2:       # 中心
        res += p[n-1] + 1
        break
    elif x > l[n] // 2:        # 1個包含している
        res += p[n-1] + 1
        x -= l[n-1] + 2
        n -= 1
    else:                      # 包含していない
        n -= 1
        x -= 1

print(res)

【ARC071】E - TrBBnsformBBtion

問題概要

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

  1. 'A'を'BB'にする.
  2. 'B'を'AA'にする.
  3. 'AAA'を消す.
  4. 'BBB'を消す.

制約

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

考察

制約ををざっと見てみると, クエリの数が最大105個と多すぎる. 判定に使えるオーダーは高々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++🔆)

// 未整形より工事中

【ABC114】D - 756

問題概要

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

制約

1 <= N <= 100

考察

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

  • a2 * b4 * c4
  • a2 * b24
  • a4 * b14
  • a74

の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;
}

【ABC114】C - 755

問題概要

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

制約

1 <= N < 109

考察

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

おおまかな工程

ループ変数はi.

  1. iを4進数に変換する(tobase4).
  2. それが'1', '2', '3'を含んでおり, かつ'0'を含んでいなければ残りの処理を続行(check).
  3. '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(†埋め込み†)

【Tenka1 Programmer Contest】D - Crossing

問題概要

\{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)

【Tenka1 Programmer Contest】C - Align

問題概要

A_1,A_2,\cdots,A_NN個の整数を好きな順番に並べたとき, 隣り合う要素の差の合計の最大値を求めよ.

制約

  • 2\leq N\leq 10^{5}
  • 1\leq A_i\leq 10^{9}

考察

とりあえずN個の整数をソートする. 最小の数字と最大の数字は隣同士であってほしいお気持ちになったので, 一旦そこを並べる. 次は最小の方に2番目に大きい数字を, 最大の方に2番目に小さい数字を並べる. こんな感じで貪欲に差を大きくしていけば良さそう.
Nが奇数だったら最後一個余るけど, そこも貪欲に置けばいい.

ex.) 1,2,3,6,8
[1] 1,8res=8-1=7
[2] 6,1,8,2res=7+(6-1)+(8-2)=18
[3] 3,6,1,8,2res=18+(6-3)=21
よって, 21と求まった.

ACコード(Python3🐍)

n = int(input())
a = sorted([int(input()) for _ in range(n)])
res = a[-1] - a[0]
minn,maxx = a[0],a[-1]
for i in range(1,n//2):
    res += maxx - a[i]
    res += a[-1-i] - minn
    minn,maxx = a[i],a[-1-i]
if n%2==1:
    res += max(abs(maxx-a[n//2]),abs(minn-a[n//2]))
print(res)

【ABC048】D - An Ordinary Game

問題概要

操作後に同一の文字が隣り合わないように, 両端以外からお互いに1文字ずつ取り除いていく. このような操作を行うことが出来なくなった方が負けとなる. 先手と後手のどっちが勝つかを出力せよ.

制約

  • 3\leq |s|\leq 10^{5}
  • sの中に同一の文字が隣り合う箇所はない

考察

操作できなくなる寸前の文字列の長さの偶奇が分かれば, 初期状態の文字列の長さの偶奇と比べることによりどっちが勝つか分かりそう.
両端の文字は絶対取り除けないから, 一旦sからそれらを抜き出してみる.
例えば, adbcadbcbababbになる. 制約より, この隣り合っているbの間に何らかの文字があったことは分かるので, abab?bとなる.
初期状態では9文字だったのが, 操作できなくなる寸前では6文字と, 計3回の操作を行った時点で詰んでいるため先手の勝ちだと分かる.
厳密な証明が出来ないのが怖いけど, 通ったからよし(よくない)

ACコード(Python3🐍)

s = input()
t = [i for i in s if i in (s[0],s[-1])]
r = len(t)
for c,d in zip(t[:-1],t[1:]):
    r += c==d
print('Second' if len(s)%2==r%2 else 'First')

蛇足

(解説が天才すぎて理解できない;。;)