公式

A - Seats 2 解説 by harurun4635


プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。 また、プログラミングコンテストの問題に慣れていない方は、 AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。


結論からいえば \(M \le \lceil N / 2 \rceil\) であれば Yes 、そうでなければ No です。 \(2M -1 \le N\) と書くこともできます。

以下のように証明できます。

11223344 ...\(2\) つずつ前から数字を書き込んでいきます(奇数の場合は最後の数字は \(1\) 回だけ書き込みます)。最後に書き込まれた数字は \(X = \lceil N / 2 \rceil\) です。

このとき、条件から同じ数字が書き込まれた座席には \(1\) 人までしか座れません。よって \(X \lt M\) ならば座らせることはできません。逆に \(M \le X\) のときは、\(i\) 人目を左の \(i\) に座らせることで oxox ... のようになり、これは条件を満たしています。

Python の実装例

n, m = map(int, input().split())
print("Yes" if 2 * m - 1 <= n else "No")

C++ の実装例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m; cin >> n >> m;
    cout << (2 * m - 1 <= n ? "Yes" : "No") << endl;
}

投稿日時:
最終更新: