Study

AtCoder249

先週末、AtCorderに初参戦しました。

結果は、A, Bの2問しか解けず😱 正直、ショックでした。

私の中では将来的には水色までたどり着く予定なのですが、先が見えなさすぎて、ちょっと絶望しています。

が、やれるとこまでは、やっていくつもりです。
というわけで、参加した AtCoder249の振り返りをしていきます。

参考にする解法はこちら
https://qiita.com/u2dayo/items/5565bf5e526ab3c6f7dc

A問題

難しかったです。最初、解けなくて焦りました。紙とペンを取り出して、なんとか解くことができました。

提出したコードはこちら

a, b, c, d, e, f, x = map(int, input().split())

t_x = 0
a_x = 0

t_v = x // (a + c)
t_r = x % (a + c)
a_v = x // (d + f)
a_r = x % (d + f)

# takahashi
t_x = b * t_v * a
if t_r <= a:  # 最後休憩なし
    t_x += b * t_r
else:  # 最後休憩あり
    t_x += b * a


# aoki
a_x = e * a_v * d
if a_r <= e:  # 最後休憩なし
    a_x += e * a_r
else:  # 最後休憩あり
    a_x += e * d

if t_x > a_x:
    print('Takahashi')
elif a_x > t_x:
    print('Aoki')
else:
    print('Draw')

参考サイトによると、歴代A問題の中でも難しい問題とのことです。正答率も全レートでB問題より低いです。やはり難しい問題だったんですね。

解法は1秒ずつシミュレートしていくパターンと、歩き+休憩を1サイクルとする算数方式があります。私の解法は後者の算数方式だったらしく、考え方は間違っていなかったようです。

変数の付け方がわかりずらいですね。t_x, a_xはt_dist, a_distと、t_v, a_vはt_cicle, a_cicleとでもするべきでした。

あと最終サイクルの距離を足すところは

if t_r <= a:  # 最後休憩なし
    t_x += b * t_r
else:  # 最後休憩あり
    t_x += b * a

と書きましたが

t_x += b * min(t_r, a)

とシンプルに書くことができました。

B問題

提出した解法はこちら

S = input()


def solution(S):
    exists_str = []
    for s in S:
        if s in S:
            if s in exists_str:
                print('No')
                return
            else:
                exists_str.append(s)

    if S.islower() or S.isupper():
        print('No')
    else:
        print('Yes')


solution(S)

全探索で問題なしと思ったのですが、スマートにやる方法がありました。

すべての文字が異なるならば、『文字列 S に現れる文字の種類数』と『文字列Sの長さ』は等しいです。

このことには回答を見るまで、気づきませんでした。

C問題

手も足も出ず・・・ 最初は問題文の意味すらよく分かりませんでした

文字列の選び方は 2**N 通り

まずこれが解説を読んでも分かりませんでした。数学の公式かなんかでしょうか? ググってもよくわかりませんでした・・・ 確かに、N=3ぐらいで確認するとその通りなので、とりあえず暗記しておくことにします。

で、これが分かったところで、やっぱりどうやって解けばいいのかわからず。bit探索って何ですか状態です。

以下をストックしたので、勉強しておきます。
こわくないbit全探索1 入門編: bit全探索ってなに?【競プロ解説

D問題

問題の内容自体は、Cよりも理解しやすかったです。ただ解けるかどうかは別の話・・・

ダメ元で以下の全探索を提出してみましたが、当然TLE。で、解法はわからずでした。

n = int(input())
an: list = [int(x) for x in input().split()]

result = 0
for i in range(n):
    for j in range(n):
        if an[i] % an[j] != 0:
            continue
        else:
            ak = an[i] // an[j]
            result += an.count(ak)

print(result)

解法は2種類あるようです。解法の仕組み自体はなんとなく理解できるのですが、計算量の話はちんぷんかんぷん・・・

計算量の考え方、そのものを勉強する必要がありそうです。logって何でしたっけって感じなので。

E問題以降

未着手

C、Dをある程度できるようになったら挑戦します。

まとめ

初参戦ですが、A,Bしかできないという悲惨なできでした。茶色すら遠そうですが、地道にやっていくことにします。