AtCoder Beginner Contest 187 D - Choose Me

今日は仕事帰りにたい焼きを食べちゃいました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc187/tasks/abc187_d)にて開催されました、AtCoder Beginner Contest 187 D問題「D - Choose Me」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。 市には N 個の町があり、 i 番目の町には青木派の有権者が A i 人、高橋派の有権者が B i 人います。他に有権者はいません。 高橋氏は、それぞれの町で演説を行うことができます。 高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。 一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。 高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？

2.制約

• 入力は全て整数
• 1 ≤ N ≤ 2 × 10⁵
• 1 ≤ A i , B i ≤ 10⁹

3.入出力例

• 入力

4
2 1
2 2
5 1
1 3

• 出力

1

3 番目の町で演説を行うと、青木氏が 5 票、高橋氏が 6 票を得ます。

4.初見の感想

• 最も効率よく演説したい
• 効率は演説したときの票の増減差である、2*A+Bで計算できる

  5.学びポイント

• どの街を回ったかは関係なく、演説した街の数だけ出せばよい
• ソートして演説でついた増減差が青木派の数を超えればよい

  6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[,] A = new long[N,2];
            long[] B =new long[N];
            long sum=0;
            for(int i=0;i<N;i++){
                String[] input = Console.ReadLine().Split(' ');
                A[i,0]=long.Parse(input[0]);
                A[i,1]=long.Parse(input[1]);
                B[i]=A[i,0]*2+A[i,1];
                sum+=A[i,0];
            }
            Array.Sort(B);
            long ans=0;
            for(int i=N-1;i>=0;i--){
                sum -= B[i];
                ans++;
                if(sum<0){break;}
            }
            Console.WriteLine(ans);
        }
    }
}

7.最後に

何を基準に選ぶのかという視点を常に持ちたいですね。