# 競プロ講習会第11回 Web資料

## ◎第11回の参加方法について

今回は AtCoder Problems を使用します。
分からない点などございましたら、質問してください。

#### ◎問題セット

https://kenkoooo.com/atcoder/#/contest/show/d1505366-b008-409c-8b2f-1ebffa7beff4

#### ◎公式解説

##### 1問目
https://atcoder.jp/contests/abc178/editorial/103

##### 2問目
https://atcoder.jp/contests/abc183/editorial/283

##### 3問目
https://atcoder.jp/contests/abc181/editorial/245

##### 4問目
https://img.atcoder.jp/abc106/editorial.pdf

##### 5問目
https://img.atcoder.jp/keyence2020/editorial.pdf

##### 6問目
https://img.atcoder.jp/data/agc/002/editorial.pdf

##### 7問目
https://img.atcoder.jp/data/agc/006/editorial.pdf

##### 8問目
https://img.atcoder.jp/dwacon6th-prelims/editorial.pdf

## ◎ヒント・補助解説

### ◎1問目:　A.Not

:::spoiler **◎プログラミング完全初心者の方へ**
以下の「アルゴ式」の「入力を受け取る」の章に先に取り組んでみましょう。
https://algo-method.com/tasks
標準入力2-4 まで終えれば、この問題にこたえるための知識は充分に揃います。
:::

:::spoiler **◎ヒント1**
標準入出力と条件分岐さえ出来れば解くことができます。
心配な方は、上の「プログラミング完全初心者の方へ」の項を見てみましょう。
:::

:::spoiler **◎解説**
https://atcoder.jp/contests/abc178/editorial/103
:::

### ◎2問目:　A.ReLU

:::spoiler **◎ヒント1**
1問目を条件分岐で解いた方には、もう解くための道具は全部そろっているはず！！
ぜひ見比べながら自力で解いてみてください。
:::

:::spoiler **◎解説**
https://atcoder.jp/contests/abc183/editorial/283
:::

### ◎3問目:　B.Trapezoid Sum

:::spoiler **◎ヒント1**

1,2問目と違い、入力の個数が一定ではありません。
pythonでは、以下のようにすれば入力を受け取ることができます。

N = int(input())

# ここに前処理を書く

for i in range(N):
    A,B = map(int,input().split())
    
    #ここに処理を書く

また、C++では以下のように入力を受け取ることができます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    
    // ここに前処理を書く
    
    for (long long i = 0; i < N ; ++i){
        long long A,B;
        cin >> A >> B;
        // ここに処理を書く
    }
}

:::

:::spoiler **◎ヒント2**
合計を保存しておく変数 $ans$ を用意しておき、そこに足し合わせていきましょう。
:::

:::spoiler **◎ヒント3**
$A+(A+1)+(A+2)+ ... + (B-1) + B$ を、ループで計算すると計算が遅すぎるので、TLE(実行制限時間超過)になります。
数学の力で高速化しましょう。
:::

:::spoiler **◎ヒント4**
C++を使用している方は、オーバーフローに気を付けましょう。
int型では無くて、long long 型を使用することで解決できます。
:::

:::spoiler **◎解説**
https://atcoder.jp/contests/abc181/editorial/245
:::

### ◎4問目　C. To Infinity

:::spoiler **◎ヒント1**
$S$は桁数が非常に大きいので、文字列として受け取りましょう。
:::

:::spoiler **◎ヒント2**
本当に5000兆回操作するプログラムを書いてはいけません。
勿論書くことはできますが、実行が終わるまでに寿命が来てしまうことは必至です。
:::

:::spoiler **◎ヒント3**
左から $10^{18}$ 番目までの文字しか聞かれない事を利用し、問題を「言い換え」ましょう。
:::

:::spoiler **◎解説**
https://img.atcoder.jp/abc106/editorial.pdf
3ページ目にあります。
:::

### ◎5問目　C. Subarray Sum

:::spoiler **◎ヒント1**
一見すると難問です。
しかし、制約を見ると…？
:::

:::spoiler **◎ヒント2**
$K$ が $N$ 以下なので、気が付けば非常に簡単です。
:::

:::spoiler **◎解説**
https://img.atcoder.jp/keyence2020/editorial.pdf
4ページ目に書いてあります。
:::

### ◎6問目　C. Knot Puzzle

:::spoiler **◎ヒント1**
まず、ほどくことが可能かどうかを判定しましょう。
:::

:::spoiler **◎ヒント2**
判定問題が解ければ、後はコードを書く能力が試されます。
:::

:::spoiler **◎解説**
https://img.atcoder.jp/data/agc/002/editorial.pdf
2ページ目にあります。
:::

### ◎7問目　B. Median Pyramid Easy
::: spoiler **◎ヒント1**
パズル系問題です。実際に手を動かして書いてみよう！！
:::

:::spoiler **◎解説**
https://img.atcoder.jp/data/agc/006/editorial.pdf
1ページ目の下半分に書いてあります。
:::

### ◎8問目　E.Span Covering
上級者向けの超難問なので、ヒントはありません。

::: spoiler **解説**
https://img.atcoder.jp/dwacon6th-prelims/editorial.pdf
5ページ目に書いてあります。
:::