Pythonで競プロに挑む日誌 vol.9 ~余剰とグループ分け~

休日は逆に調子上がらない説.

現在の目標

• 今年の10月内に茶色を取得する
  • ABS の問題を全部解く←イマココ
  • ABC の A, B 問題を全部解く
• 年内に緑色を取得する
  • ABC の C, D 問題を全部解く
• APG4b で C++ にも手を出す

今日の問題

ABC086C - Traveling
https://beta.atcoder.jp/contests/apg4b

結果

answer.py

#coding: utf-8
import sys
N = int(input())

for i in range(N):
    t, x, y = map(int, input().split())
    #print(t, x, y)

    if x + y > t or (x + y)%2 != t%2:
        print("No")
        sys.exit()
print("Yes")

# 実行時間：319 ms
# メモリ　：3060 KB
# コード長：322 Byte
# 得点　　：300/300

またも自力では回答できませんでした...こちらの解説や, ほかの方の回答を参照しました.

動き方の条件から, 初期位置 (0, 0) で 1 秒ごとに x + y の偶奇が変わるので, x + y と t の偶奇が一致するかを判定すればよいとのこと.

図を描いたら, t の偶奇で点を分類できそうなことはわかったのですが, そこから余剰を利用することまで頭が回りませんでした. 余剰はグループ分けに便利な演算だということを学びました.

また, 前後の座標との因果関係について考えてしまっていたので収集つかなくなってました. 与えられる座標一点の情報で判定できる方法を模索すべきでしたね. 「問題をより小さくできないか」という視点を養いたいものです.

明日やること

• ABC を解き始める.