【C#】ABC-144 - E - Gluttony

2019/10/28 23:41 図が間違っていたのを修正

ABC爆死したので解説記事書きます。悔しい…悔しい…

2019/10/27 AtCoder Beginner Contest 144
Rank: 3504(rated)
Perf: 515
Rating: 728(-22)
https://t.co/HDR7FL48j2

ふんっ(-22)
— Atria (@AtriaSoft) October 27, 2019

問題文引用

高橋君は早食い大会に出ることにしました。

この大会は N 人でのチーム戦であり、高橋君のチームは年齢順に 1から N までの番号がついた N 人のメンバーからなります。メンバー i の消化コストは Ai です。

大会では 1 から N までの番号がついた N 個の食べ物が用意されており、食べ物 i の食べにくさは Fi です。大会のルールは以下の通りです。

1個の食べ物につき1人のチームメンバーを割り当てる。同じメンバーを複数の食べ物に割り当てることはできない。

あるメンバーについて、そのメンバーの消化コストが x、担当する食べ物の食べにくさがyのとき、その食べ物の完食には x*y 秒かかる。

N人のメンバーそれぞれが完食にかかる時間のうち最大値が、チーム全体の成績となる。

コンテストの前に、高橋君のチームは修行をすることにしました。

各メンバーは、自分の消化コストが0より小さくならない限り、1回修行するごとに自分の消化コストを1減らすことができます。ただし、修行には膨大な食費がかかるため、N人合計でK回までしか修行することができません。

各メンバーの修行回数と担当する食べ物を適切に選んだとき、チーム全体の成績は最小でいくらになるでしょうか。

制約

入力はすべて整数
1≤N≤2×10^5
0≤K≤10^18
1≤Ai≤10^6(1≤i≤N)
1≤Fi≤10^6(1≤i≤N)

引用元:https://atcoder.jp/contests/abc144/tasks/abc144_e

解説

メンバーの消化コストを格納した配列をMember,食べ物の食べにくさを格納した配列をFoodsとします。

まずは「K=0についての最適解を考える」事から始めます。

K=0についての最適解を考える

K=0のとき、最適解は”昇順ソートしたMember[i]*降順ソートしたFoods[i]”となります。

K > 0についての最適解を導く

ここで、Kの制約に着目すると愚直に求めること(つまりkをインクリメントしてシュミレーションで求めること)が不可能だと分かります。

おまけ：（何を勘違いしたかシュミレーション解をコンテスト中に提出してしまった。もちろんTLE。）

そこで、「すべてのMemberに対して、完食にかかる時間をX(これが答え)以下にできるか」という問題について考えます。

ここで「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め、(2)可能かどうかを求める関数」を作成します。

Member[i] * Foods[i] で出てくる値のすべてをX以下にしたい。

この計算方法を用いることで、「(1)すべての数をX以下としたときに、何回の操作(修行)が必要なのか」を求められます。

状況を整理するため、この関係を数式に起こすとこうなります。ここでは、必要とされる手数をneedと置いています。また、“X以下としたい”のXをtargetとして置いています。

この式を用いて必要な手数の合計、「ex」を導き出します。(二つ上の画像の “7cost!” ってやつ)

そして、(2)可能かどうかを求めるのですが、これは「ex <= k」を満たすかどうかで判断できます。

これらより、「(1)すべての値をx以下にするために何回操作(修行)が必要なのかを求め、(2)可能かどうかを求める関数」はこうなります。

static bool is_possible(long target)
{
     long ex = 0;
     for (int i = 0; i < N; i++)
     {
         long need = target / Foods[i];
         ex += Max(0, Member[i] - need);
     }
     return ex <= K;
}

static bool is_possible(long target)

{

long ex = 0;

for (int i = 0; i < N; i++)

{

long need = target / Foods[i];

ex += Max(0, Member[i] - need);

}

return ex <= K;

}

※exに間違って負の数を加算しないよう気をつけましょう

二分探索を用いる

残り必要な作業は “X(target)の決定”です。

これは二分探索を用いることで解決できます。

X(target)を二分探索することで、計算量を抑えながら答えを導くことができます。

二分探索Tips:

– left は常に条件を満たさない

– right は常に条件を満たす

– right – left = 1 になるまで範囲を狭める (最後は right が条件を満たす最小)

【めぐるのアルゴリズム講座】
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l
— 因幡めぐる@競技プログラミング (@meguru_comp) February 9, 2016

まとめ

今回の問題の流れをまとめるとこんな感じです。

入力を受け取る
Memberを昇順ソート、Foodsを降順ソート
操作可能かどうかを求める関数を作る
二分探索でX(target)を設定しながら関数を使う
条件に合うX(target)を出力する

ACコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class AtCoderrr
    {
        static long N,K;
        static long[] Member, Foods;
        static void Main(string[] args)
        {
            long[] nk = ReadLine().Split(' ').Select(long.Parse).ToArray();
            N = nk[0];
            K = nk[1];
            Member = ReadLine().Split(' ').Select(long.Parse).ToArray();
            Foods = ReadLine().Split(' ').Select(long.Parse).ToArray();
            Array.Sort(Member);
            Array.Reverse(Member);
            Array.Sort(Foods);
            if (is_possible(0))
            {
                WriteLine(0);
                return;
            }

            //ここから二分探索
            //求めるべき答えを見つけ出す
            long left = 0, right = (long)1e18;
            while (right-left &gt; 1)
            {
                var mid = (left + right) / 2;
                if (!is_possible(mid))
                {
                    left = mid;
                }
                else
                {
                    right = mid;
                }
            }
            WriteLine(right);
        }


        static bool is_possible(long target)
        {
            long ex = 0;
            for (int i = 0; i &lt; N; i++)
            {
                long need = target / Foods[i];
                ex += Max(0, Member[i] - need);
            }
            return ex &lt;= K;
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.IO;

using System.Text;

using static System.Console;

using static System.Math;

namespace AtCoder

{

class AtCoderrr

{

static long N,K;

static long[] Member, Foods;

static void Main(string[] args)

{

long[] nk = ReadLine().Split(' ').Select(long.Parse).ToArray();

N = nk[0];

K = nk[1];

Member = ReadLine().Split(' ').Select(long.Parse).ToArray();

Foods = ReadLine().Split(' ').Select(long.Parse).ToArray();

Array.Sort(Member);

Array.Reverse(Member);

Array.Sort(Foods);

if (is_possible(0))

{

WriteLine(0);

return;

}

//ここから二分探索

//求めるべき答えを見つけ出す

long left = 0, right = (long)1e18;

while (right-left > 1)

{

var mid = (left + right) / 2;

if (!is_possible(mid))

{

left = mid;

}

else

{

right = mid;

}

WriteLine(right);

}

static bool is_possible(long target)

{

long ex = 0;

for (int i = 0; i < N; i++)

{

long need = target / Foods[i];

ex += Max(0, Member[i] - need);

}

return ex <= K;

}

提出

https://atcoder.jp/contests/abc144/submissions/8181961

【C#】ABC-144 – E – Gluttony

問題文引用

制約

解説

K=0についての最適解を考える

K > 0についての最適解を導く

おまけ：（何を勘違いしたかシュミレーション解をコンテスト中に提出してしまった。もちろんTLE。）

二分探索を用いる

まとめ

ACコード

提出

Atria

最近の投稿

カテゴリー

問題文引用

制約

解説

K=0についての最適解を考える

K > 0についての最適解を導く

おまけ：（何を勘違いしたかシュミレーション解をコンテスト中に提出してしまった。もちろんTLE。）

二分探索を用いる

まとめ

ACコード

提出

Atria

タグクラウド

最近の投稿

カテゴリー

人気記事