はじめに
自分用の備忘録。
この問題のポイント
時間と距離の偶数、奇数は一致している必要がある!1つ前の交差点と目的地の交差点が番号を振ると偶数と奇数で絶対に逆になる。それに、もし地点0から5秒後に2つ離れたところにいてねって言われてもできない。なぜなら、1秒ごとに動かないと行けないから、。偶数の地点に行くには偶数の時間、奇数の地点に行くには奇数の時間が指定されている必要がある!例えば、、地点0,0 から地点2,2に行きたい場合、最短でも4秒かかる。1秒ごとに1つ動かないと行けないから、5秒後にここにいてねって言われても無理。でも、6秒後ならいける。でも、7秒後はむり。このように、時間と距離の偶数、奇数は一致している必要がある!
この問題は何秒で到達できるかっていうことを言われてるから、距離的にそもそも行けるのかどうかを出してあげる必要がある。
メモ
写経、それは一行一行写し、一行ずつの意味と経緯を自問自答する行為
問題文と公式の解答例(C++)
問題文
解答例(Java)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] t = new int[110000]; int[] x = new int[110000]; int[] y = new int[110000]; t[0] = x[0] = y[0] = 0; // 初期状態 for (int i = 0; i < N; ++i) { t[i+1] = scanner.nextInt(); x[i+1] = scanner.nextInt(); y[i+1] = scanner.nextInt(); } boolean can = true; for (int i = 0; i < N; ++i) { int dt = t[i+1] - t[i]; int dist = Math.abs(x[i+1] - x[i]) + Math.abs(y[i+1] - y[i]); if (dt < dist) can = false; if (dist % 2 != dt % 2) can = false; // dist と dt の偶奇は一致する必要あり! } if (can) System.out.println("Yes"); else System.out.println("No"); } }
メモ
解答例 2
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] t = new int[N + 1]; int[] x = new int[N + 1]; int[] y = new int[N + 1]; boolean flag = true; t[0] = x[0] = y[0] = 0; for (int i = 1; i <= N; i++) { t[i] = sc.nextInt(); x[i] = sc.nextInt(); y[i] = sc.nextInt(); } // abstrute for (int i = 1; i <= N; i++) { int timeDifference = t[i] - t[i -1]; int distance = Math.abs(x[i] - x[i - 1]) + Math.abs(y[i] - y[i - 1]); if (distance > timeDifference) { flag = false; break; } if (timeDifference % 2 == distance % 2) { flag = true; } else { flag = false; break; } } if (flag) { System.out.println("Yes"); } else { System.out.println("No"); } } }