AtCoder Beginner Contest 306に参加したので冒頭4問を振り返ります

こんにちは。

ダイの大冒険という漫画のガチ勢のbun913といいます。

皆さんはAtCoderという競技プログラミングを楽しめるサービスをご存知でしょうか？

https://atcoder.jp/?lang=ja

私は以前よりちょくちょく趣味でコンテストに参加しているのですが、先日の2023年6月18日（土）に開催されたトヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)にも参加していました！

今回はA問題、B問題、C問題、D問題を正解することができたので正解に至った思考の整理や類似の問題なんかを軽く紹介いたします。

解いた問題と正解に至るまで

A - Echo

要するに長さNの文字列Sが与えられるため、Sの一文字一文字を2回ずつ表示すれば良いという問題ですね。

特に迷うこともなく素直に以下のように実装しました。

N = int(input())
S = input()
# 答えを保持するための配列
ans = []

for s in S:
    # 素直に2回ずつ配列に文字を詰めていく
    ans.append(s)
    ans.append(s)
# 配列を展開して標準出力に出力。区切り文字列を" "とすることでスパッと意図した形で出力する。
print(*ans, sep="")

B - Base 2

0と1 からなる長さ64の数列 A = (A0,A1,...,A63)が与えられます。

A0 * 2 **0 + A1 * 2 **1 + .... + A63 * 2 **63を求めてください

こちらについて、普通にfor文を回して指示通りにすれば良いと思ったのですが、私はこの式を見たときに以下のような着想を得ました。

• これって普通に2進数から10進数に変更するときの式と似てるな
• っていうか、数式をひっくり返して2進数を10進数に変更すれば良いのでは？

普段以下のように2進数を10進数に変換する計算をします。

2進数1010を10進数に変換
(0 * 2 **0) + (1 * 2 ** 1) + (0 * 2 ** 2) + (1 * 2 ** 3)
= 10

数列Aの場合はひっくり返して上げる必要がある点にだけ注意が必要なので、以下のように実装しました。

A = list(map(str, input().split()))
# Aを反転させた配列を取得
RA = A[::-1]
# 文字列として結合
s = "".join(RA)
ans = int(s, 2)
print(ans)

C - Centers

なんというか「素直に実装する類のC問題」だなぁぁ〜と思いました。（小並感）

とはいえ本番では焦っていたので、問題文を斜め読みしてしまい逆に時間をかけてしまいました。

特に解説できるポイントもないのですが、以下のように実装しました。

N = int(input())
A = list(map(int, input().split()))
# 出現回数の管理用
cnt_list = [0 for _ in range(N+1)]
# 2回目に現れるインデックスの管理用
ind_list = [0 for _ in range(N+1)]

# Aの中に出てくるiのうちちょうど2回目に出てくる添字番号をメモしておく
for i, a in enumerate(A):
    cnt_list[a] += 1
    if cnt_list[a] == 2:
        ind_list[a] = i+1 # 振り返り時追記: +1するのが無駄実装
# ind_listのうち要素を再度取得して大きい順に並び替え
inds = sorted(ind_list[1:])
# ind_listにはAの要素番号があるため、あとはそれを順に出力するだけ
ans = []
for ind in inds:
    ans.append(A[ind-1]) # 振り返り時追記: ↑の無駄実装のせいで-1しないといけない
print(*ans, sep=" ")

D - Poisonous Full-Course

高橋くんがお腹を壊した状態で毒入りの料理を食べると⚪︎んでしまうというパワーワード溢れる面白い問題でした。

• 料理に美味しさが設定されているので、美味しさの総和が最大になるように食べる必要がある
  • 料理は食べても食べなくても良いが、食べなかった料理はもう後で食べることはできない
• お腹を壊した状態で解毒剤入りの料理を食べるとお腹の調子が元に戻る
• お腹を壊した状態で毒入りの料理を食べる終了
  • 条件として高橋くんは後に控える大事な仕事のために生きた状態でレストランを出ないといけません
• お腹を壊していない状態で毒入りの料理を食べるとお腹を壊す

という点を踏まえて実装していく必要がありました。

↑のようなお腹の状態を気にする必要があるのと、解毒剤入りの料理は美味しさが、-100だけどその後に出てくる毒入りの料理の美味しさが1000というパターンなどを考えると、素直にその場その場の最適な料理を食べれば良いというわけではなさそうだなと考えました。（いわゆる、貪欲法というやつ？）

ということで、動的計画法（DP） という実装をすれば良さそうだな！と思ったのですが、動的計画法の問題を解く訓練はしていなかったので、実装までに時間がかかりました。

• 参考:動的計画法の基礎的な問題
  • 028 - Frog 1

具体的にいうとお腹を壊した状態でのi皿目での美味しさの最大値 と お腹を壊していない状態でのi皿目での美味しさの最大値 の管理をどのようにするかという点を考えていました。

最終的には以下の様に実装しました。

N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

# dp[i][0]: i番目の料理まで食べたときに、お腹を壊していない状態でのおいしさの最大値
# dp[i][1]: i番目の料理まで食べたときに、お腹を壊している状態でのおいしさの最大値
dp = [[-float('inf'), -float('inf')] for _ in range(N+1)]
dp[0][0] = 0
dp[0][1] = 0

for i in range(1, N+1):
    # i番目の料理を食べない場合
    dp[i][0] = max(dp[i][0], dp[i-1][0])
    dp[i][1] = max(dp[i][1], dp[i-1][1])
    # i番目の料理を食べる場合
    if X[i-1] == 0:
        # 解毒剤入りの場合
        # 前回の皿までで毒入りのものを食べていても解毒剤さえ食べれば無問題
        # なので、「i-1皿目までの美味しさの最大値 (お腹壊している状態、お腹壊していない状態双方)+i皿目の美味しさ」を考える
        dp[i][0] = max([dp[i][0], dp[i-1][1] + Y[i-1], dp[i-1][0] + Y[i-1]])
    else:
        # 毒入りの場合
        # 「i-1皿目までの美味しさの最大値（お腹を壊していない場合）+i皿目の美味しさ」を考える
        dp[i][1] = max([dp[i][1], dp[i-1][0] + Y[i-1]])
print(max(dp[N]))

最後に

現在のところ私は「C問題までをほぼ確実に解くマン」を目指しているのですが、本番でD問題を解けたのが初めてで非常に嬉しかったです。

一方でこのコンテストも諸般の事情によりUnrated（レートに反映されない）となってしまい、ちょっぴり残念な気持ちになってしまったことは否めません。

「1回1回のコンテスト結果に左右されず、解いたC問題の過去問の数」を目標としていたはずなのに、人間というのは欲深いですね（？）

とはいえ、C問題・D問題が解けたというのは素直に実装力や考察力が上がってきている証拠だと思いますので、引き続きゆるりと精進してまいります。