ABC474Dを解いた【構築】

筆者はレート800前後の茶～緑コーダ

ABC474のD問題を解いていく

実装コード

A[i] > B[i] となる位置を1つ選び、その位置だけ値を十分大きくすることで条件を満たす数列を構築する。

• N と数列 A, B を受け取る
• A[i] > B[i] を満たす位置を探し、変数 x に保存する
• 条件を満たす位置が1つもなければ、構築できないため No を出力して終了する
• 構築できる場合は Yes を出力し、すべての要素が 1 の配列 ans を用意する
• ans[x] だけを十分大きな値 10 ** 18 に変更する
• 最後に構築した ans を出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    A = rLI()
    B = rLI()

    x = -1
    for i in range(N):
        if A[i] > B[i]:
            x = i

    if x == -1:
        print("No")
        return

    print("Yes")
    ans = [1] * N
    ans[x] = 10 ** 18
    print(*ans)

if __name__ == '__main__':
    main()

感想

このように、条件を満たす具体例を作る問題は 構築 と呼ばれるらしい。
不可能になる条件を絞り込み、それ以外の場合に実際の数列をどう作るか考えるのがポイントだと分かった。