Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ABC203 参加記録

AtCoder コンテスト参加記録
  • 3完0ペナ 97分でした
  • E問題解けたと思いましたが、、TLE で3完になりました。しばらく一度に提出するのを控えようと思います。

A - Chinchirorin

if 文を使って条件を列挙し、問題文の通りに判定します。

a, b, c = map(int, input().split())
if a == b: print(c)
elif a == c: print(b)
elif b == c: print(a)
else: print(0)

B - AtCoder Condominium

部屋番号の整数を実際に構成して、足し合わせて答えとします。 1 \leq N, K \leq 9 なため、計算量は余裕です。

N, K = map(int, input().split())
ans = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        ans += i*100 + j
print(ans)

C - Friends and Travel costs

10^{100} が大きいのでここまで行き着くかまずは考えてみます。 最初に 10^{9} 円を持ち、 2 \times 10^{5} 人から 10^{9} 円をもらう場合でも 2 \times 10^{14} くらいで終わります。よって最後に到達することは考えなくて良さそうです。

友達からもらうお金は、辿り着ける村の順番にあらかじめソートします。 順に見ていく中で、辿り着いたときに負の値になると、途中でお金が足りなくなったと判断します。

N, K = map(int, input().split())
l = [(0, 0)]
for _ in range(N):
    A, B = map(int, input().split())
    l.append((A, B))
l.sort(key=lambda x: x[0])
i = 0; 
for a, b in l:
    if K < a - i:
        print(i + K)
        return
    K -= a - i
    i += a - i
    K += b
print(i + K)

D - Pond

本番では方針さえ全然思いつきませんでした。二分探索で答えを決め打ち、0 1 に変換する方針の問題は前にも出てきていたのでちゃんと覚えておきたい典型です。

マスの行列の大きさの最大が 800 なため、各マスを探索する分には O(N^{2}) で十分間に合います。そこから中央値の探索をすることを考えます。

中央値は値そのものよりも順位を見る統計量です。 K\times K の区画を動かすことを考えたとき、元々の中央値の値より小さい値(もしくは大きい値)がいくつ抜けていくつ入ってきたかを考えようとしました。この場合、行または列で少なくとも O(K) の確認を行う必要があり、最終的に O(N^{2}K) になります。 大体 6\times 10^{7} くらいになるのでそこそこ厳しいです。また、同じ値が出入りしたときの更新の方法も簡単ではなさそうです。

答えを二分探索で決め打ちしたとき、全てのマスについて、その決め打ちした値以上か？それとも未満か？を 0 1 で表現できます 。 K \times K の区画で、1 の数が \lfloor\frac{K^{2}}{2}\rfloor +1 個以上あれば、その値は中央値になる可能性があります。

この確認を全ての区画( (N-K)^{2} 個の区画)で行って、少なくとも一つ中央値になる可能性があるとなれば、二分探索の上限を小さくでき、そうでないなら下限を大きくします。

K \times K の区画で 0 1 の個数の集計をそのままやると、区画ごとに O(K^{2}) かかり TLE ですが、二次元累積和を使えば前処理に O(N^{2}) 、区画の 0 1 の個数集計は O(1) で答えられます。

二分探索は O(\log{a_{\max}}) で済むので、全体で O(N^{2}\log{a_{\max}}) で解けます。

D問題 提出コード

def accumulate_2d(field:list, H:int, W:int) -> list:
    """
    二次元累積和を計算する
    """
    res = [[0]*(W+1)]
    for i in range(H):
        tmp = field[i].copy()
        res.append([0] + tmp)
    for i in range(1, H+1):
        for j in range(1, W+1):
            res[i][j] += res[i-1][j] + res[i][j-1] - res[i-1][j-1]
    return res


def f(n):
    global A, N, K
    # 0 1 判定
    B = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            B[i][j] = A[i][j] >= n
    # 累積和テーブル
    field = accumulate_2d(B, N, N)
    # 各区画で個数計算
    l = K; r = K
    for k in range(N-l+1):
        for j in range(N-r+1):
            tmp = field[l+k][r+j] - field[k][r+j] - field[l+k][j] + field[k][j]
            if tmp < K**2//2+1: 
                # ある区画でより小さい値が中央値になる
                return False
    return True


def main():
    global A, N, K
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
    
    R = 10**9+1 # right side
    L = 0 # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        t = f(n=mid) # boolean function
        if t: L = mid # True
        else: R = mid # False
    ans = L
    print(ans)


if __name__ == "__main__":
    main()

E - White Pawn

本番で、解き方は割とすぐ思いつきましたが、TLE を解消できませんでした。

黒ポーンの配置の制約から、境界については考える必要はなさそうです。 サンプルにあるようなケース以外にも、特に下記の場合の動きを正しく管理するにはどうするか？を考えます。

f:id:Xenous:20210606132216p:plain
確認した自作テストケース

黒のポーンが置かれている位置についてソートし、左端から順に見ていきます。各黒ポーンの時点で、到達できる y 軸の値を集合 (この集合を S とおきます) で管理します。

まず、新しく移動可能になる y 座標について考えます。このポーンの y 座標を q とおくと、 q が S に含まれておらず、 q+1 または q-1 が S に含まれているなら、 S に q を追加することができます。

次に、移動可能だった場所が移動できなくなるパターンを考えます。これは 「 q+1 と q-1 が S に含まれていない」かつ「 q が S に含まれている」が成り立つときです。このとき q を S から削除します。

以上で要素の管理のルールは表現できました。あとはこれを間に合うように更新させていきます。

黒ポーンをソートして順に見ていくので、ここまでで O(M\log{M}) かかります。要素の追加と削除ですが、set 型の union() や difference() を使用すると、結合させる集合どうしの大きさに比例して計算量が大きくなり、 O(MN\log{M}) となって間に合いません。

追加と削除の要素は高々ポーンの数しか出てこないことを考えると、直接要素を add、remove したほうが高速でした（具体的な計算量はわかりませんでした）。

E 問題 提出コード

def main():
    N, M = map(int, input().split())
    dots = dict()
    for _ in range(M):
        X, Y = map(int, input().split())
        if X not in dots: dots[X] = set([])
        dots[X].add(Y)

    X = list(dots.keys())
    X.sort()
    status = set([N])
    for x in X:
        yset = dots[x]
        able = set([])
        stop = set([])
        for y in yset:
            if y-1 in status or y+1 in status and y not in status: able.add(y)
            if y in status and y-1 not in status and y+1 not in status: stop.add(y)
        for a in able:
            status.add(a)
        for s in stop:
            status.remove(s)
    ans = len(status)
    print(ans)


if __name__ == "__main__":
    main()

ARC121 参加記録

AtCoder コンテスト参加記録
  • コンテストから時間あけてしまいました。
  • 1完 95分でした

A - 2nd Greatest Distance

40分ごろに提出できそうでしたが、だいぶ遅かったため B問題を解いたタイミングで出すようにしました。(失敗しましたが...)

N 個の点があり、点 i, j の距離が \max{(|x_{i} - x_{j}|, |y_{i} - y_{j}|)} で定められています。 距離の定義から、 x 軸方向と y 軸方向別々に見ても良さそうですね。それぞれでもっとも遠いところから2番目を考えます。

気になるパターンは、 x 軸と y 軸を別々に比べたときに、実は同じ頂点を見ていた、という場合です。 x 軸で調べた値と y 軸で調べた値を並べてしまうとこのようなことが起こります。 場合分けを考え始めると煩雑になるため、間違いなく二番目の頂点が含まれている部分まで候補の点を出し、その中で全探索します。

x 軸で考えます。もっとも遠いのは左端の頂点と右端の頂点をとってきた場合です。その次に短いのは、右端の代わりにその一つ手前の頂点を取ること、左端の代わりに次の頂点をとることになります。従って、候補はこの時点で三つ出てきます。

y 軸も同様に考えたとき、頂点を集合で管理すれば、最小三つ、最大六つになります。この中で定義通りの距離を求めて二番目を求めればOKです。

B - RGB Matching

この問題の教訓は、Counter 使う前に sort しろ、です。もったいない。。

R, G, B の各色について、それぞれ同色が2つずつペアにできれば不満度は 0 です。つまり、各色の個体数が偶数なら 0 です。

次に、そうでない場合というのは、偶数、奇数、奇数のパターンしかありません。合計が偶数になるためです。従って、色によらずこの一つのパターンだけ考えればOKです。以下では、R(偶数)、G(奇数)、B(奇数)とします。

このとき、ペアにならない犬について不満度が小さくなるような組み合わせを見つけます。以下の2つの場合が考えられます。

  • GのあまりとBのあまりをくっつける
  • GのあまりとR、BのあまりとR をくっつける

あらかじめ、R、G、Bにおいて、どの値が何個あるかを数えておきます。例えば G の不満度の値を固定して、その値を B のとりうる不満度の列で二分探索し、もっとも差が小さくなるものを見つけます。

これを上記の2パターンでやって、小さい方が答えです。

実装では、個数のカウントに collection.Counter() を使います。 辞書型のオブジェクトで、.keys() でキーを取得できます。これに対して二分探索をするのですが、事前にソートしておけば、.keys() の値もソートされた状態で取得できます。

ABC202 参加記録

AtCoder コンテスト参加記録
  • 4完0ペナ 56分でした

A - Three Dice

サイコロの反対の値は、出た目を x とおくと、 7-x で表せます。 あとは加算して答えです。

a, b, c = map(int, input().split())
a = 7-a; b = 7-b; c = 7-c
print(a+b+c)

B - 180°

180度回転で行わないといけない操作が問題文に定義されているので、それを行います。 先に数字を変換してから逆順に出力しました。

S = input()
ans = []
for s in S:
    if s == '6':
        ans.append('9')
    elif s == '9':
        ans.append('6')
    else:
        ans.append(s)
ans.reverse()
print(''.join(ans))

C - Made Up

B_{C_j} の解釈から考えます。サンプル 1 を例にとります。

# サンプル1
3
1 2 2
3 1 2
2 3 2

Cとして 2 3 2 が与えられています。最初の値( j=1)は C_{1} = 2 です。 したがって B_{C_j} = B_{2} = 1 です。

さて、このとき A_i = 1 となる i の個数を求めます。これは単純に、数列 A の中で 1 が何個あるか先に数えておけば良さそうです。

同じ要領で j=2、すなわち B_{C_j} = B_{1} = 3 と同じになるような i の個数を数えて、... を繰り返し、全ての j について数え上げればOKです。

あらかじめ A の要素のカウントを collections.Counter で行うと良いと思います。Cの値はBのインデックスになるので、あらかじめ 1 を引いておきます。

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [x-1 for x in map(int, input().split())]

Acounter = Counter(A)
ans = 0
for c in C:
    x = B[c]
    ans += Acounter[x]
print(ans)

D - aab aba baa

まず制約で 1 \leq A, B \leq 30 とあります。a と b の並び替えで一番大きな計算は _{60}\mbox{C}_{30} ですが、python はこの計算をオーバーフローを気にせず実行できます。オーバーフローに気をつけて計算する場合は、パスカルの三角形を用いて計算しておくと良さそうです(たぶん)。

後は b の位置で数え上げを行います。例えば a の個数が 4 つ、b の個数が 3 つの場合、まずは左から見て 1 つ目の b の位置で場合分けをして、数え上げていきます。

f:id:Xenous:20210523142246p:plain
b の位置で分ける数え上げのイメージ

例えば K = 15 としたとき、11〜20 の部分に含まれるので、左の ab は確定します。次は、残りの aaabb について同様にして調べれば良いです。

f:id:Xenous:20210523145051p:plain
K = 15 のときの探索の流れ

本番では結構バグって時間がかかってしまいました。スパゲティコードになってますが一応参考までに載せておきます。

D問題 提出コード

def nCk(n:int, k:int) -> int:
    """
    nCk の値を O(n) で計算する. (n-k)! // k! の計算を行う.

        Parameters:
        -----------
        n, k: int
            nCk に該当する0以上の整数
        
        Return:
        -------
        int
            nCk の計算結果.
            n または k が 0 より小さい場合は 0 を返す.
            n が k より小さい場合も 0 を返す.
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    k = min(k, n-k)
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
    denom = 1
    for i in range(k, 1, -1):
        denom *= i
    return numer // denom


def main():
    A, B, K = map(int, input().split())
    if K == 1:
        ans = 'a'*A + 'b'*B
        print(ans)
        return

    cnt = 0; Acnt = A; Bcnt = B
    ans = ''
    # K がどこにあるか探索する
    while True:
        for i in range(0, Acnt+1):
            # b の位置を固定したときの場合の数
            res = nCk(i+(Bcnt-1), min(i, Bcnt-1))
            if res == 0:
                # a または b の数が 0 になったら脱出
                break
            if cnt < K <= cnt+res:
                break
            cnt += res
        if res == 0:
            # a または b の数が 0 になったら、後ろに残りの a の数分くっつけるだけ
            ans += 'a'*Acnt
            break
        # 確定した部分を入れる
        ans += 'a'*(Acnt - i) + 'b'*(Bcnt > 0)
        Acnt = i
        if Bcnt > 0: Bcnt -= 1
        if Bcnt == 0 and Acnt == 0:
            break
    print(ans)


if __name__ == "__main__":
    main()

E - Count Descendants

解説ACです。本番では二重の辞書(dict 型の value に dict を持つ)で、DFSで戻ってくる際に、各頂点の「深さ」と「頂点番号」を集合管理することでクエリに答えようとしましたが、マージする際に木の情報を上書きしてしまい、うまくいきませんでした。

解説にあるように、DFS で巡った順に番号を振っていくと、かなり見通しが良くなります。 以下は例です。

f:id:Xenous:20210525125825p:plain
頂点に初めて訪れたとき(青色)と、最後にその頂点から出ていくとき(赤色)の時刻

深さごとに、それぞれ入りの時刻を保持しておくと、以下のように整理できます。 ここで例えば「頂点 2 を含む長さ 2 のパスが作れる頂点の個数」を考えたとき、depth が 2 の行において、頂点 2 の入った時刻と出た時刻の間にある要素の個数を見ると、それが頂点 2 を通る長さ 2 のパスになっていることがわかります。

f:id:Xenous:20210525131710p:plain
深さごとに入りの時刻を整理した図

この頂点の探索を二分探索で行えば、各クエリに O(\log{N}) で応答できるので、最終的には O(N + Q\log{N}) で十分間に合います。

今回の番号の振り方は下記でも練習できます。

AtCoder 水色になりました

振り返り

AtCoder 水色になりました。

f:id:Xenous:20210522105951p:plain

ということで、簡単に振り返りで、モチベーションについてと、精進してきたことを書き残しておきます。 精進部分については緑や水色を目指す方の参考になれば幸いです。

まずは簡単な自己紹介です。

  • 社会人です。
  • 修士卒です。一応数学科にいて、途中から統計学の方へシフトしました。
  • SIer です。業務でコードは書いてません。
  • AtCoder 初参戦は2019/11 本格参加は2020/03 です。
  • PAST は第3回、第5回ともに中級です。

モチベーションについて

色々な方が竸プロのモチベーションについて書いていたりしますが、私の場合はレートです。完全にオンラインゲーム感覚です。 昔から結構オンラインゲームにハマっていて、そのゲームでのウデマエ(=レート)を上げるのが楽しいんですよね。竸プロの場合、ウデマエはアルゴリズムの理解と応用力でしょうか。一目見て解法が思い浮かぶ人は本当にすごいと思います。

直大さんのブログでの色の説明や、E8さんの記事を見るとおおよそ水色が竸プロerにおいては中級者なのかなと思い、2020年中に水色を目指してプレイしてました。5ヶ月ほど遅れてしまいましたが、水色になることは達成できました。

精進方法について

今までにどういう方針で何をやったかを前半で、問題を解くときにやっていたことを後半で記載します.

どういう方針で何をやったか

目標の色レート帯になるには、なりたい色のパフォーマンス値を取る必要があります。パフォーマンスはコンテストの出来で決まりますが、「自分と同じレート帯が解ける問題を早く解くこと」、または「自分と同じレート帯の人が解けない問題を解くこと」で高い値を得ることができます。

よって、精進の方針として、「見た瞬間わかる」くらいになること(数の暗黙知？)と、「自分にとって難しいと思える問題を解けること」の二軸で進めることにしました。

さて、水色を目標としたときに、水色においての基礎知識を E8 さんがまとめた記事があります。精選100問です。こんな素晴らしくまとめてくださった記事を使わない手はないと思い、最初はこれに取り組み始めました。

しかし、DPは全く理解できず、、自分にとってわかりやすそうなものと出題頻度をみて、優先順位を決め、精選100問のうち以下の内容を先に取り組みました。

  • 全探索、二分探索、bit全探索、DFS、BFS、ダイクストラ
  • DP超基礎編のみ
  • UnionFind、累積和、いもす法
  • 試し割り法による素因数分解、約数列挙
  • 高速な組み合わせ nCk の計算

また、上記がわかったつもりでもコンテスト中気づけなかったり、解ききれないことも多く、そもそも竸プロの問題に慣れる必要があると思いました。そこで、AtCoder Problems の bootcamp を使います。 Atcoder Problems では、Beginner 向けに bootcamp 300問が用意されてます。これの easy 2 問、medium 2問、hard 2問の計6問のバチャを作ってやってました。

これらを解き切った頃には緑色に到達し、レートも1000越えしていたと思います。ちょうど2020年の11月ごろで、半年間はかかってます。 その後はだいぶ問題に慣れたので、精選100問の中級編の余りと、上級編でコンテストによく出てくるものを一旦さらっておくようにしました。以下が取り組んだ内容です。

  • DP(ナップザックDP、区間DP、bitDP、LIS)
  • ワーシャルフロイド法
  • 最小全域木の構成法(クラスカル法)
  • 座標圧縮
  • 半分全列挙
  • 平方分割
  • Binary Index Tree
  • セグメント木
  • 遅延評価セグメント木

他に、コンテスト中に知っておく必要があるなと思って調べたことです。

  • エラトステネスの篩
  • 桁DP
  • 確率DP、期待値DP

セグメント木などは、自分で実装してみたりしたものの、使えるようにするだけで一週間くらいかかってました。 これらを履修した後でも相変わらず緑でした。おそらく周りの方々も精進し続けて、全体のレベルが上がっているのでしょう（そう思いたい）。

上記全て取り組み終わったのがちょうど2021年2月くらいです。それ以降は水・青diffを時間が取れそうな日に取り組んでいましたが、コンテストでDPがまだ解けていなかったため、あんまりやりたくなかった Educational DP Contest に取り組みます。

現状まだ取り組み途中ですが、ちょうどABC201のD問題が水diffのDPの問題で、このおかげ？で色変することができました。 引き続き EDPC に取り組み、そのあとは上級編の残り、典型90問 と ACL に取り組もうかと思ってます。

ここまで、やったことをまとめるとこんな感じです。

  • (灰~茶 のとき) 2020/03 ~ 2020/05: 精選100問 中級編 （全探索、DFS/BFS、累積和、unionfindあたり）
  • (茶~緑 のとき) 2020/05 ~ 2020/11: AtCoder Problems Bootcamp for Beginner 300問
  • (緑後半のとき) 2020/11 ~ 2021/02: 精選100問 中級編のこり、上級編一部
  • (最近) 2021/03 ~ 2021/05: 水青埋め、EDPC

問題を解くときにやっていたこと

よく議論になる点について私の考えを書いておきます。

  • 解説をどのタイミングで見るか？

解説を見る前に10〜30分は自分の頭で解法を考え、計算量を見積もって、イケそうなら実装するまでやったほうがいいと思います。そうするほうが記憶に残りやすいのと、「自分の考えた解法がなぜダメなのか」を考えることができます。これは間違った解き方において反例を出す能力が向上すると思います。

解説をさっさとみたほうが効率的な気もしますが、結果的に記憶に残る方を選んでやれば良いと思ってます。

  • Streak を切らさないほうがいいのか？

一時期 Streak を切らさないようにしていましたが、切らさないようにABCのA問題を解くなどした時期もあり、いい面も悪い面もあるかなと思います。

難しい問題に取り組んで Streak を繋げようとすると、一日で解けない場合や、WAが出て焦ったりして精神衛生上良くないことが私にはあったので、コントロールが難しいですね。

問題を解く週間をつけたいとか、問題に触れる時間がなくなってしまった時に、無理矢理時間を作る意味で取り組むのがいいかなと思ってます。

終わりに

振り返りで色変記事を書いてきました。他の方の精進の参考になれば嬉しいです。 これからもウデマエを上げて、青を目指していきたいと思います！

ABC201 参加記録

AtCoder コンテスト参加記録
  • 4完2ペナ 80分でした

A - Tiny Arithmetic Sequence

数列は増加列でも減少列でも良いので、ソートして差分が等しければ作れると判断できます。

B - Do you know the second highest mountain?

python では、列を指定してソートできるので、それを使います。 list.sort(key=lambda x: x[1], reverse=True) で書けます。

N = int(input())
l = []
for _ in range(N):
    S, T = input()[:-1].split()
    T = int(T)
    l.append((S, T))

l.sort(key=lambda x: x[1], reverse=True)
print(l[1][0])

C - Secret Number

全探索のやり方が思い浮かばなかったのは反省です。。 本番では、丸の数が 5 個以上の場合は答え 0 、4個のときは、3個のときは、...とそれぞれで場合の数を求めて加算しました。 使う数字の種類で並び替えの計算が変わるので、それぞれで計算する方針です。これは(工夫次第で短くはなると思いますが)実装の時間が取られますね。。

全探索の方針は、0000〜9999 を順に調べて、全ての o が含まれているかどうかチェックする方針です。 こちらの方が考え方も実装もシンプルです。

D - Game in Momotetsu World

このような勝ち負けのゲームでは後ろから考えていくのがセオリーのようです。それに従って、右下のマスから左上に戻るように探索します。

各マスで、 (高橋くんの得点) - (青木くんの得点) を考えます。高橋くんは、この値を最大化するように動こうとし、青木くんはこれを最小化するように動こうとします。便宜上、この値をスコアと呼びます。

高橋くんが移動可能なマスと青木くんが移動可能なマスは固定されているので、分けて考えてしまいます。高橋くんは位置 h と w の偶奇が異なるマスに移動可能で、青木くんは偶奇が一致しているマスに移動できます。

高橋くんが移動可能なマスでは、スコアは最小化の更新を行います。青木くんが移動可能なマスでは最大化の更新です。高橋くんは自分が移動できるマスのスコアのうち高い方を選んで移動し、青木くんは自分が移動できるマスのスコアのうち小さい方を選んで移動します。

最終的に、最初の左上のマスから、高橋くんの移動可能なマスのスコアの最大値を見て勝ち負けを判断することができます。

回答コード

import sys

input = sys.stdin.readline
dig = [(-1, 0), (0, -1)]

H, W = map(int, input().split())
field = []
for _ in range(H):
    tmp = list(input()[:-1])
    field.append(tmp)
field[0][0] = '*'

if H == 1 and W == 1:
    print('Draw')
    return

check = [[float('inf')] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i%2 == j%2: check[i][j] = -float('inf')

if (H-1)%2 == (W-1)%2: check[H-1][W-1] = -1 if field[H-1][W-1] == '+' else 1
else: check[H-1][W-1] = 1 if field[H-1][W-1] == '+' else -1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        base = check[h][w]
        for dh, dw in dig:
            i = h + dh
            j = w + dw
            if not (0 <= i < H and 0 <= j < W):
                continue
            tmp = field[i][j]
            if i%2 == j%2: check[i][j] = max(check[i][j], base - (tmp == '+') + (tmp == '-'))
            else: check[i][j] = min(check[i][j], base + (tmp == '+') - (tmp == '-'))

res = check[0][0]
if H > 1: res = max(check[1][0], res)
if W > 1: res = max(check[0][1], res)

if res > 0:
    ans = 'Takahashi'
elif res < 0:
    ans = 'Aoki'
else:
    ans = 'Draw'
print(ans)

ARC118 参加記録

AtCoder コンテスト参加記録
  • ACの2完0ペナ 79分でした

A - Tax Included Price

最初からなかなかハードな問題だと思いました。

式から O(1) で求められそうな感じはしますが、わからなかったので実験しました。具体的には、実際に消費税 t を固定して 1 円から順番に求めていき、スキップされたもの(税込み価格としては現れない正の整数の金額)を取りだして並べていきました。

そのあと、スキップされた値の差分を隣どうしとって行きます。そうすることで差分の周期性が見えてきます。 実験から、以下のような動きをしていることがわかりました。

  • t が 100 の約数であるときは、差分の周期は 1 で全て値は同じになる。
  • そうでないときは、差分のループは長さ t の数列で表せる。

これらから、 N を ループの長さ t で割ったときの商と余りを駆使して、 N 番目の数字を O(1) で計算することができます。

B - Village of M People

まず a を 数列 A の各要素として、 \frac{Ma}{N} を求めます。このとき、小数ではなく整数で扱いたいので、商を B として扱い、余りの列を別で持っておきます。

数列 B はこの時点では \sum{B} = M を満たしていませんが、足りない部分を割り振ることによって数列 B を完成させます。 先ほど求めた余りの列の大きい順から割り振れば良くなります。余りは切り捨てたときの整数との距離のような値と解釈でき、余りが小さければ今 B として決めた値に近く、そうでないときは +1 した値の方が近くなります。

C - Coprime Set

以下の2つが成り立つような数列 A を作ります。

  • 全ての i, j で、 i \neq j ならば A_i \neq A_j かつ \mbox{gcd}(A_i, A_j) \gt 1 が成り立つ ・・・①
  • \mbox{gcd}(A_1, \cdots, A_N) = 1 が成り立つ・・・②

まず A_i に素数をもってくることができません。素数があれば ② を成り立たせるように作るのは簡単になりそうですが、①を成立させるには全てその素数の倍数でないといけません。そうすると結局②を成立させることができず、作れません。

また、4 などの 1種類の素数で構成された数字も使えません。これも、①を成立させるにはその一種類の素数の倍数である必要があり、②を満たせません。

そうしたときに、まず N = 3 で考えてみます。素数を使うことはできませんが、ふたつの異なる素数の掛け算で構成された値を使ってみるのはどうでしょうか。例えば、小さい順に、6, 10, 15 を考えてみると、それぞれ①②を満たします。

そして、これら 2\times3, 2\times5, 3\times5 のどれかの倍数であれば、①②を満たしつつ数列を追加することができます。 追加する際に 10000 より大きくならないことに注意すれば、この問題を解くことができます。

ZONeエナジー プログラミングコンテスト “HELLO SPACE” 参加記録

AtCoder コンテスト参加記録
  • A, B, D の3完0ペナ 40分でした

A - UFO襲来

長さが 12 で固定のため、単純に調べれば OK です。

S = input(); cnt = 0
for i in range(len(S)):
    cnt += S[i:i+4] == 'ZONe'
print(cnt)

B - 友好の印

本番では切片の二分探索で解きました。 今考えてみると、各障害物の座標それぞれについて、その座標と UFO の座標を通る直線の式を求めて、一番高い切片となったものが答えで良いですね。

C - MAD TEAM

解説ACです。本番では O(N^{2}) 解法でやってみましたが TLE でした。 能力値の最大を持っている人をそれぞれ固定して残りを全探索する方針でしたが、これは嘘解法ですね。。そうでない場合も普通に作れそうです。

竸プロ典型90問でも、最大値の最小化は二分探索、というものがありますが、応用できませんでした。これを使って 0 1 にする発想は覚えておきたいです。

実装は、答えの値を二分探索で決め打ちして、各メンバーの能力がそれ以上かそうでないかを 1 0 で表現して圧縮し、3つ選んだときの組み合わせを探索する方針です。

ここで、5桁の bit で考えて実装するのがやりやすいかと思います。例えば、ある人の能力がそれぞれ [6, 7, 3, 1, 10] として、6 以上かどうかで 1 0 を振ることを考えたとき、これを 5桁 の bit で見て、11001 (10進数だと25) とします。

あとは、3つの組み合わせの探索で bit の OR 演算を行い、結果 11111 になれば、二分探索で決め打ちした値は答えになり得ます。

(参考)提出コード

from itertools import combinations
import sys

input = sys.stdin.readline


def ORlist(l:list) -> int:
    res = 0
    for k in l: res = res | k
    return res


def main():
    N = int(input())
    energy = []
    for _ in range(N):
        A, B, C, D, E = map(int, input().split())
        energy.append((A, B, C, D, E))
    
    R = 10**9 + 1 # right side
    L = 1   # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        energyset = set([])
        for ener in energy:
            A, B, C, D, E = ener
            s = 2**4*(A >= mid) + 2**3*(B >= mid) + 2**2*(C >= mid) + 2**1*(D >= mid) + 2**0*(E >= mid)
            energyset.add(s)
        energylist = list(energyset)
        flag = False
        for iters in combinations(energylist, min(3, len(energylist))):
            res = ORlist(list(iters))
            if res == 2**5-1:
                flag = True
                break
        if flag: L = mid # True
        else: R = mid # False
    print(L)


if __name__ == "__main__":
    main()

D - 宇宙人からのメッセージ

ABC199 の C問題と発想は同じです。

操作が二種類あり、そのうち「末尾に加える」は O(1) でできるので良いのですが、「反転させる」操作は O(|S|) かかる操作なので、実際に反転させる処理を書くと TLE になると思います。

したがって、「反転させる」が起こったら、挿入位置の方を反転させて、「先頭に加える」ようにします。末尾にも先頭にも O(1) で追加したいので、collections.deque を使います。

反転しているかどうかは flag で管理しました。

また、問題文では最後に同じ文字が2文字連続したら取り除く操作をしていますが、この操作は挿入した段階で消しても変わりません。むしろ挿入段階でやった方が abba など対応しにくい形も気にせず取り除けるので、挿入段階で消してしまいます。

提出コード

from collections import deque


def main():
    S = input()
    flag = False
    ans = deque([])
    for s in S:
        if s == 'R':
            if flag: flag = False
            else: flag = True
        else:
            if flag: # 反転しているとき
                ans.appendleft(s)
                if len(ans) >= 2:
                    if ans[0] == ans[1]:
                        ans.popleft()
                        ans.popleft()
            else:
                ans.append(s)
                if len(ans) >= 2:
                    if ans[-1] == ans[-2]:
                        ans.pop()
                        ans.pop()
    if flag:
        ans.reverse()
    print(''.join(ans))


if __name__ == "__main__":
    main()

E - 潜入

後日ときます。