2020-04-13

listの使い方　C++

値の追加、削除が高速にできるlistというSTLライブラリがあるらしいので使い方をまとめた。

まずはlistヘッダをincludeする。

#include<list>

(1)宣言

「list<型名>リスト名」で宣言する。
[例]Aという名前のint型のlistを作る。

list<int>A;

(2)末尾に値を追加

「リスト名.push_back(追加する値)」で追加する。
[例]Aに0から4までの数値を追加する。

for (int i = 0; i < 5; i++) {
	A.push_back(i);
}

Aは今{0,1,2,3,4}となっている。

(3)先頭に値を追加

「リスト名.push_front(追加する値)」で追加する。
[例]Aに10から14までの数値を追加する。

for (int i = 10; i < 15; i++) {
	A.push_front(i);
}

Aは今{14,13,12,11,10,0,1,2,3,4}となっている。

(4)イテレータの宣言

イテレータとはlist内の値が何番目かを表す変数である。
今後の操作でイテレータが必要になるので宣言する。
「list<リストの型名>::iterator イテレータ名」で宣言する。
[例]Aに対してitrという名前のイテレータを宣言する。

list<int>::iterator itr;

(5)K番目（0-index)の値を削除

「イテレータ名 = リスト名.begin();
　for (int i = 0; i < K; i++) {
　　　イテレータ名++;
　}
　イテレータ名=リスト名.erase(イテレータ名);」
でK番目の値を削除できる。
[例]Aの３番目の値(11)を削除する。

itr = A.begin();
for (int i = 0; i < 3; i++) {
	itr++;
}
itr=A.erase(itr);

Aは今{14,13,12,10,0,1,2,3,4}となっている。
なお、削除の前後でイテレータの値は変化しない。

(6)K番目の要素の直前に値を挿入する。

「イテレータ名 = リスト名.begin();
　for (int i = 0; i < K; i++) {
　　　イテレータ名++;
　}
　リスト名.insert(イテレータ名,挿入する値);」
で挿入できる。
[例]Aの5番目の値(1)の直前に100を挿入する。

itr = A.begin();
for (int i = 0; i < 5; i++) {
	itr++;
}
A.insert(itr, 100);

今Aは{14,13,12,19,0,100,1,2,3,4}となっている。
なお、挿入と同時にイテレータの値は1増えている。

(7)要素の出力

[例]Aの全要素を出力する。

for (itr = A.begin(); itr != A.end(); itr++) {
	cout << *itr << ' ';
}

出力結果
14 13 12 10 0 100 1 2 3 4

(8)その他の機能

A.pop_front();

先頭の値を削除

A.pop_back();

末尾の値を削除

2020-02-20

ARC004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

問題

https://atcoder.jp/contests/arc004/tasks/arc004_2

<問題概要>

平面上に0～N番のN+1個の点がある。i番目の点とi+1番目の点の距離はd[i]である。0番目の点とN番目の点の距離の最大値と最小値を求めよ。

<問題読み替え>

N個の棒がある。これらをつなげた端と端の距離の最大値と最小値を求めよ。

<解法>

d[i]の総和をsum、d[i]の最大値をM1、２番目に大きい値をM2とする。

また、M1を抜いたd[i]の総和をsum'=sum-M1とする。

(1)最大値

まっすぐにのばせば最大になるのは明らかなので最大値はsum

(2)最小値

(ⅰ)M1>sum'の時

どう頑張っても最小値はM1-sum'=2*M1-sumより小さくならないので最小値は2*M1-sum

(ⅱ)M1<=sum'の時

端と端がくっついて最小値は0になりそうだがこれを証明する。

(端がくっつく条件はM1<=sum'であることを証明する)

まず、端がくっつく条件にd[i]の順番は関係ない。

なぜなら棒をベクトルとして考えると端がくっつくとはベクトルの総和が0であるということであり、このことは棒の順番を変えても成り立つからである。ここでM1の棒を抜いた棒の集合の端と端の距離の最大値と最小値を考える。この棒の集合を2グループに分けてそれらをつなげた棒Aと棒Bを作る。Aの長さをa,Bの長さをbとする。次の方法で分けることでabs(a-b)<=M2　①

とすることができる。

(分け方)

M1を抜いたd[i]をsortして、小さい順にA,Bに交互に振り分ける。

これでabs(a-b)<=M2となった。AとBのなす角をθとするとこれらの端と端の距離はD=(a^2+b^2-2*a*b*cosθ)^(1/2)

-1<=cosθ<=1より

abs(a-b)<=D<=a+bとなる。

Dは連続なのでabs(a-b)<=M1<=a+bを満たせばすべての棒を使ったときに端がくっつく。①と、M2<=M1よりabs(a-b)<=M1は常に満たしているので端がくっつく条件はM1<=a+b=sum'(証明終)

答え

最大値　sum

最小値　max(0,2*M1-sum)