Study

AtCorder252

  /

AtCorder 252に参加しました。

参加4回目。A, B, Cの3完でした。

Cが終わった時点で、時間は残り45分ぐらいで、じっくりと時間を掛けてDに取り組んだのですが、解けませんでした。解けそうなのに、WAがいくつか混じって解けないという、悔しい思いました。しっかりと復習して行きたいと思います。

参考にする回答はこちら。
https://qiita.com/u2dayo/items/4fda81db708aa4fdb488

Contents
  1. [A] ASCII code
  2. [B] Takahashi’s Failure
  3. [C] Slot Strategy
  4. [D] Distinct Trio
  5. まとめ

[A] ASCII code

提出したコードはこちら

n = int(input())
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
print(ascii_lowercase[n-97])

a-zの配列をググってコピーして、inputのintから97を引いたindexでアクセするというアプローチをしました。

回答を見てびっくり。chr(N)と書くだけでよかったんですね。

Unicode文字コード <--> 文字 の変換関数(chr / ord)の存在は知りませんでした。競プロぐらいでしか出番はなさそうな気がしますが、覚えておくことにします。

[B] Takahashi’s Failure

提出したコードはこちら

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

a_max = max(a_list)

def solution():
    for b in b_list:
        if a_list[b-1] == a_max:
            print("Yes")
            return
    print("No")

solution()

ほぼ回答と同じコード。考え方も同じで問題なし。

[C] Slot Strategy

提出したコードはこちら

import math

n = int(input())
s_list = [str(input()) for _ in range(n)]


def calc(used_t_count: list):
    # used_countからtotal時間を計算していく。
    # print(used_t_count)
    total_t = 0
    for i, v in enumerate(used_t_count):
        if v == 0:
            continue
        else:
            used_t = (i * 1) + (10 * (v - 1))
            total_t = max(total_t, used_t)
    return total_t

ans = math.inf
for i in range(10):  # iを表示して止まる時間
    used_t_count = [0] * 10  # 行動済みのtの回数
    total_t = 0
    for s in s_list:
        t = s.index(str(i))
        used_t_count[t] += 1
    # print(used_t_count)
    total_t=calc(used_t_count)
    ans = min(ans, total_t)

print(ans)

かなり時間がかかってしまいました。

まず最初は問題の意味がよくわかりませんでした。例題を何回も紙に書きながら読み返して、やっと意味がわかりました。問題の意味がわかったあとも、回答であーでもない、こーでもないと四苦八苦しました。

解法自体は、脳死でとりあえず全探索をトライ。計算量はO(10100X)に成りそうなので、いけそうな気はしてました。

コードの提出自体は1回でクリアできましたが、少し長ったらしいコードになってしまいました。もっとスマートな解法があるだろうなと思ってはいたんですが、クリアしたので次に行きました。

コードの綺麗さに違いはありますが、解説を見る限り考え方自体はあっていそうです。この手のタイプの問題は、シミュレーションというそうですね。それは知りませんでした。

[D] Distinct Trio

じっくりと時間かけましたが、最後までクリアできず。入力例3すら、正当になりませんでした。

全探索だと明らかに無理だということはわかって、数学的なアプローチをずっと考えていました。組み合わせの公式とかを思い出しながらやっていました。

数学の知識が圧倒的に足りないので、このまま競プロをやるなら中学の算数ぐらいは一度、やり直した方が良いかもと思い始めています。

組み合わせの関数combの存在はしらなくて、ネットでググった以下を使っていました。

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

回答を見ると、リストから全組み合わせを出して、数字が同じ場合の数を引くことで答えを出していますね。私は、最初にlistをsetに変換してから組み合わせを出し、その上で数字が重複するバターン数を加算していく方法でアプローチしたのですが、正解に辿り着けませんでした。

最近、listをsetに変換して上手くいくパターンの問題を知ってしまったので、その考えに最後まで引きづられてしまいました。

もっと問題の数をこなして、いろいろなパターンに対応できる様になりたいと思いました。

まとめ

前回に引き続き、A,B,Cの3完でした。このままだと良くて茶色止まりになりそうです。

最近は本業が忙しくてアルゴリズムの勉強がなかなかできないのですが、次回に向けて少しでもできることを増やしておきたいと思う今日この頃です。

RELATED POST