目次

• 問題
  • 入力
  • 出力
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/abc005/tasks/abc005_3

たこ焼きをすべてのお客さんに提供できるかを判定する問題です.

# 入力

T
N
a_1 a_2 ... a_N
M
b_1 b_2 ... b_N

• T - T秒以内に出来たたこ焼きまでは売れる
• N - たこ焼きの数
• a_i - たこ焼きが$a_i$秒時点で出来ることを表す時間
• M - お客さんの数
• b_i - お客さんが$b_i$秒時点で来ることを表す時間

# 出力

すべてのお客さんに待たせることなく１つずつたこ焼きを売ることが出来るならyes.
出来ないならnoと答える問題です.

T秒より前に出来たたこ焼きは売ることは出来ません.

# 解説

お客さんに１つずつたこ焼きをマッチングする問題です.

問題を解き始める前に可能な計算量を見積もっておきます.
$T, M, N$がともに$100$と小さいので$O(TMN)$程度の三重ループでも間に合います.
ただし明らかに$O(2^N)$の全探索は間に合いません.

これを念頭に置いて問題をよく理解すると、あるお客さんに対して売れる可能性のあるたこ焼きは以下の１パターンであることが分かります.

まだ売れていないたこ焼きの内お客さんの到着時間 - T以内に完成したたこ焼き

前のお客さんまでで売れているたこ焼きは確定しています.
また、Tを過ぎたたこ焼きは単純に使わずにスルーすれば良いです.
完成しているたこ焼きが１つも無くなった時点でお客さんを待たせることになるので答えはnoです.

問題になるのは、お客さんの到着時間 - Tを満たすたこ焼きが複数ある場合です.
この場合どのたこ焼きを売るのが正しいでしょうか.
答えは最も早く完成したたこ焼きです.
なぜならその方が次のお客さんに別のたこ焼きを売れる可能性が高いからです.

# 計算量

$O(M)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

Int T, N, M;
vector<Int> A;
vector<Int> B;

void input() {
  cin >> T >> N;
  Int x_;
  loop(n,0,N) {
    cin >> x_;
    A.push_back(x_);
  }
  cin >> M;
  loop(m,0,M) {
    cin >> x_;
    B.push_back(x_);
  }
}

bool match() {
  Int a_i = 0;
  loop (b_i,0,B.size()) {
    bool last = b_i == B.size()-1;
    Int b = B[b_i];
    while (a_i < A.size()) {
      if (b - A[a_i] < 0) return false; // b is waiting!
      if (b - A[a_i] > T) { a_i++; continue; } // too old takoyaki. Look for newer one.
      if (last) return true; // Found and b is the last person, completed!
      a_i++; break; // Found. Next person.
    }
  }

  return false; // No more takoyaki. Sold out.
}

void solve() {
  if (match()) cout << "yes" << endl;
  else cout << "no" << endl;
}

int main() {
  input();
  solve();
  return 0;
}