はじめに
問題文と公式の解答
メモ
事前に計算しておくことがコツ。制約から問題の性質を考えることもできるよねー。今思うのはとりあえず色々な道具知っていき、これは?あれ試せるかな?って一つずつ試して行ったらどうにかなる気がする。
ステップ
- まずは入力値を受け取る
- 事前に計算した後に(
3重for
)、ぶちこみたい箱を用意する - では実際に計算して計算結果をここにぶち込む
- その箱の中にエックスはあるかいと問う。
解答例 Java
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[] A = new long[N]; for (int i = 0; i < A.length; i++) { A[i] = sc.nextInt(); } int M = sc.nextInt(); long[] B = new long[M]; for (int i = 0; i < M; i++) { B[i] = sc.nextInt(); } int L = sc.nextInt(); long[] C = new long[L]; for (int i = 0; i < L; i++) { C[i] = sc.nextInt(); } int Q = sc.nextInt(); long[] X = new long[Q]; for (int i = 0; i < Q; i++) { X[i] = sc.nextInt(); } // pre HashSet<Long> pre = new HashSet<Long>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (int j2 = 0; j2 < L; j2++) { long temp = A[i] + B[j] + C[j2]; pre.add(temp); } } } for (int i = 0; i < Q; i++) { // System.out.println(i); // process for (int j = 0; j < pre.size(); j++) { if (pre.contains(X[i])) { System.out.println("Yes"); break; } else { System.out.println("No"); break; } } } } }
解答例 2 公式をJaavに変換
memo
回答零2のほうで面白いなと思ったポイントは、ストリング型に格納してからスプリットを使って文字を数字に直してるところ!考え方は上のやつと一緒。
#include <iostream> #include <vector> #include <bitset> int main() { using namespace std; unsigned N, M, L; cin >> N; vector<unsigned> A(N); for (auto &&a : A) cin >> a; cin >> M; vector<unsigned> B(M); for (auto &&b : B) cin >> b; cin >> L; vector<unsigned> C(L); for (auto &&c : C) cin >> c; // 連続する 3e8 + 1 bit を用意して // A[i] + B[j] + C[k] として出現する値かどうかを管理 bitset<300000001> possible; for (const auto a : A) for (const auto b : B) for (const auto c : C) possible[a + b + c] = true; unsigned Q; cin >> Q; for (unsigned i = 0, x; i < Q; ++i) { cin >> x; cout << (possible[x] ? "Yes" : "No") << endl; } return 0; }