C - Snuke Festival
はじめに
競技プログラミング、AtCoder Beginner Contest 077
C - Snuke Festival
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
今年もすぬけ祭の季節がやってきました。 りんごさんは、まず手始めにすぬけ君召喚の儀式を執り行おうと思っています。 儀式には祭壇が必要で、祭壇は上部、中部、下部の 3 つのカテゴリーのパーツ 1 つずつからなります。 祭壇の 3 カテゴリーのパーツがそれぞれ N 個ずつあります。 i 個目の上部のパーツのサイズは Ai 、i 個目の中部のパーツのサイズは Bi 、i 個目の下部のパーツのサイズは Ci です。 祭壇を作るにあたっては、中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません。 逆に、この条件を満たす任意の 3 つのピースを組み合わせて祭壇を作ることができます。 りんごさんが作ることのできる祭壇は何種類あるでしょうか。 ただし、2 つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち 少なくとも 1 つが異なることを言います。
制約
・1≤N≤10^5 ・1≤Ai≤10^9(1≤i≤N) ・1≤Bi≤10^9(1≤i≤N) ・1≤Ci≤109(1≤i≤N) ・入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。 N A1 ... AN B1 ... BN C1 ... CN
出力
りんごさんが作ることのできる祭壇の種類数を出力せよ。
解き方
以下を参考にしています。
https://img.atcoder.jp/arc084/editorial.pdf
https://atcoder.jp/contests/abc077/submissions/4561061?lang=ja
解き方の流れ
まず、条件に
「中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません」
とあることから
祭壇のできるパーツの組み合わせは全て
Ai<Bi<Ciであることが分かります。
ここから、
Biを決めてしまえば
AiはBiよりも小さい値、
CiはBiよりも大きな値の個数を数えられれば
各Biに対する祭壇を作れる個数を出すことができ
全て足し合わせれば
問題の答えとなる「りんごさんが作ることのできる祭壇の種類数」を出すことができます。
解き方の流れ
①Biを１つ決める
②Biよりも小さいAi、Biよりも大きいCiの個数をそれぞれ出す
③ ②で出したAiとCiの個数をかけて、①で選んだBiを使用した際に作れる祭壇の種類数を出す
④残りの各Biに対して①～③を繰り返す
⑤ ③で出した各Biを使用した際に作れる祭壇の種類数を全て足し、問題の答えを求める
実装する
この問題を実装する際、
どのように
Biよりも小さいAiの個数、
Biよりも大きいCiの個数を
出すかが問題になります。
これは解き方の流れの
②Biよりも小さいAi、Biよりも大きいCiの個数をそれぞれ出す
にあたります。
Biよりも小さい数字の個数、
Biよりも大きい数字の個数を求めたいので
Ai、Ciの配列を小さい順に並び替えれば
二分探索を使うことができます。
二分探索 - Wikipedia
～よりも小さい数字の個数
まずは
Biよりも小さい数字の個数が欲しい
Aiの個数を出す二分探索を考えます。
コードは以下です。
//引数 value=Bi array=Aiの配列
static long LowerBound(long value, long[] array)
{
//下は０でスタート
var low = 0;
//上は配列の長さでスタート
var high = array.Length;
//highがlow以下になるまで探索を繰り返す
while (low < high)
{
//中間地点(index)
var middle = (high + low) / 2;
//valueが中間地点以下であれば上を中間地点に引き下げる
if (value <= array[middle]) high = middle;
//中間地点よりもvalueが大きければ下を中間地点に引き上げる
else low = middle + 1;
}
return low;
}
まず引数は
long value = Bi
long[] array = Aiの配列
です。
呼び出し元では
返ってきた値をそのまま
Biよりも小さいAiの個数として扱っています。
中身は基本的には二分探索と同じですが
異なる部分がいくつかあります。
まず、
引数で渡されるBiと同じ数字が、
Aiの配列の中にも可能性があるので
条件式にイコールをつける必要があります。
//valueが中間地点以下であれば上を中間地点に引き下げる if (value <= array[middle]) high = middle;
このイコールがないと
問題によってはいつまでも条件分岐の中に入ることができずに
無限ループしてしまいます。
では、等符号が入る位置を変えて
//中間地点よりもvalueが小さければ上を中間地点に引き下げる if (value < array[middle]) high = middle; //valueが中間地点以上であれば下を中間地点に引き上げる else low = middle + 1;
とするのはどうかというと
WAしてしまいました。
//中間地点よりもvalueが小さければ上を中間地点に引き下げる if (value < array[middle]) high = middle; //valueが中間地点以上であれば下を中間地点に引き上げる else low = middle;
としてもTLEしてしまうので
一番上で示した形でないとうまく答えが出ないようです。
このメソッドの想定としては
low=value或いはlowがvalueよりも一つ大きい値になっていると思います。
理由はlowが配列のindexだからです。
このメソッドの呼び出し元では
返ってきた値をそのまま
Biよりも小さいAiの個数として扱っているので
返ってくるlowのindexよりも
Biよりも小さい個数は一つ少ないことになります。
例えば、
low=3で返ってきた場合、
lowはindexなので個数としては0,1,2,3の4つないとおかしいですが
実際は3つで計算されるので
Aiのindexが3の値はBiよりも小さくない値であることになります。
これらを色々そろえるために
コード中の等符号の位置が決められていたり
「low = middle」だけでいいようにみえる場所に
+1の処理が入っていると思われます。
～よりも大きい数字の個数
次に
Biよりも大きい数字の個数が欲しい
Ciの個数を出す二分探索を考えます。
コードは以下です。
//引数 value=Bi array=Ciの配列
static long UpperBound(long value, long[] array)
{
//下は０でスタート
var low = 0;
//上は配列の長さでスタート
var high = array.Length;
//highがlow以下になるまで探索を繰り返す
while (low < high)
{
//中間地点(index)
var middle = (high + low) / 2;
//中間地点よりもvalueが小さければ下を中間地点に引き下げる
if (value < array[middle]) high = middle;
//valueが中間地点以上であれば下を中間地点に引き上げる
else low = middle + 1;
}
return low;
}
まず引数は
long value = Bi
long[] array = Ciの配列
です。
呼び出し元では
Nから返ってきた値を引いたものを
Biよりも大きいCiの個数として扱っています。
そのため、
このメソッドから返しているのはindexなのに
呼び出し元ではBi以下の個数として扱われているので
lowに入っているindexは
Biよりも一つ大きいほうにずれたものであることが分かります。
また先の
Biよりも小さいAiの個数を求めるメソッドとは
条件式の等符号が入っている位置が違っています。
これは欲しい個数が異なるものであることに依る
違いだと思われます。
例えば
AiもCiも以下の同じ配列であるとします。
1 2 3 4 5 6 7
このときBiが「4」だとすると
Aiの個数を求めるメソッドは
4より小さい数の個数3を返しますが
（実際にはindexなのでlowが指しているのは4（low=valueのパターン））
Ciの個数を求めるメソッドは
Bi以下の値の個数を返すので4を返し、
（実際にはindexなのでlowが指しているのは5（valueよりもlowが一つ大きいパターン））
Biよりも大きい値は7－4＝3と求めることができます。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
//値が小さい順に並び替え
var A = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();
var B = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();
var C = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).OrderBy(x => x).ToArray();
//答えを格納する変数
var ans = 0L;
//Biに対する Biよりも小さいAiの個数と Biよりも大きいCiの個数を求めて
//各Biに対する祭壇の種類数を出して 足していく
//各Biについて種類数を出したいのでN回まわす
for (int i = 0; i < N; ++i)
{
//Biよりも小さいのAiの個数
var a = LowerBound(B[i], A);
//Bi以下のCiの個数
var c = UpperBound(B[i], C);
//各Biに対する祭壇の種類数を出して 足す
ans += a * (N - c);
}
Console.WriteLine(ans);
}
//引数 value=Bi array=Ciの配列
static long UpperBound(long value, long[] array)
{
//下は０でスタート
var low = 0;
//上は配列の長さでスタート
var high = array.Length;
//highがlow以下になるまで探索を繰り返す
while (low < high)
{
//中間地点(index)
var middle = (high + low) / 2;
//中間地点よりもvalueが小さければ下を中間地点に引き下げる
if (value < array[middle]) high = middle;
//valueが中間地点以上であれば下を中間地点に引き上げる
else low = middle + 1;
}
return low;
}
//引数 value=Bi array=Aiの配列
static long LowerBound(long value, long[] array)
{
//下は０でスタート
var low = 0;
//上は配列の長さでスタート
var high = array.Length;
//highがlow以下になるまで探索を繰り返す
while (low < high)
{
//中間地点(index)
var middle = (high + low) / 2;
//valueが中間地点以下であれば上を中間地点に引き下げる
if (value <= array[middle]) high = middle;
//中間地点よりもvalueが大きければ下を中間地点に引き上げる
else low = middle + 1;
}
return low;
}
}
