【競プロ精進ログ】【2021/03/21】ABC196: C ARC115: A, C

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC196: C – Doubled
ARC115: A – Two Choices
ARC115: C – ℕ Coloring
まとめ

ABC196: C – Doubled

ABC196 より、ABC196: C – Doubledを解きました。
難易度は灰色。

コンテスト中は普通に解けなくて時間をだいぶ溶かしました。
最近上達してきたと思っていたのですが、久々に灰Diffを落とし、まだまだ勉強不足なことを実感しました。

解法としては、繰り返しなので前半の最大値(1000000)までの数を全探索して、文字列連結させたものが答えになります。

コンテスト中はもっと複雑なコード書いて全然通らないのを繰り返してました。
実際に探索が必要な部分のみを抜き出して全探索というのは考えたのですが、この解法は思いつかなかったです。

提出コードはこちら(回答まんまです)。

N = int(input())
for i in range(1, 1000001):
    if int(str(i) * 2) > N:
        print(i - 1)
        exit()

ARC115: A – Two Choices

ARC115 より、ARC115: A – Two Choicesを解きました。
{% comment %} 難易度は緑色。 {% endcomment %}

ARCのA問題でした。
S(i, j)の組み合わせで、同じ問題に対して異なる選択をしている個数が奇数の場合のみ、正解数が同じにならない場合であることはすぐわかったのですが、O(N^2)のアルゴリズムしか思いつきませんでした。

一時間くらいねばったところで、一人目とそれ以外の回答の比較をすれば、以降は偶数か奇数の比較をしていくだけでいいことに気づきAC。

提出コードはこちら。

N, M = map(int,input().split())
S = [-100]
ans = 0

for i in range(N):
    S.append(input())

# for i in range(1, N):
si = S[1]
T = []
a = 0
o = 0
for j in range(2, N+1):
    sj = S[j]
    count = 0

    for m in range(M):
        if si[m] != sj[m]:
            count += 1

    if count % 2 == 1:
        o += 1
        ans += 1

    else:
        a += 1

    T.append(count)

for t in T:
    if t % 2 == 0:
        ans += o
        a -= 1
    else:
        ans += a
        o -= 1

print(ans)

ARC115: C – ℕ Coloring

ARC115 より、 ARC115: C – ℕ Coloringを解きました。

かなり簡単に感じましたが、もしかして正攻法じゃなかったかな？と。
1から順に最小値を記録していき、最小値を持っている値の倍数に出会ったら最小値を加算していくことを繰り返し、O(N)で解くことができました。

提出コードはこちら。

N = int(input())

ans = ["1"]
min = 1
minpos = 1
for i in range(2, N+1):
    if i % minpos == 0:
        min += 1
        minpos = i
        
    ans.append(str(min))

print(" ".join(ans))