Codeforces Round #411 (Div. 2)

codeforces

参加しました、結果は4完でした。
いつもと比べて割と出来がよかったですね、ただ全体的に良かったみたいですが。

A.o
B.o
C.o
D.o

A. Fake NP

問題概要

二つの整数l, r(l <= r)が与えられる。
区間[l, r]にある各整数の約数をカウントしていく。（ただし1は除く）
最も多くカウントされる約数を求めよ、ただし複数ある場合は任意のものを出力してよい。

考えたこと

ぱっと見難しそうで飛ばそうかとも思ったんですが落ち着いて考えてみることにしました。
まず答えが合成数になることは無さそうです、ある合成数で割り切れるのならそれの素因数でも必ず割りきれるので。
よって答えは素数になりそうだなと思いました。（この辺の考察はあんまり意味が無いですけど）

それで素数pに対して、一般に長さLの区間にpで割り切れる数がどれくらいあるかというと、だいたいL/p個くらいです。
なぜなら連続したp個の整数の中にpで割り切れる数は1つしかないからですね。
というわけで、このL/pが最も大きくなるのはpが小さければ小さいほどよいので、p = 2が答えになるだろう、と思いました。

大筋はこれであってるのですが、１つだけ問題があって、l = rかつlが奇数のときですね。
このときは2が約数に入ってこないので、2を出していると不正解になってしまいます。
ただl = rのときはカウントは高々1回で、つまりlを割り切る約数（1以外）なら何でも正解になりますから、lと出力しておけばよさそうです。
r - l >= 1のときは、2個以上の整数が列挙されるので少なくとも2が1回以上カウントされることになり、大丈夫です。

import sys

def solve():
    l, r = map(int, input().split())

    if l == r:
        ans = l
    else:
        ans = 2

    print(ans)

if __name__ == '__main__':
    solve()

B. 3-palindrome

問題概要

文字a, b, cのみを使って長さnの文字列sを作る。ただし、sの長さ3の連続した部分文字列が回文であってはいけない。
例えば、'abc', 'abca'などはよいが、'aba'はダメ。
この条件を満たす文字列で、cを使う回数をなるべく小さくしたい。
cを使う回数を最小にした文字列を1つ出力せよ。

考えたこと

最小って言ってるので、まずはcを1回も使わずにそのような文字列が作れないか考えてみたくなります。
もし作れたら最小性は明らかなのでそれを出力すればよいだけになります。
実際例を見てもcを一度も使わずに構成できているので何だかできそうですよね。

それで小さいケースで考えてみると、例えばn = 4だったら'abba'とかすればよくて、n = 6だったら'abbaab'とかすればいいって感じで何か規則性が見えてきます。
ちゃんと考えると、まず'abb'って作っておいて、後ろに最後から2番目の文字とは違う文字を繋げていけば、長さ3の回文を表れないようにできます。
n >= 3のときはこうやって、n = 1, 2のときは適当にやればいいって感じにやりました。

import sys

def solve():
    n = int(input())

    if n == 1:
        print('a')
    elif n == 2:
        print('aa')
    else:
        ans = ['a', 'b', 'b'] + ['']*(n - 3)

        for i in range(3, n):
            if ans[i - 2] == 'a':
                ans[i] = 'b'
            else:
                ans[i] = 'a'

        ans = ''.join(ans)

        print(ans)

if __name__ == '__main__':
    solve()

上の方法は構成方法から長さ3の回文が現れないことは明らかなので正当性は分かりやすくていいですが、結局'abbaabbaabbaab...'ってなるなあって分かると以下のように書くのがスマートっぽいです。

import sys

def solve():
    n = int(input())

    ans = 'a' + 'bbaa'*100000

    ans = ans[:n]

    print(ans)

if __name__ == '__main__':
    solve()

C. Find Amir

問題概要

頂点{1, 2, ..., n}からなる完全グラフ（任意の2頂点間に枝があるグラフ）が与えられ、頂点i, j(1 <= i < j <= n)間の枝のコストは(i + j) mod (n + 1)と定義される。
このグラフの任意の頂点から出発して、全ての頂点を訪問したい（同じ点は何度通っても良いし、一回コストを払った枝は何度でも無料で通れる）。
このとき必要な最小コストを求めよ。

考えたこと

グラフ理論の言葉を使ってそれっぽくいうと、「最小全域木(Minimum Spanning Tree, MST)を求めよ」というタイプの問題になりますかね。
一般的にMSTを求めるアルゴリズムはプリム法とかクラスカル法っていうアルゴリズムがあるみたいですが、今回の場合はこれらの手法を使わずに簡単に求めることができます。

まず枝のコストの定義からすぐ分かることとして(1, n), (2, n - 1)間の枝のコストは0です。一般的には(i, n + 1 - i)のコストが全て0になります。
0でつなげるものは繋いでおいて損は無いですから、まずこれらの頂点間はコスト0で繋いでおくことにすると、(n + 1) // 2個の連結成分が出来ることになります。
そしてこれらの連結成分は(n + 1) // 2 - 1 = (n - 1) // 2個のコスト1の枝で結ぶことができます。
具体例で考えてみると分かりやすくて、例えばn = 9のときは以下のような感じで結べます。

f:id:nanae1914:20170505151630j:plain

よって、答えはそのまま(n - 1) // 2とO(1)で求めることができました。

import sys

def solve():
    n = int(input())

    ans = (n - 1) // 2

    print(ans)

if __name__ == '__main__':
    solve()

コードだけ見るとA問題並に簡潔に書けてしまいます。

D. Minimum number of steps

問題概要

文字a, bのみからなる文字列sが与えられる。
この文字列sに対して次のような操作を考える。

  • sの部分文字列'ab'を'bba'に置き換える

この操作をsの部分文字列に'ab'が存在しなくなるまですることを考える。
この操作ができなくなるまでの最小回数(mod 10^9 + 7)を求めよ。

例
'ab' -> 'bba'
'aab' -> 'abba' -> 'bbaba' -> 'bbbbaa'

考えたこと

まず気になるのは「結果は操作の順序に依存するのか？」ということです。
依存するなら大変ですが、もし依存しないことが分かれば適当な順序で操作をシミュレートしたときの回数が自動的に答えになります。

とりあえず例のパターンは分岐が無いので、分岐がある小さ目の例を考えてみます。
s = 'abab'として
前の'ab'から置き換えた場合
'abab' -> 'bbaab' -> 'bbabba' -> 'bbbbaba' -> 'bbbbbbaa'
となって4回で終わります。
次に後ろの'ab'から置き換えた場合
'abab' -> 'abbba' -> 'bbabba' -> 'bbbbaba' -> 'bbbbbbaa'
となり、やはり4回で終わります。
最終的な文字列も全く一緒で、操作の順序には依存しなさそうだなあと考えます。

次に今までの例を見て、最終状態が'bb...ba...a'になっていることに気が付きます。
どんな場合も最終状態はこのようになるのか、というとこれは正しいですね。'ab'という文字列があったら操作を続けなければいけないですから。
ということは結局元の文字列にあるaを全てのbの右側に持って行かなきゃダメだなあと分かります。
ここでもう一度与えられた操作「'ab' -> 'bba'」という操作を見てみると、これはbの数が2倍になるスワップであるということに気が付きます。
全てのaをこのbが2倍になるスワップで右側に移動させなきゃいけないんですが、これはちょっと考えると操作の順序に依らないということが分かります。
実際あるaを全てのbより右側に持っていくには、それより右にあるaを先に右に移動させておいてからじゃないとできないからです。

まとめると

  • 与えられた文字列を逆順に読んでいく
  • 読んだ文字がbならbのカウントを+1する
  • 読んだ文字がaなら今まで読んだbの数分だけスワップが必要なので、答えにbのカウントを足す。
  • そしてスワップした後bの数は2倍に増えているので、bのカウントを2倍にする

というアルゴリズムでO(N)で答えが求められます。

import sys

mod = 10**9 + 7

def solve():
    s = input()[::-1]

    ans = 0
    b_cnt = 0

    for ch in s:
        if ch == 'b':
            b_cnt = (b_cnt + 1) % mod
        else:
            ans = (ans + b_cnt) % mod
            b_cnt = (b_cnt * 2) % mod

    print(ans)

if __name__ == '__main__':
    solve()

総評

今回はD問題までは割とすらすら解けました。時間を見ると1時間弱でDまで解けていました。
こういうことはなかなかないので嬉しいですね。
「問題の難易度にあまり差が無くどれだけ早く解けたかで順位が決まってしまうから今回の問題は微妙」という声もありました。
確かにコンテストとしてはあまり良くないかもしれないですが、個人的にはスラスラ解ける問題ばかりで構成されていると問題が解けて気分が良くなるので、たまにはこういうのも悪くないなあと思いました。
コンテストで4問解けることってなかなか無いですから。Atcoder(ARC, AGC)だと1~2完が精々で、酷いと0完というのはなかなか精神的に来るものがあります。

D以降ですが、どっちも全然分かりそうになかったです。Eはまず問題を理解するのに苦労しました。
「元の木の構造は何か関係あるの？」とかそういうのがよく分からず。理解できても解ける気はしなかったです。
FはEより問題は分かりやすかったですが、やっぱり分かりませんでした。期待値＋クエリの問題って感じでした。
同じ連結成分にある2点なら-1で、そうでなければ一方の木からランダムに1点選んで、もう一方の木からランダムに1点選んで、それらの間に辺を張って、出来た木の直径を得られる値とするときの期待値を求めよって感じでした。
いちいち計算してるとTLEするから何か木の性質を使って上手い事計算量を減らすんですかね……