AtCoder Beginner Contest 258 A 問題から C 問題の解説(Python3)

rute
2022/07/11 08:24

こんにちは。こんばんは。Rute(リュート)です。
先日、AtCoder Beginner Contest 258 の問題を解きました。

この記事では主に、AtCoder Beginner Contest 258 の A問題から C問題までの解説を行いたいと思います。
各問題の回答ソースコード例はPython3(3.8.2)です。

A問題「When?」

問題

解法

Kの値は100以下であるので、K分後の時間は21時か22時であることが分かります。
Kの値が59以下の時、K分後の時間は21時K分となります。
Kの値が60以上100以下の時、K分後の時間は22時(K - 60)分となります。
あとは、これによって求めた時間をHH:MMの形式で出力すれば良いです。
K = 3, K = 68などの場合、分の時間が10分未満になるので、
zfill等の関数を使って、2桁にすることに注意しましょう。

または、Kを60で割った商をH, Kを60で割ったあまりをMとして、
Hに21を足すことによって、K分後の時間であるH時M分を求める事も可能です。

以下、ソースコード例です。

K = int(input())
  if K &lt;= 59:
    S = str(K).zfill(2)
    print("21:"+S)
  else:
    S = str(K % 60).zfill(2)
    print("22:"+S)

B問題「Number Box」

問題

解法

Nの値は高々10以下であるので、マス目の数はN²に比例するものになることから100マスくらいが最大のマス目の数であると分かります。

あとは、上下左右と斜めの8方向に対してシミュレーションを行い、並べた整数の最大値を計算すればよいです。

計算量は、N²のマス目に対して8通りのN - 1 回の移動をシミュレーションするので、
O(N³)となります。制約では十分高速に動作します。

ソースコード例は長いので、以下のURLよりご確認下さい。
ソースコード例

C問題「Rotation」

問題

解法

「Sの末尾の文字を削除し、先頭に挿入する」という操作は両端キューというデータ構造で行うことができそうです。
しかし、x は N 以下までという制約があるため、仮に "1 N"というクエリがQ回北場合、O(NQ)の計算量が必要となり、実行時間制限の時間では実行することができません。

ここでは、文字列の位置に着目します。
「Sの末尾の文字を削除し、先頭に挿入する」ということと、
「Sの末尾以外の文字の座標を1つずつ右に移動する」ということは実は同じです。

入力例1では、まず"2 2"というクエリが与えられているため、2文字目の"b"を出力します。
その後、"1 1"というクエリが与えられます。
末尾の文字を削除して先頭に挿入すると "abc" → "cab"となります。先頭の文字だった"a"は2文字目に、2文字目だった"b"は3文字目に、"c"は1文字目に移ります。

入力例には与えられていませんが、"cab"の状態で"1 2"というクエリが与えられた場合は、"abc"となり、それぞれの文字の位置が2つ右に移動しています。

よって、両端キューなどで愚直にx回操作を行わなくとも、文字の座標を制御することは可能であり、k(0≦k≦N-1)文字目の文字の位置は、
"1 x"のクエリで与えられるxの総和をΣxとして、 (k + Σx)をNで割ったあまりとなります。

計算量は文字列の入力でO(N)、クエリ処理でO(Q)となるためO(N+Q)です。

以下、ソースコード例です。

N,Q = map(int,input().split())
S = input()
now = 0
#nowは右にずらす文字の数
for x in range(Q):
    t,x = map(int,input().split())
    if t == 1:
        now += x
        #Nを超えたらNで割ったあまりにする
        now %= N
    else:
        文字列は、0-indexedなのでx-1をしてから
        print(S[((x-1)-now)%N])