競技プログラミングをやってみた話2

## Why？

[こちら](https://qiita.com/shitikakei/items/a98d208cbdf80ecbf372)の続編です。
随時更新していって、ある程度まできたら次の記事に移ります。

最終更新日: 1/19

## 標準入力

問題で与えられた数値などを受け取る方法。
作法のようなものだと思って脳死で覚える。

```python

# こういうデータを受け取りたい場合
1
2 3
test

# こう書く
N = int(input()) # N = 1
b,c = map(int,input().split()) # b = 2, c = 3
S = input() # S = test

# こういうデータを受け取りたい場合

3 2
1 2
5 5
-2 8

# こう書く

N, X = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]

```

## やった問題

### [B - Cakes and Donuts](https://atcoder.jp/contests/abc105/tasks/abc105_b)

<details><summary>書いたコード</summary><div>

```python

# ケーキやドーナツを買って合計Nドルちょうどになるパターンがあるかどうか調べたい

N = int(input())
cake = 4
donuts = 7
ans = "No"

# Nがそれぞれケーキかドーナツの値段の倍数であればケーキかドーナツどちらかを買い続ければNドルになる
if N % cake == 0 or N % donuts == 0:
    print('Yes')
    exit()

# 上記の条件で成り立たなかった場合全探索
# ポイントはindexを分けること
for i in range(N):
    # 先にケーキのインデックスを固定してドーナツの個数を変化させて条件に合致するか調べる
    for j in range(N):
        if N == (i*cake + j*donuts):
            ans = "Yes"
            break
print(ans)


```

</div></details>

### [B - 81](https://atcoder.jp/contests/abc144/tasks/abc144_b)

<details><summary>書いたコード</summary><div>

```python

# 与えられた整数が九九の範疇に収まるか調べたい

N = int(input())
ans = 'No'

# 九九なのでrange(1,10)の試行で実現できる
for i in range(1,10):
    for j in range(1,10):
        if N == (i*j):
            ans = 'Yes'
            break
print(ans)

N = int(input())
ans = 'No'

def calculate(x,y):
  sample = x * y
  return sample

for i in range(1,10):
  for j in range(1,10):
    result = calculate(i,j)
    if result == N:
      ans = 'Yes'
print(ans)


```

</div></details>

### [B - Good Distance](https://atcoder.jp/contests/abc133/tasks/abc133_b)

<details><summary>書いたコード</summary><div>

```python

# D次元にあるN個の座標同士の距離が整数になるものがいくつあるか

import math
N, X = map(int, input().split())
# 与えられた座標を取得する
l = [list(map(int, input().split())) for _ in range(N)]
count = 0


def test(x, y):
    d = 0
    # X次元の数だけ各座標の軸の距離を計算したい ex. X=2の場合、各座標のX軸同士とy軸同士で以下の計算をする
    for i in range(X):
        # lから座標を取り出し、さらにX次元の数だけ比較する。例えばX=2であるなら最初はX軸同士で次にY軸同士を計算してループが終了する
        d += abs((x[i]-y[i]))**2
    # dの平方根を返す
    return math.sqrt(d)

# あえて1から始める
for j in range(1, N):
    # j = 1の場合、range(1)となり、t = 0を成立させられる
    for t in range(j):
        # 多次元配列のデータの取り出し方は以下の通り
        result = test(l[j], l[t])
        if result == int(result):
            count += 1
print(count)



# 多次元配列の場合の数値の取り出し方応用編
# ex. num_list　= [[1, 2], [5, 5], [-2, 8]]とした場合

# sample =  num_list[0] = [1,2]
# sample1 =  num_list[1] = [5, 5]
# sample[0] = 1　= num_list[0][0]
# 以下同じ理屈で取り出せる
# sample[1] = 2
# sample1[0] = 5
# sample1[1] = 5

```

</div></details>

### [B - Making Triangle](https://atcoder.jp/contests/abc175/tasks/abc175_b)

<details><summary>書いたコード</summary><div>

```python
# 与えられた辺の長さから三角形が成立する組み合わせが何組あるか

# モジュール
import itertools

N = int(input())
l = list(map(int,input().split()))
count = 0
# 昇順にソート
l.sort()
# itertools.combinations(iterable,int)で第2引数に指定した数での組み合わせを返してくれる
for i in itertools.combinations(l,3):
    # 三角形の条件は二辺の合計が残りの一辺より大きく、かつ今回は三辺の大きさがそれぞれ異なるという条件が付帯されているので以下の条件となる
    if i[0] + i[1] > i[2] and i[0] != i[1] != i[2]:
        count += 1
print(count)

N = int(input())
num_list = list(map(int, input().split()))
count = 0
num_list.sort()

for i in itertools.combinations(num_list, 3):
  if i[0] + i[1] > i[2] and i[0] != i[1] != i[2]:
    count += 1
print(count)

```

</div></details>

### [B - Some Sums ](https://atcoder.jp/contests/abc083/tasks/abc083_b)

<details><summary>書いたコード</summary><div>

```python

# 与えられた数字の桁同士を足して、条件を満たした数字の総和を求めたい

N,A,B = map(int,input().split())
new_list = []
# ある数字の桁の総和を表すには10で割った余りを足し続ければいい。
for i in range(1,N+1):
    # 試行する数字を保存
    index = i
    ans = 0
    # 0になるまで試行する
    while i > 0:
        # 余りを足す
        ans += i % 10
        # 10で割る
        i = i // 10
    # 条件を満たした場合、最初に保存した数字をリストに入れる
    if A <= ans <= B:
        new_list.append(index)
# リストの合計を出力
print(sum(new_list))


```

</div></details>

### [B - Palindromic Numbers](https://atcoder.jp/contests/abc090/tasks/abc090_b)

<details><summary>書いたコード</summary><div>

```python

# A以上B以下の整数のうち、回文数となるものの個数を知りたい

A,B = map(int,input().split())
count = 0

# 整数を文字列に変換してリストにし、逆順にしたものを比較すればいい
for i in range(A,B+1):
    sample = str(i)
    sample2 = list(reversed(str(i)))
    sample2 = ''.join(sample2)
    if sample == sample2:
        count += 1
print(count)


```

</div></details>

### [A - Digits Sum](https://atcoder.jp/contests/agc025/tasks/agc025_a)

<details><summary>書いたコード</summary><div>

```python

N = int(input())
ans = N

# Nを10で割った余りが0の場合、欲しい答えは10となるらしい
if N % 10 == 0:
    print(10)
    exit()
# それ以外の場合
for i in range(1,N):
    # 肝は整数A、Bの合計がNであるということは、B = N - Aであるということ
    A = i
    B = N - i
    sum1 = 0
    sum2 = 0
    while A > 0:
        sum1 += A % 10
        A //= 10
    while B > 0:
        sum2 += B % 10
        B //= 10
    if ans > sum1 + sum2:
        ans = sum1 + sum2
print(ans)


# 別解1 AとBそれぞれの各位の和の合計をリストに格納してそこから最小値だけ抽出する

for i in range(1, N):
    A = i
    B = N - i
    result1 = 0
    result2 = 0
    while A > 0:
        result1 += A % 10
        A = A // 10
    while B > 0:
        result2 += B % 10
        B = B // 10
    sum = result1 + result2
    new_list.append(sum)
print(min(new_list))

# 別解2 整数A、Bの合計がNであるとき、Aの各位の和とBの各位の和の合計の最小はNの各位の和に等しいというところから

# 文字列で数字を取得
num = input()

ans = 0
for i in range(len(num)):
    # 文字列として取得した整数は下記のようにして桁を取り出せるのであとはそれを足し続ければいい
    ans += int(num[i])

if ans == 1:
    print(10)
else:
    print(ans)


```

</div></details>

### [B - Digits](https://atcoder.jp/contests/abc156/tasks/abc156_b)

<details><summary>書いたコード</summary><div>

```python

# 整数をN進法に変換したい

# ある整数NをK進法に変換するにはNをKで割った余りを後ろから順に拾えばいいので、何回その処理ができるかカウントすればいい
N, K = map(int, input().split())
list = []
count = 0
while N > 0:
    count += 1
    # 問題とは関係ないがもし余りを記録しておく必要があればリストに格納しておく
    list.append(str(N % K))
    N = N // K
print(count)
# 以下は2・8・16進数への変換結果を表示したい場合
sample = int(''.join(list))
if K == 2:
    print(bin(sample))
elif K == 8:
    print(oct(sample))
elif K == 16:
    print(hex(sample))


```

</div></details>


## 現状の所感

このあたりから数学の知識と Python のライブラリの知識が必要になってきたように感じられる。
最初の2問は index を分けるということに気付けるかどうかが鬼門。
九九の方を先にやる方がこの発想には至りやすいのでわかりやすい。

3問目と4問目はいわゆる組み合わせの問題ですが、それをどうコードに置き換えるかが難しい。

3問目は多分数学が苦手な人や私のような競技プログラミング弱者にとって壁になるであろうタイプの問題。
ポイントは多次元配列を扱うということと、どうやって全探索をするかという点。
特に後者は普通にただの range()でやってしまうと out of index のエラーになってしまうのでそれを如何に防ぐのかというのがさっぱりわかりませんでした。
どちらも初見では不回答、3 周してなんとか少しは腹落ちした気がします。

4問目はさらに発展して与えられた入力から 3C2 を作り、条件を満たすものを探すというものでした。
itertools というライブラリが iterable から組み合わせを総当りで作ってくれるのでこれを利用して問いていきました。
あとは三角形の成立条件を覚えているかが鍵です。
私は覚えていなかったので初見ではできませんでした。

B - Some Sumsからは進数に関する問題。
基本的にはNをX進数に変換する場合は、Nを0になるまでXで割り続けた余りを拾っていくという形でできる。
さらにPythonの場合は2・8・16進数は組み込み関数で変換できるのでそれを使えば変換も行える。


## 参考

[Pythonでリストや文字列を逆順に並べ替え（reverse, reversed）](https://note.nkmk.me/python-reverse-reversed/)
[整数の性質｜n進法について](https://hibikore-tanren.com/notation-system/)