競技プログラミングでdcを使う(2/?)

[1](https://qiita.com/shogo314/items/abdf5e8e9e213bafe837) **2** [3](https://qiita.com/shogo314/items/6838b0beb84f911f0515) [4](https://qiita.com/shogo314/items/a7b6668602bb976ef940) 5(執筆中)

# はじめに
ここではdcの基本的な考え方であるスタックについて勉強していきましょう。
スタックというのはデータを上に積んでいって、それを上から取り扱うような構造をいいます。
1ページ目ではスタックについて触れずに進めていましたが、スタックを理解するために、いったん1ページ目の内容は忘れて読み進めてください。
# スタックの扱い方

```
2 13
```
![b02_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/581f1d77-b7d7-2bcc-c4f3-ee5a46443c6a.png)

数字を書くとその数字がスタックに積まれます。数字同士はスペースで区切ってください。
***

|入力|5 3<br> 9|
|:-:|:-|

```
??
```

![b02_02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/c527ea92-e209-5405-545c-74b9f98dd207.png)

「?」で数字を読み込むと前から順にスタックに積まれていきます。
「?」は一行だけ読み込みます。


***

```
6 8pn
```

|出力|8<br>8|
|:-:|:-|

![b02_03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/0ed1efb6-1f89-7ffd-e727-6efbf8be2383.png)
「p」は一番上の値に改行を付けて出力します。
「n」は一番上の値を取り出し、改行を付けずに出力します。
# 計算のコマンド
1ページ目では計算に「+」「-」「*」「/」「%」「^」が使えると紹介しましたが、実際にスタックがどうなっているかを見ていきましょう。この6つは2つの値を取り出し、その計算結果をスタックに積むという操作をしています。

```
6 8+
```

![b02_04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/dc996cfa-2544-3e12-f0fa-82689d006371.png)
$6 + 8$を計算します。

***

```
8 2-
```

![b02_05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/bbe6e5e4-1663-01a6-5cf3-d71d549283e9.png)
$8 - 2$を計算します。

***

```
3 4*
```

![b02_06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/8afd6a70-dd23-f4dc-4171-87df6bef1a79.png)
$3 \times 4$を計算します。

***

```
11 4/
```

![b02_07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/b487d6fc-8a72-917c-798b-7e48833db05b.png)
$11 \div 4$を計算します。
整数の割り算は切り捨てて整数が答えになる。

***

```
11 4%
```

![b02_08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/ac089c4f-2062-861d-349e-6d9525e38383.png)
$11 \div 4$の余りを計算します。

***

```
3 2^
```

![b02_09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/3d619750-aaa1-cabc-0bdc-7d9bc24afdc4.png)
$3^2$を計算します。
# 実際の問題
1ページ目で扱った問題を見ていきましょう。
[ABC004](https://atcoder.jp/contests/abc004/tasks/abc004_1)

|入力|1000|
|:-:|:-|

```
?2*p
```

|出力|2000|
|:-:|:-|

![a004_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/4e07538a-771b-d0b7-a8a8-686998ea9bf4.png)

$1000 \times 2$を計算します。
***
[ABC009](https://atcoder.jp/contests/abc009/tasks/abc009_1)

|入力|2|
|:-:|:-|

```
?1+2/p
```

|出力|1|
|:-:|:-|

![a009_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/e28ec43b-0168-6848-76c1-4f42181e99d0.png)

$(2+1) \div 2$を計算します。
# 複数のスタックを用いる
他の問題も見ていきましょう。
[ABC001](https://atcoder.jp/contests/abc001/tasks/abc001_1)

|入力|15<br>10|
|:-:|:-|

```
??-p
```

|出力|5|
|:-:|:-|

![a001_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/ac5c34ba-1a70-bd9e-f07d-87c33b885b2d.png)

***

[ABC017](https://atcoder.jp/contests/abc017/tasks/abc017_1)

|入力|50 7<br>40 8<br>30 9|
|:-:|:-|

```
?*?*?*++A/p
```

|出力|94|
|:-:|:-|

![a017_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/5501724b-f9c5-c06a-645d-ec5fda9d2f75.png)

$(50\times7+40\times8+30\times9)\div10$を計算します。
前述しましたが、「A」は「10」と解釈されます。
#他の演算子
「~」は割り算をして商と余りをスタックに積みます。

[ABC023](https://atcoder.jp/contests/abc023/tasks/abc023_a)

|入力|23|
|:-:|:-|

```
?A~+p
```

|出力|5|
|:-:|:-|

![a023_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/30c2baa7-3eed-32e9-8dff-13d8a7548d27.png)

この問題のためにあるようなコマンドですね。

***
「|」はべき剰余を計算します。

```
5 2 7|
```

![b02_10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/1f1439de-b9a0-7d39-3343-e223726a5f19.png)

$5^2$を$7$で割った余りを計算しています。
***
「v」はルートを計算します。桁数には気をつけるようにしましょう。

```
Bv
```

![b02_11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1327735/fad564f8-17be-6c1c-b101-b48d2a4c88e2.png)

$\sqrt{11}$を計算しています。
数字が負のときは、なにも積まないので、ただ一番上のデータが消えます。
# おわりに
ここまでの知識で解ける問題があるので[こちら](https://qiita.com/shogo314/items/fff4be1573d2f86dba2a#%E8%A4%87%E6%95%B0%E3%81%AE%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%82%92%E7%94%A8%E3%81%84%E3%82%8B)の「複数のスタックを用いる」の箇所にある問題を解いてみましょう。
次からは、コマンドを勉強していきましょう。

#
[1](https://qiita.com/shogo314/items/abdf5e8e9e213bafe837) **2** [3](https://qiita.com/shogo314/items/6838b0beb84f911f0515) [4](https://qiita.com/shogo314/items/a7b6668602bb976ef940) 5(執筆中)