ABC354参加後振り返り

2024年5月19日 19:56

前書き

2024/3からAtCoderを始めました。
現職は、2年目の新人インフラSEです。
業務中では、実際に手を動かすとなると時間がかかるという場面が多く、
AtCoderを通して高パフォーマンスを出せるように実装力を磨きます。
使用言語はPython3です。

ABC 354 振り返り

全体を通しての感想

今回はA, B, Cの3完でした。
A問題・B問題で添え字ガチャ的な立ち回りをしてしまったり、
D問題では、慌ててしまって剰余類の個数を数えるだけの実装で30分以上溶かして時間内に解けずに悔しく、未熟さを感じました。落ち着け。。。
やはり、実装力（とプレッシャーへの弱さ）が私の課題なので、
今後も続けて地力を上げていきます。

D問題まで時間内に間に合っていれば4桁パフォーマンスが出たかと思うとちょっと勿体なくて悔しいですが、highestを取れていたことは素直にうれしいです。

A問題 - Exponential Plant

問題
A - Exponential Plant (atcoder.jp)

答案①（AC）
毎夜$${2^i}$$ cm 成長する植物は、発芽したときの高さを0 cmとすると、$${k}$$日目の朝の時点では$${\displaystyle\sum_{i=0}^{k-1} 2^i}$$ cm となっています。$${ \displaystyle\sum_{i=0}^{k-1} 2^i = 2^{k}-1 }$$なので、これと$${H}$$を比較して$${H}$$より大きくなるような最小の$${k}$$を下から順に探索すれば答えが求まります。（約4分）

#input
H=int(input())

#process
ans = 0
while True:
    if 2**(ans)-1 > H:
        break
    else:
        ans += 1

#output
print(ans)

B問題 - AtCoder Janken 2

問題
B - AtCoder Janken 2

答案①（AC）
辞書順に整列された名前のリスト$${\tilde S}$$とレートの総和$${T = \sum C}$$に対して、$${\tilde S_{T\mod N}}$$が答えとなります。

解いている最中では、「片方だけ型変換する入力の取得」と「tupleを要素に持つリストの並べ替え」の実装で戸惑いました。
（※ただ、答案②で示すように、これらの実装は問題を解くうえで必須な要素ではありません。）
「片方だけ型変換する入力の取得」は、一度input().split()で取得した文字列のリストの中身を一時的に格納する変数ts, tcを用いて(ts, int(tc))を入力する実装で乗り切りました。
また、並べ替えについては、keyで射影をとるlambda関数を指定することでtupleのリスト全体をtupleのある成分についてソートするときの順序で並べ替えることができるので、これを用いてユーザー名（とレートの組）の辞書順のリストを実装しました。
コンテストでは以下のコードを提出しました。（約20分）
（入力と番号を計算するためのロジックが同じループ内に混ざってて汚い。。。）

N = int(input())

SC = [('',0)]*N
temp = 0

for i in range(N):
    ts, tc =  input().split()
    SC[i] = ts, int(tc)
    temp += int(tc)

#process
sorted_SC = sorted(SC, key=lambda x: x[0])

print(sorted_SC[temp % N][0])

答案①の清書（AC）

#input
N = int(input())

#(S_i, C_i)をi番目の要素とするようなリストSCを作成する。
#input():      "S_i C_i" ※ここでのC_iはstr型
#-> .split():  [S_i, C_i]
#-> *:         S_i, C_i
#-> lambda:    (S_i, C_i) ※ここでのC_iはint型
# これを"for i in range(N)"でN回繰り返す。
SC = [(lambda s, c: (s, int(c)))(*(input().split())) for i in range(N)]

#process
#[x[0] for x in SC] をソートするときの置換をSCに適用し、sorted_SCに格納する。
#つまり、第0成分である文字列S_iの辞書順でSCをソートした結果をsorted_SCとする。
sorted_SC = sorted(SC, key=lambda x: x[0])

#sorted_SCからCを取り出して総和をとり、mod N した番号の第0成分が答えである。
ans = sorted_SC[sum([x[1] for x in sorted_SC]) % N][0]

#output
print(ans)

答案②（AC）
辞書順に整列された名前のリスト$${S}$$と$${N = |S|}$$とレートの総和$${T = \sum C}$$があれば答えが求められるので、もっとシンプルに実装できます。

#input
N = int(input())
S = []
C = []
for i in range(N):
    ts, tc =  input().split()
    S.append(ts)
    C.append(int(tc))

#process
sorted_S = sorted(S)

ans = sorted_S[sum(C) % N]

#output
print(ans)

C問題 - AtCoder Magics

問題
C - AtCoder Magics

答案①（AC）
主な制約は$${2\leq N \leq 2\times 10^5}$$であるため、$${O(N \log N)}$$程度の処理は制限時間内で実行可能です。とくに、$${\{A_i\}}$$のソートなどが実行できるので、ソートを用いて問題を効率よく解くことができないか考えます。

議論を簡単にするため、$${\{A_i\}_{i \in I}, I := \{1,2,\cdots, N\}}$$がソート済みであることを仮定します。
このとき、操作の定義により$${N}$$番目のカードは必ず採用されます。
次に、$${N-1}$$番目のカードは$${C_{N-1}\leq C_N}$$である場合採用されます。
さらに、$${N-2}$$番目のカードは$${C_{N-2}\leq \min\{C_{N-1},C_N\}}$$である場合に採用されますが、$${\min\{C_{N-1},C_N\}}$$は直前に採用されたカードのコストであるので、逐一$${\min}$$を取らずに$${O(1)}$$で$${C_{N-k}\leq \min\{C_{N-k+1},\cdots,C_N\}}$$の比較ができます。（本問の場合、各$${C_i}$$が異なるので、比較において不等号は$${<}$$であるとしても同値になります。）
同様に繰り返して得られる$${C_i}$$の部分列を取って得られたものを$${\{C_i\}_{i\in I'}}$$とすれば、$${|I'|}$$と$${I'}$$を昇順にソートした中身が解答となります。

一般の場合、$${A_i}$$のソートをしてから同じアルゴリズムを適用することによって、$${O(N \log N)}$$で解くことができます。（約33分）

※さらに$${\{A_i\},\{C_i\}}$$に等号が混じる場合は、$${(A_i,C_i)}$$のソートを辞書順（$${A_i}$$は昇順、$${C_i}$$は降順）で実行することでほぼ同様に解くことができます。（完全に同一のカードを複数採用する場合は、そのことも考慮して実装する必要があります。）

#input
#入力値とカード番号を含めたtuple(A_i,C_i,i)を格納するリストを作る。
#カード番号は1から始まることに注意して、[0, N)から整数iをとってi+1を入れる。
ACI = [(0,0,0)]*N
for i in range(N):
    ta, tc =  input().split()
    ACI[i] = int(ta), int(tc), i+1

#process
#Aの昇順で並べ替える。
sorted_ACI = sorted(ACI, key=lambda x: x[0])

m = sorted_ACI[N][1]
ans = []

#条件に従ってCの部分単調増加列をとる。
for t in reversed(sorted_ACI):
    if m >= t[1]:
        m = t[1]                    #採用するカードのコストをmに格納して保持する。
        ans.append(t)               #採用するカードの情報（強さ,コスト,番号）をansに追加。

#output
#部分列のカードの枚数および昇順にソートしたカード番号を答える。
print(len(ans))
print(*sorted([x[2] for x in ans]))

D問題 - AtCoder Wallpaper

問題
D - AtCoder Wallpaper

答案①（AC ※コンテスト後）
$${A,B,C,D}$$が巨大のため、$${O(N)}$$では到底間に合わないです。
壁紙のパターンは、$${4\times 2}$$の長方形領域を繰り返す規則性があるので、これを用いて$${8}$$種類のマスがそれぞれいくつ含まれているかを$${O(1)}$$で計算し、マスごとの面積と掛け合わせた総和を求めればそれが答えとなります。

方針が立つまでは一瞬だったのですが、まさかの剰余類の数え上げでパニックになってしまって30分を溶かしてしまい、コンテスト中に提出できませんでした。。。
剰余の応用・$${O(1)}$$問題については両方ともほぼ経験がなかったので、今回解けなかったことは仕方ない（とさえ思いたくない）としても、つぎはこの程度の内容でやられないようにします。

#input
A, B, C, D = map(int,input().split())

#process
#1×1マスを左下の座標で代表させて、A,B,C,Dが定める長方形に含まれる8種のマスの個数を数える。

#水平方向のパターンの数え上げ
#右から長さ4の区間を繰り返し取り除いた余りをres_ACとし、
#[A,C)に含まれる剰余類の濃度nv_0,...,nv_3をそれぞれ求める。
res_AC = range(A, A+(C-A)%4)

nv_0 = len([x for x in res_AC if x % 4 == 0])+ (C-A) // 4
nv_1 = len([x for x in res_AC if x % 4 == 1])+ (C-A) // 4
nv_2 = len([x for x in res_AC if x % 4 == 2])+ (C-A) // 4
nv_3 = len([x for x in res_AC if x % 4 == 3])+ (C-A) // 4

#垂直方向のパターンの数え上げ
#上から2の整数商を取っていったあまりをres_BDとし、
#[B,D)に含まれる剰余類の濃度nh_0,nh_1をそれぞれ求める。
res_BD = range(B, B+(D-B)%2)

nh_0 = len([x for x in res_BD if x % 2 == 0]) + (D-B) // 2
nh_1 = len([x for x in res_BD if x % 2 == 1]) + (D-B) // 2

#黒く塗られた部分の面積を計算する
#4種の列パターンにおける黒く塗られた領域の面積（の2倍）の計算
#列方向にマスの面積の総和をとる。
ap0 = 2*nh_0+nh_1
ap1 = nh_0+2*nh_1
ap2 = nh_1
ap3 = nh_0

#全体の黒く塗られた領域の面積（の2倍）の計算
#行方向に「列方向にマスの面積の総和をとったもの」の総和をとる。
ans = nv_0*ap0+nv_1*ap1+nv_2*ap2+nv_3*ap3

#output
print(ans)