ABC326の解説記事 (PyPy3 ABC)

はじめに

問題はこちら
初心者（灰色〜茶色）向けです。
自力ACしたC問題まで実施します。

A - 2UP3DOWN

考え方

X階 → Y階の移動ですから、登りはプラス、下りはマイナスとして、 Y-Xの値を考えればよいです。
2回までの登り、3回までの下りの際に階段を使うので、

-3\space\leq Y - X \leq\space2

であれば　階段（= Yes）、そうでなければエレベーター（= No)です。

解答例

私の解答

x, y = map(int, input().split())
print('Yes' if (-4 < y-x and y-x < 3) else 'No')

B - 326-like Numbers

考え方

実際に 326-like Numbers の一覧を作成し、n 以上のものの個数を求めればよいです。
なぜなら、326-like Numbers は たかだか3桁の自然数ですから、100~999の1000個もないからです。

実際に、次のように 326-like Numbers　を構成できます。

1. 100の位をi, 10の位をjとします。（i = 1, 2, ... , 9 であることに注意）
2. 1の位は i × j になります。 ここで、i × j >= 10の場合は 326-like Numbers にはならないことに注意です。

解答例

私の解答

n326s = set()
for i in range(1,10) :
    for j in range(10) :
        if i*j > 9 :
            break
        n326s.add(100*i + 10*j+ i*j)
n = int(input())
print(filter(lambda x:x >= n, n326s))

C - Peak

考え方

プレゼントの数が最大になるパターンはいずれかの整数値、特にプレゼントの位置と考えてよいです。
実際に、最大値となる数直線の位置をxとすると、床関数の値 floor(x)の値をxと取り直しても最適であることは変わらないです。また、xの位置にプレゼントがないとき、xの先にある最初のプレゼントの位置をxと取り直しても最適のままです。
最初のプレゼントから順番に、各プレゼントの位置から長さMの半開区間にあるプレゼントの数を数えていき、最大のパターンだけ記録していく貪欲法で解けます。
私の解答について記載します。（おそらく尺取法に分類されると思います。）

1. プレゼントを昇順ソートします。
2. 次の変数を用意します。
   • base ： 基準となるプレゼントの番号、初期値0
   • now ： 区間の中にあるプレゼントの番号、初期値0
   • tmp ： baseからnowまでののプレゼントの数、初期値0
   • ans ： base-1番まででチェックしたプレゼントの数の最大値、初期値0
3. nowが最後に行くまで下記処理を繰り返します。
   1. 番号baseのプレゼントの位置（a_n[base]）から距離m未満のプレゼントの数を求めます。
      具体的には、番号nowのプレゼントの位置（a_n[now]）を、番号baseのプレゼントの位置(a_n[base]) + m 未満の位置にある間、nowとtmpを増やす。
   2. a_n[now]がa_n[base]+mの外に移動した場合、最大値を更新します。
      具体的には、tmpがansより大きければ、ansをtmpに置き換えます。
   3. base の位置を下記まで進めます。
      a_n[base] <= a_n[now] < a_n[base] + m　となる最初のbase
      （ = nowのプレゼントを拾える最初のbase)
      なぜかというと、a_n[base+1] + m < a_n[now] の場合は、a_n[base+1] + m の範囲内のプレゼントの数 は a_n[base] の時よりも1つ小さくなり、必ず、最大値にはならないからです。（now のプレゼントが拾えないまま、baseのプレゼントが拾えなくなる）
4. ループを抜けたタイミングのtmpとansのうち大きい方が答えになります。(私の解答では、最後のタイミングの更新ができていないです。拙劣な実装で恐縮です。）

解答例

私の解答

n, m = map(int, input().split())
a_n = sorted(list(map(int, input().split())))
now, base, tmp, ans = 0, 0, 0, 0
while now < n :
    if a_n[now] < a_n[base] + m :
        tmp += 1
        now += 1
    else :
        ans = max(ans, tmp)
        while base <= now :
            if a_n[now] < a_n[base] + m :
                break
            else :
                base += 1
                tmp -= 1
print(max(ans, tmp))

参考文献

特段なし

感想

今回D問題が解けず悔しかったです、、、 ４以上の場合のパズルの解き方のアルゴリズムがわからない、、、

問題

年内入緑目指して頑張ります。