C - Modulo Summation
はじめに
競技プログラミング、AtCoder Beginner Contest 103
C - Modulo Summation
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
N個の正整数a1,a2,...,aNが与えられます。 非負整数mに対して、f(m)=(m mod a1)+(m mod a2)+...+(m mod aN)とします。 ここで、X mod YはXをYで割った余りを表します。 fの最大値を求めてください。
制約
・入力は全て整数である ・2≤N≤3000 ・2≤ai10^5
入力
入力は以下の形式で標準入力から与えられる。 N a1 a2 ... aN
出力
fの最大値を出力せよ。
解き方
以下を参考にしています。
https://img.atcoder.jp/abc103/editorial.pdf
f(m)を最大にすることを考える。
まず、
f(m)=0になるmの数は以下のように求められる。
m=a1*a2*…aN
例：入力例1 f(m)=0になるｍの数は m=3*4*6=72
このmから1を引いた数であれば
a1～aNまでの全ての数で
mを割ったときの余りが最大になる。
例：入力例1 余りが最大になるｍの数は m=3*4*6-1=71 71%3=2 71%4=3 71%6=5
f(m)=0になるmを求めると
かなり大きな数になってしまう、
かつ
f(m)=0になるmから1を引いたものをmにすれば
余りは常に最大になることが分かっていてmを求める必要がないので
a1～aNまでの数から1を引いたものを全て足せば答えが出る。
全体のコード
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 => Int32.Parse(x)).ToArray();
var ans = 0L;
for (int i = 0; i < N; ++i)
{
ans += A[i] - 1;
}
Console.WriteLine(ans);
}
}
C - All Green
はじめに
競技プログラミング、AtCoder Beginner Contest 104
C - All Green
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 それぞれの問題には、難易度に応じて点数が付けられています。 現在、1以上D以下のそれぞれの整数iに対して、100i点を付けられた問題がpi問存在します。 これらの p1+…+pD問 が AtCode に収録された問題のすべてです。 AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。 ユーザーの総合スコアは、以下の2つの要素の和です。 ・基本スコア: ユーザーが解いた問題すべての配点の合計です。 ・コンプリートボーナス: 100i点を付けられたpi問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナスci点を獲得します (1≤i≤D)。 AtCode の新たなユーザーとなった高橋くんは、まだ問題を1問も解いていません。 彼の目標は、総合スコアをG点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？
制約
・1≤D≤10 ・1≤pi≤100 ・100≤ci≤10^6 ・100≤G ・入力中のすべての値は整数である。 ・ci,Gはすべて100の倍数である。 ・総合スコアをG点以上にすることは可能である。
入力
入力は以下の形式で標準入力から与えられる。 D G p1 c1 : pD cD
出力
総合スコアをG点以上にするために解く必要のある最小の問題数を出力せよ。 なお、この目標は必ず達成可能である（制約を参照のこと）。
解き方
以下を参考にしています。
https://img.atcoder.jp/abc104/editorial.pdf
提出 #3149305 - AtCoder Beginner Contest 104
解き方の方針を考える
まず、
単純に点数が大きいほうから考えていけば
少ない問題数でGを超える得点を出せるように見えますが
コンプリートボーナスがあるので
この考え方では解けません。
次に
配点ごとの組み合わせを全て試すことを
考えますが
時間的制約に引っかかってしまうので
これも難しいです。
そこで、
制約の中で一番
数が小さいものを探します。
すると、以下の制約に気づきます。
・1≤D≤10
上の制約から
点数の種類は1以上10以下しかないことが分かったので
これを中心に解き方を考えてみます。
すると、
点数の取り方には以下の特徴があることに気づきます。
① 点数の種類（100i点）の中で、
解く問題数が中途半端な数になるものが存在したとしても一つだけである、
それ以外の点数の問題は全て解いてコンプリートボーナスをとるか、
一問も解かないかのどちらか
② ①で解く問題が中途半端な数になるのは、問題を全て解く点数を除いた中で、最も点数が高い問題
①について
一つの点数に対する問題を全て解けば、
コンプリートボーナスがもらえるので
中途半端に解くよりも多くの得点を得ることができます。
なるべく少ない問題数で目標に到達するには
コンプリートボーナスをとるほうが得なので
基本的には一つの点数に対する問題は全て解くことなり、
解かない点数の問題は一問も解かず、
中途半端に解く点数は一つだけになります。
②について
中途半端に解く問題はコンプリートボーナスをとれないので、
とれる点数は問題の点数だけです、
そのため、
全ての問題を解く点数を除いた中で
一番点数の高いものを選ぶことによって
少ない問題数で目標点数に到達することができます。
解き方を考える
上で考えた方針をもとに具体的な解き方を考えていきます。
上で導いた特徴をもとにすると各点数は
以下の3グループ（③はあれば）に分けられます。
①全て解いてコンプリート報酬までとる
②全く解かない
（③）中途半端に解く（コンプリート報酬はとらない）
この中で③は
①でコンプリート報酬までとった合計が
目標点数を超えていてかつ
最も少ない問題数で済んでいる場合は存在しないので
取り敢えず①と②を出す方法を考えます。
各点数を①と②のグループに分けたいので、
ここではbit全探索が使えることに気づきます。
bit全探索については以下の記事が分かり易いです。
lovedvoraklayout.hatenablog.com
bit全探索で選ばれたものは
①全て解いてコンプリート報酬までとる
のグループに入れることにして
解いた問題数と
コンプリート報酬までとった点数を保存しておきます。
ここで、
保存した点数が目標点数まで到達して「いる」場合は、
今までの問題数の最小値と比べて
小さければ最小値として保存します。
保存した点数が目標点数まで到達して「いない」場合は
③に入れる点数のグループを考えます。
③の点数は
①全て解いてコンプリート報酬までとる
を除いて最も高いものです。
もしこの③の点数の問題数が足りずに
目標点数まで到達しなかった場合は
①②③の組み合わせが解答として正しくないので
飛ばして次の組み合わせを作ります。
問題数が足りて、
目標点数に到達した場合は
今までの問題数の最小値と比べて
小さければ最小値として保存します。
これを繰り返していくと、
問題数の最小値を出すことができます。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var dg = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var D = (int)dg[0];
var G = dg[1];
//問題数とボーナススコアを保存するリスト
var list = new List<long[]>();
for (int i=0;i<D;++i)
{
var pc= Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
list.Add(new long[2] { pc[0], pc[1] });
}
//解く問題数の最小値を更新していく変数
var ans = long.MaxValue;
//bit全探索
for (int i = 0; i < (Math.Pow(2, D)); i++)
{
var count = 0L;
var total = 0L;
for (int j = 0; j < D; j++)
{
if ((1 & i >> j) == 1) {
//「①全て解いてコンプリート報酬までとる」のグループに入るので
//問題数と点数を足す
count += list[j][0];
total += list[j][0] * 100 * (j + 1) + list[j][1];
}
}
//目標点数まで足りない場合
if (total < G)
{
//①に入るグループを除いた中で、最も点数の大きいものが対象になる
for (int j = D - 1; 0 <= j; --j)
{
//①のグループ（(1 & i >> j) == 1）に入らないもの
if ((1 & i >> j) == 0)
{
//目標を達成するために必要な問題数
var add = ((G-total)+((j + 1) * 100)-1) / ((j + 1) * 100);
//問題数が足りていたら
if (add <= list[j][0])
{
//問題数と点数を足す
count += add;
total += add * 100 * (j + 1);
//最小値を更新
if (G <= total) ans = Math.Min(ans, count);
}
break;
}
}
}//目標点数まで足りた場合は、問題数の最小値を更新
else ans=Math.Min(ans,count);
}
Console.WriteLine(ans);
}
}
D - XOR World
はじめに
競技プログラミング、AtCoder Beginner Contest 121
D - XOR World
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
f(A,B)をA,A+1,...,Bの排他的論理和としたとき、f(A,B)を求めてください。 ▼排他的論理和とは 整数c1,c2,...,cnのビットごとの排他的論理和yは、以下のように定義されます。 ・yを二進表記した際の2k(k≥0) の位の数は、 c1,c2,...,cnのうち、 二進表記した際の2kの位の数が1となるものが奇数個ならば1、偶数個ならば0である。 例えば、3と5の排他的論理和は6です(二進数表記すると: 011 と 101 の排他的論理和は 110 です)。
制約
・入力は全て整数である。 ・0≤A≤B≤10^12
入力
入力は以下の形式で標準入力から与えられる。 A B
出力
f(A,B)を計算し、出力せよ。
解き方
以下を参考にしています。
drken1215.hatenablog.com
qiita.com
f(A,B)（A,A+1,...,B）の排他的論理和
まず、
求めなければならない「f(A,B)（A,A+1,...,Bの排他的論理和）」は
「f(0,B) XOR f(0,A-1)（(0～Bの排他的論理和) XOR (0～(A-1)の排他的論理和)）」と書き換えることができます。
これは、
XORの性質としてX XOR X=0（Xは任意の数）というものがあり
f(0,B)とf(0,A-1)のXORをとることによって
両者で重なっているf(0,A-1)の部分が全て0になり（X XOR X=0）
最終的に残る部分がf(A,B)になるからです。
参考と具体例：
qiita.com
また、通常の足し算ならば
3～10までの和を求める場合
上と同じ形にすると
(1～10までの和)ー(1～3までの和)＝(3～10までの和)
というように
全体を足した数から不要な部分を引くことにより
欲しい部分が求まりますが
XORでは引くのではなく、
XORすることで答えが出すことができます。
「足し算」と「引き算」がどちらもXORであることも
XORの特徴らしいです。
参考と具体例：
drken1215.hatenablog.com
特徴を見つける
f(0,X)を書き出してみると以下のようになります。
| X | 2進数 | f(0,X) |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 10 | 11 |
| 3 | 11 | 0 |
| 4 | 100 | 100 |
| 5 | 101 | 1 |
| 6 | 110 | 111 |
| 7 | 111 | 0 |
| 8 | 1000 | 1000 |
| 9 | 1001 | 1 |
| 10 | 1010 | 1011 |
| 11 | 1011 | 0 |
| 12 | 1100 | 1100 |
| 13 | 1101 | 1 |
| 14 | 1110 | 1111 |
| 15 | 1111 | 0 |
上の書き出しから
Xが奇数のとき、f(0,X)は0と1を繰り返す
ということが分かります。
以上から、
以下のようにすればf(0,X)を求められることが分かります。
①Xが奇数のとき
(X+1)/2が偶数なら0、奇数なら1
すなわち、(X+1)/2%2
②Xが偶数のとき
Xが奇数のときの値は
上の式にXを入れるだけですぐ出せるので、これを利用する。
（Xが偶数のとき
f(0,X-1)とf(0,X+1)の値は上の式に入れるだけで
答えが分かる。）
出し方は以下の二通り
①f(0,X-1)を使う
②f(0,X+1)を使う
①f(0,X-1)を使う
f(0,X-1)はまだXとXORしていない状態なので
f(0,X)を出すには「X XOR f(0,X-1)」をする。
| X | 2進数 | f(0,X) |
|---|---|---|
| 3 | 11 | 0 |
| 4 | 100 | 100 |
Xを4とすると、
f(0,X-1)はf(0,3)すなわち0
f(0,4)は 0 XOR 100=100
②f(0,X+1)を使う
f(0,X+1)は余分に X+1 が XOR されている状態なので
f(0,X)を出すには「(X+1) XOR f(0,X+1)」をする。
| X | 2進数 | f(0,X) |
|---|---|---|
| 4 | 100 | 100 |
| 5 | 101 | 1 |
Xを4とすると、
f(0,X+1)はf(0,5)すなわち1
f(0,4)は 1 XOR 101=100
※XORは引き算もXOR
下のコードでは①を用いています。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Damondai
{
static void Main()
{
var ab = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var A = ab[0];
var B = ab[1];
//f(A,B)をf(0,B)^f(0,A-1)に変形
var ans = Solve(A - 1) ^ Solve(B);
Console.WriteLine(ans);
}
static long Solve(long num)
{
//奇数の場合
if (num % 2 == 1) return Calc(num);
//偶数の場合
else
{
//0なら0を返す
if (num <= 0) return 0;
//Xが偶数のとき f(0,X)=X^(X-1)
return num ^ Calc(num - 1);
}
}
static long Calc(long num)
{
return (num + 1) / 2 % 2;
}
}
D - Decayed Bridges
はじめに
競技プログラミング、AtCoder Beginner Contest 120
D - Decayed Bridges
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
N個の島と M本の橋があります。 i番目の橋は Ai番目の島と Bi番目の島を繋いでおり、双方向に行き来可能です。 はじめ、どの2つの島についてもいくつかの橋を渡って互いに行き来できます。 調査の結果、老朽化のためこれら M本の橋は 1番目の橋から順に全て崩落することがわかりました。 「いくつかの橋を渡って互いに行き来できなくなった 2つの島の組 (a,b)(a<b) の数」を不便さと呼ぶことにします。 各i(1≤i≤M)について、i番目の橋が崩落した直後の不便さを求めてください。
制約
・入力は全て整数である。 ・2≤N≤10^5 ・1≤M≤10^5 ・1≤Ai<Bi≤N ・(Ai,Bi)の組は全て異なる。 ・初期状態における不便さは0である。
入力
入力は以下の形式で標準入力から与えられる。 N M A1 B1 A2 B2 ⋮ AM BM
出力
i=1,2,...,Mの順に、i番目の橋が崩落した直後の不便さを出力せよ。 答えが32bit整数型に収まらない場合があることに注意すること。
解き方
以下を参考にしています。
https://img.atcoder.jp/abc120/editorial.pdf
atcoder.jp
考える順序
最終的な出力は
全ての橋がある状態から
一つずつ橋が崩壊する順序に「不便さ」を
出していきますが
橋がある状態から一つずつ橋がなくなっていき
「不便さ」が増えていく状態を考えるよりも
橋がない状態から一つずつ橋が増えていき
「不便さ」が解消されていく状態を考える方が楽なので
最終的な出力とは逆に考えていきます。
後入れ先出しのStackに保存しておけば、
何もしなくてもStackに保存した順序と逆の順序で
出力してくれます。
橋が増えていく（不便さが減っていく）状態を考える
一番初めにすべての橋がない状態の「不便さ」は
以下のように出せます。
(N * (N - 1)) / 2
橋が一つもなくどの島にも行き来できない状態なので
橋の組み合わせの数がそのまま「不便さ」になります。
次に橋が増えていくときの「不便さ」について考えてみます。
これには2つのパターンが考えられます。
①行き来することが出来なかった島に橋がかかる
②もともと行き来することが出来た島に橋がかかる
①行き来することが出来なかった島に橋がかかる
例えば、島1,2,3,4が存在し
既に1,2には橋が架かっているとします。
ここにさらに、2と3の間に橋がかかった場合は
(1,3)(2,3)という行き来が出来なかった島の組み合わせが
新たに行き来できるようになるため
このパターンが当てはまります。
このとき「不便さ」は以下のようになります。
一つ前の「不便さ」をH、（Stackに入っている最新の値（Stack.Peek()））
橋が架かるグループのそれぞれの要素の数
（上の島1,2,3,4の例でいうと、
既に橋が架かっている「1,2」とかかっていない「3」の要素の数
すなわち「2」と「1」）をA,Bとおくと
H-A*B
となります。
②もともと行き来することが出来た島に橋がかかる
例えば、島1,2,3,4が存在し
既に1,2,3には「1-2-3」と橋が架かっているとします。
このとき行き来できる島は
(1,2)(1,3)(2,3)です。
ここにさらに、1と3の間に橋がかかった場合は
1 ─ 2 │／ 3
となり
もともと行き来できた島に橋がかかるだけで
新たに行き来できる島は増えないので
このパターンが当てはまります。
このとき「不便さ」は以下のようになります。
一つ前の「不便さ」をH、（Stackに入っている最新の値（Stack.Peek()））とおくと
新たに行き来できる島は増減せず
「不便さ」に変化はないので
H
となります。
「不便さ」の変化は①と②の2パターンしかないので
橋が架かるグループのそれぞれの要素の数A,Bが求められれば
「不便さ」を出していくことができます。
しかし、
単純に橋が架かるグループのそれぞれの要素の数A,Bを求めると
タイムアウトしてしまうので
効率的に求めることが必要になります。
橋が架かるグループのそれぞれの要素の数を求める
Union-Findと呼ばれるデータ構造を用いると
橋が架かるグループのそれぞれの要素の数A,Bを
効率的に求めることができます。
Union find(素集合データ構造)
Union-Find木の解説と例題 - Qiita
Union-Findの本来の形は
root : 枝の根(親)を返す関数
unite : 根(親)が同じ出ない二つの枝を併合する関数
same : 二つの枝が同じ根に属するかどうかを返す関数
などがありますが以下の解答ではこの形にしていません。
parentという配列とsizeという配列を用いて解いています。
parent[] : 枝の親を格納しておく配列
これが同じなら同じ親に属しているということになります。
島1,2,3,4があり、現在の橋の状態が
1 ─ 2 4 │／ 3
とするとparentには以下のように値が入っています。
配列番号に合わせているので、島の数とは-1ずれています。
また、親の数は常に繋がっている要素の中で一番小さいものとしています。
parent[0]=0（1の島の親は自分自身なので自分が入る）
parent[1]=0（2の島の親は1なので0が入る）
parent[2]=0（3の島の親は1なので0が入る）
parent[3]=3（4の島の親は自分自身なので自分が入る）
size[] : 枝の要素数を格納しておく配列
島1,2,3,4があり、現在の橋の状態が
1 ─ 2 4 │／ 3
とするとsizeには以下のように値が入っています。
配列番号に合わせているので、島の数とは-1ずれています。
また、親の数は常に繋がっている要素の中で一番小さいものとしています。
parent[0]=3（1の島の親は自分自身で、2と3が枝としてぶら下がっているので要素数は3）
parent[1]=1（2の島の親は1で、自分には何もぶら下がっていないので要素数は1）
parent[2]=1（3の島の親は1で、自分には何もぶら下がっていないので要素数は1）
parent[3]=1（4の島の親は自分自身で、自分には何もぶら下がっていないので要素数は1）
（この問題では、親の要素数のみを見て
判断していけばよい、
かつ
一度枝になってしまった島が親になることはないので
親以外のサイズは更新しなくても大丈夫そうでした。）
橋が架かる島の親をparent配列から取り出し、
親のもつ要素数をsize配列から取り出せば
「橋が架かるグループのそれぞれの要素の数」
が分かり、
問題を解くことができます。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Dmondai
{
static int[] parent;
static void Main()
{
var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
//島の数
var N = nm[0];
//橋の数
var M = nm[1];
//入力されるAi番目の島とBi番目の島を保存するリスト
var AB = new List<int[]>();
for (int i = 0; i < M; ++i)
{
var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
AB.Add(new int[2] { ab[0] - 1, ab[1] - 1 });
}
//Union-Find
//枝の要素数を格納しておく配列
var size = new long[N];
//枝の親を格納しておく配列
parent = new int[N];
//size[]とparent[]を初期化
for (int i = 0; i < N; ++i)
{
//全ての島にぶら下がる枝は、自分の島だけ
size[i] = 1;
//全ての島が自分が親
parent[i] = i;
}
//答えを格納するStack
var ans = new Stack<long>();
//橋が一つもかかっていない状態を格納
ans.Push(((long)N * ((long)N - 1)) / 2);
//橋が増えたときの「不便さ」の変化
for (int i = M - 1; 0 < i; --i)
{
//橋がかかるそれぞれの島の親を取得
var ab = AB[i];
var parent1 = GetParent(ab[0]);
var parent2 = GetParent(ab[1]);
//もし親が異なるならば
if (parent1 != parent2)
{
//「不便さ」が減る
ans.Push(ans.Peek() - (size[parent1] * size[parent2]));
//親を片方の親に統一
//以下の場合(parent2)の島の親が(parent1)になり、(parent2)は(parent1)にぶら下がる枝になる
parent[parent2] = parent1;
//親のサイズを更新
//(parent1)が(parent2)を吸収して大きくなったので(parent2)のサイズを足す
size[parent1] += size[parent2];
}
//親が同じなら「不便さ」に変化はないので直近の値を入れる
else ans.Push(ans.Peek());
}
//Stackに入れたのでそのまま出力すれば問題なし
for (int i = 0; i < M; ++i) Console.WriteLine(ans.Pop());
}
//親を返す関数
//ここで枝の親が変化していた場合、枝に更新がかかる
//例えば 1 2-3 という繋がりがmain関数の中で 1-2-3 へと変化したとすると
//main関数内で2の親は1であることが更新されるが、
//3の親は2の親のままになっているので、ここで正しい情報に更新する
static int GetParent(int num)
{
//配列の番号と親の番号が一致していれば親
if (parent[num] == num) return num;
//一致していなければ、親ではないので上にさかのぼる
else return parent[num] = GetParent(parent[num]);
}
}
D - Lazy Faith
はじめに
競技プログラミング、AtCoder Beginner Contest 119
D - Lazy Faith
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
東西方向に伸びる道路に沿ってA社の神社とB軒の寺が建っています。 西からi社目の神社は道路の西端からsiメートルの地点に、 西からi軒目の寺は道路の西端からtiメートルの地点にあります。 以下のQ個の問いに答えてください。 問i (1≤i≤Q): 道路の西端からxiメートルの地点から出発して道路上を自由に移動するとき 神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか？ (必要数を超えた数の寺社を通過してもよい。)
制約
・1≤A,B≤10^5 ・1≤Q≤10^5 ・1≤s1<s2<...<sA≤10^10 ・1≤t1<t2<...<tB≤10^10 ・1≤xi≤10^10 ・s1,...,sA,t1,...,tB,x1,...,xQはすべて異なる。 ・入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。 A B Q s1 : sA t1 : tB x1 : xQ
出力
Q行出力せよ。 i行目に問iへの答えを出力すること。
解き方
以下を参考にしています。
https://img.atcoder.jp/abc119/editorial.pdf
atcoder.jp
道路の西端からxiメートルの地点から出発して道路上を自由に移動するとき
神社一社と寺一軒を訪れるのに必要な最小の移動距離を考える。
Xiからの移動距離を最小にするにはどこを訪れればいいか
まずは神社で考えてみる。
訪れるのに最小の移動距離を出したいので
xiメートルの位置から訪れる可能性のある神社は
xiから東に進んで最も近い位置にある神社、
xiから西に進んで最も近い位置にある神社
のどちらかである。
西 ← 神社 神社 神社 Xi 神社 神社 → 東 ３ ２ １ ０ １ ２ ★ ★
上の図で言うと
Xiから西と東に
それぞれ1進んだ「★」がついている場所が
訪れる可能性のある場所である。
また、
上の神社の例では
西と東に進んだ最短距離の神社はどちらもXiから距離が「1」だが
この距離が例えば「1」と「2」のように異なっていたとしても
西と東でそれぞれ一つずつ、計2つの候補を考えておく必要がある。
それは、
神社だけではなく寺も訪れなければならないからである。
出力しなければいけない答えは
神社と寺を一つずつ訪れた際の最短距離なので
神社と同じように寺も西と東それぞれ最短距離のものに
訪れる可能性がある。
神社から考えると
寺が西と東、どちらのものに訪れれば
最短距離になるのか分からないので西と東の候補が必要
寺から考えると
神社が西と東、どちらのものに訪れれば
最短距離になるのか分からないので西と東の候補が必要
ということである。
神社の場合 西 ← 神社 神社 神社 Xi 神社 神社 → 東 ４ ３ ２ １ ０ １ ２ ３ ★ ★ ↑ ↑ 寺？ 寺？
寺の場合 西 ← 寺 寺 Xi 寺 → 東 ５ … ２ １ ０ １ ２ ３ ★ ★ ↑ ↑ 神社？ 神社？
訪れる可能性のある
神社の西と東でそれぞれ1つずつ、計2つ
寺の西と東でそれぞれ1つずつ、計2つの
組み合わせを考えると以下のようになる。
①Xi→西の神社→西の寺 ②Xi→西の神社→東の寺 ③Xi→東の神社→西の寺 ④Xi→東の神社→東の寺 ⑤Xi→西の寺→西の神社 ⑥Xi→東の寺→西の神社 ⑦Xi→西の寺→東の神社 ⑧Xi→東の寺→東の神社
この8つの中で距離が最短のものを出力すればよい。
西と東でXiから最短の神社と寺をどうやって求めるか
しかし、
ここで問題となるのは
どうやってXiから最短の神社と寺を求めるかである。
単にループを回すだけではタイムアウトするので
二分探索で高速に求める。
また、
二分探索で西と東のものをそれぞれ求める必要はなく
西か東、どちらかが求められれば
もう片方は次のインデックスとなるので
片方だけを求めればいい。
（例えば、
神社の位置を格納した配列を保存しておいて
Xiから西に進んで一番近い神社だけを二分探索で求め
仮にインデックスが「2」と返ってきたとき
Xiから東に進んで一番近い位置にある
神社のインデックスは「3」である。）
西 ← … 神社 Xi 神社 神社 … → 東 ｲﾝﾃﾞｯｸｽ … ２ ３ ４ … ★ ★
二分探索の方法については以下
ja.wikipedia.org
以下では、
Xiから西に進んだときに
最も距離の近い神社（寺）のindexを返すようにしている。
//二分探索
static long GetFirstIndex(long[] array, long startPlace)
{
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
//bottom,startPlace,topの並びになったらおしまい
while (bottom + 1 != top)
{
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
}
//西のindexが欲しいので左端を返す
return bottom;
}
引数は「long array, long startPlace」となっているが
これは
「long array」→神社（寺）の位置が入っている配列
「startPlace」→Xiの位置
である。
そして、まず
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
配列の長さが1以下ならば
神社（寺）は一つしかなく
必ずそこを訪れることになるので
決まりで「0」を返している。
次に
二分探索は探索範囲をだんだんと狭めていく
探索方法なので
一番初めは渡した配列を丸ごと探索範囲としている。
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
そして、whileで
「bottom + 1 != top」
すなわち
bottom,startPlace,topの並びになるまでループを回している。
この並びは
「西に進んだときに最も近い位置にある神社、Xi、東に進んだときに最も近い位置にある寺」
の並びである。
内部の動きはそのまま二分探索で
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
配列の中で中央を出して、
startPlace（Xi）が中央よりも大きければ
bottom（探索対象の左端）を中央にずらし、
startPlace（Xi）が中央よりも小さければ
top（探索対象の右端）を中央にずらしている。
これを繰り返すことに依って
範囲が段々と狭まり答えが出てくる。
最後は
Xiから西に進んだときに最も近い位置にあるindexが欲しいので
bottomを返している。
最短距離を出す
そして、
二分探索をして返ってきた
indexをもとにXiから東に進んだときに最も近い位置にあるindexを出し、
もう片方（先に神社を出していれば寺、そうでなければ神社）も
Xiから西に進んだときに最も近い位置にあるindexを取得して
それをもとにXiから東に進んだときに最も近い位置にあるindexを出し、
この4つから
全8パターンの中で最も最短距離で行けるものを出力する。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var abq = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var A = abq[0];
var B = abq[1];
var C = abq[2];
//神社
var shrineArray = new long[A];
//寺
var templeArray = new long[B];
for (int i = 0; i < A + B + C; ++i)
{
if (i < A + B)
{
if (i < A) shrineArray[i] = Int64.Parse(Console.ReadLine());
else templeArray[i - A] = Int64.Parse(Console.ReadLine());
}
else
{
//スタート地点
var startPlace = Int64.Parse(Console.ReadLine());
//スタート地点から西に進んだときに最も近い位置にある神社のインデックス
var shrineFirstIndex = GetFirstIndex(shrineArray, startPlace);
//スタート地点から西に進んだときに最も近い位置にある寺のインデックス
var templeFirstIndex = GetFirstIndex(templeArray, startPlace);
//答えを入れる変数を用意
var ans = long.MaxValue;
//神社の西と東、計2つ
for (int j = 0; j < 2; ++j)
{
//神社が1つしかないなら、2つ目については考えないのでcontinueする
if (shrineArray.Length <= 1 && j == 1) continue;
//寺の西と東、計2つ
for (int k = 0; k < 2; ++k)
{
//寺が1つしかないなら、2つ目については考えないのでcontinueする
if (templeArray.Length <= 1 && k == 1) continue;
//神社と寺の距離
var distance = Math.Abs(shrineArray[j + shrineFirstIndex] - templeArray[k + templeFirstIndex]);
//スタート地点から神社と寺、どちらから行く方が早いか
var fast = Math.Min(Math.Abs(startPlace - shrineArray[j + shrineFirstIndex]), Math.Abs(startPlace - templeArray[k + templeFirstIndex]));
//距離が短いほうを採用
distance += fast;
//もしここで出た距離が現在の最短距離として保存してあるものよりも
//小さかったらアップデートする
if (distance < ans) ans = distance;
}
}
Console.WriteLine(ans);
}
}
}
//二分探索
static long GetFirstIndex(long[] array, long startPlace)
{
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
//bottom,startPlace,topの並びになったらおしまい
while (bottom + 1 != top)
{
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
}
//西のindexが欲しいので左端を返す
return bottom;
}
}
C - Base -2 Number
はじめに
競技プログラミング、AtCoder Beginner Contest 105
C - Base -2 Number
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
整数Nが与えられるので、Nの−2進数表現を求めてください。 ここで、Sが Nの −2進数表現であるとは、以下を全て満たすことです。 ・Sは'0'および'1'のみからなる文字列である ・S='0'でなければSの先頭の文字は'1'である ・S=SkSk−1...S0とすると、S0×(−2)^0+S1×(−2)^1+...+Sk×(−2)^k=N が成り立つ なお、任意の整数 Mに対して Mの−2進数表現が一意に定まることが証明できます。
制約
・入力はすべて整数である ・−10^9≤N≤10^9
入力
入力は以下の形式で標準入力から与えられる。 N
出力
Nの−2進数表現を出力せよ。
解き方
以下を参考にしています。
AtCoder ABC 105 C - Base -2 Number (300 点) - けんちょんの競プロ精進記録
ARC105-C：Base -2 Number - 数学/競プロメモ
ABC105 参加記録 - ARMERIA
ARC105-C：Base -2 Number - 数学/競プロメモ
まず、
2進数を求めるときの方法を考えてみます。
以下の記事の考え方を用いています。
betrue12.hateblo.jp
2進数の各桁は以下のように決まります。
| 26 | 25 | 24 | 23 | 22 | 21 | 20 |
|---|---|---|---|---|---|---|
| 27で割った余りの有無 | 26で割った余りの有無 | 25で割った余りの有無 | 24で割った余りの有無 | 23で割った余りの有無 | 22で割った余りの有無 | 21で割った余りの有無 |
試しに10進数の9を2進数にしてみます。
| 割られる数 | 割る数 | 余りの有無 |
|---|---|---|
| 9 | 21 | 1 |
| 8 | 22 | 0 |
| 8 | 23 | 0 |
| 8 | 24 | 1 |
考え方は、余りがもしあれば
桁のbitを立てて
その数ぶんはもう「表示している」ということになるので
9から引いています。
そのため、
動きは以下のようになっています。
9%2^1=1 余りがあるので2^0の桁のbitを立てる 2^0の桁を立てたので9-(2^0)=8になる 8%2^2=0 余りがないので何も起こらない 8%2^3=0 余りがないので何も起こらない 8%2^4=8 余りがあるので2^3の桁のbitを立てる 2^3の桁を立てたので8-(2^3)=0になる
この2進数の考え方は-2進数でも同じように使うことができます。
| (-2)6 | (-2)5 | (-2)4 | (-2)3 | (-2)-2 | (-2)1 | (-2)0 |
|---|---|---|---|---|---|---|
| (-2)7で割った余りの有無 | (-2)6で割った余りの有無 | (-2)5で割った余りの有無 | (-2)4で割った余りの有無 | (-2)3で割った余りの有無 | (-2)-2で割った余りの有無 | (-2)1で割った余りの有無 |
先ほどの二進数と同じように
入力例1を-2進数に変換してみると以下のようになります。
入力例1
-9
| 割られる数 | 割る数 | 余りの有無 |
|---|---|---|
| -9 | (-2)1 | 1 |
| -10 | (-2)2 | 1 |
| -8 | (-2)3 | 0 |
| -8 | (-2)4 | 1 |
動きは以下のようになっています。
(-9)%(-2)^1=1 余りがあるので(-2)^0の桁のbitを立てる (-2)^0の桁を立てたので(-9)-((-2)^0)=-10になる (-10)%(-2)^2=2 余りがあるので(-2)^1の桁のbitを立てる (-2)^1の桁を立てたので(-10)-((-2)^1)=-8になる (-8)%(-2)^3=0 余りがないので何も起こらない (-8)%(-2)^4=8 余りがあるので(-2)^3の桁のbitを立てる (-2)^3の桁を立てたので(-8)-((-2)^3)=0になる
この動きをそのまま実装します。
全体のコード
using System;
using System.Collections.Generic;
using System.Linq;
class Cmondai
{
static void Main()
{
var N = Int64.Parse(Console.ReadLine());
//割る数にかけるための-2
const long constant = -2;
//割る数
var num = 1L;
//各桁を格納するためのStackを用意
var ans = new Stack<char>();
//Nが0の場合は(-2)進数も0になる
if (N == 0) ans.Push('0');
//Nの(-2)進数を求める
//Nが0になるまで、割って引くことを繰り返す
while (N != 0)
{
//余りがない
if (N % (num * constant) == 0)
{
//1が立たないので0
//Nに変化なし
ans.Push('0');
}
//余りがある
else
{
//bitに1が立つ
ans.Push('1');
//1が立つのでその分Nから数を引く
N -= num;
}
//次の割る数を作成
num *= (-2);
}
long count = ans.Count();
//保存しておいた各桁を出力
for (long i = 0; i < count; ++i) Console.Write(ans.Pop());
Console.WriteLine();
}
}
C - Candles
はじめに
競技プログラミング、AtCoder Beginner Contest 107
C - Candles
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
数直線上にN本のろうそくが置かれています。 左からi番目のろうそくは座標xiに置かれています。 ただし、x1<x2<...<xNが成り立ちます。 最初、どのろうそくにも火が付いていません。 すぬけ君は、N本のうちK本のろうそくに火を付けることにしました。 今、すぬけ君は座標0にいます。 すぬけ君は、数直線上を左右に速度1で移動することができます。 また、自分と同じ座標のろうそくに火を付けることができます。 このとき、火を付けるのに掛かる時間は無視できます。 K本のろうそくに火を付けるのに必要な最小の時間を求めてください
制約
・1≤N≤10^5 ・1≤K≤N ・xiは整数である。 ・|xi|≤10^8 ・x1<x2< ... <xN
入力
入力は以下の形式で標準入力から与えられる。 N K x1 x2 ... xN
出力
K本のろうそくに火を付けるのに必要な最小の時間を出力せよ
解き方
以下を参考にしています。
https://img.atcoder.jp/arc101/editorial.pdf
atcoder.jp
K本のろうそくに火をつける時間を最小にしようとすると
ろうそくの並びが連続している箇所につけることになります。
ろうそくのK個連続した並びを全て列挙すると
N-K+1通りになり全探索が使えそうなので
ループで列挙していくことにします。
ループの中の処理を考えます。
開始地点の座標は0であることが決まっているので、
Kを仮に3とし、
火をつけるろうそくを「A,B,C」とすると
ろうそくのつけ方は以下の2パターンになります。
①0→A→B→C ②0→C→B→A
ここで出したろうそくをつけるのにかかる時間を
保存しておき、
後で最小値を出せばそれが答えになります。
（もしくは常に最小値を保存）
全体のコード
using System;
using System.Collections.Generic;
using System.Linq;
class Cmondai
{
static void Main()
{
var nk = Console.ReadLine().Split(' ').Select(value => Int32.Parse(value)).ToArray();
var N = nk[0];
var K = nk[1];
//N個のろうそくのうち、連続したK個の組み合わせの個数
var count = N - K + 1;
var x = Console.ReadLine().Split(' ').Select(value => Int64.Parse(value)).ToArray();
//かかる時間を保存
var cost = new List<long>();
//ろうそくK個の組み合わせの数ぶん、ループ
for (int i = 0; i < count; ++i)
{
//K個のろうそくで、右端から左端までかかる時間
var l = Math.Abs(x[i] - x[i + K - 1]);
//0→左端…
//左端から0までの時間を足して、リストに保存
cost.Add(Math.Abs(x[i]) + l);
//0→右端…
//右端から0までの時間を足して、リストに保存
cost.Add(Math.Abs(x[i + K - 1]) + l);
}
//最も時間の短いものが答え
var ans = cost.Min();
Console.WriteLine(ans);
}
}
