ABC466-C Count Close Pairs

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        int Answer = 0;
        int R = 1;
        for (int L = 1; L <= N; L++) {
            while (R + 1 <= N && IsLower1(L, R + 1)) {
                R++;
            }
            Answer += R - L;
        }
        Console.WriteLine("! {0}", Answer);
    }

    // 2点間の距離が1以下かを返すヘルパメソッド
    static bool IsLower1(int pSta, int pEnd)
    {
        if (pSta == pEnd) return true;

        Console.WriteLine("? {0} {1}", pSta, pEnd);
        string Result = Console.ReadLine();
        return Result == "Yes";
    }
}

解説

2点間の距離が1以下かを返すヘルパメソッドを用意し、
尺取法で解いてます。

問い合わせ上限を超えないかに関しては、
右端が伸びない問い合わせは、最大N回
右端が伸びる問い合わせも、最大N回
なので2N回を超えないと分かります。