はじめてのプロコンメモ(その3)

Python3で挑むにあたり忘れないようにメモ書きを残しておく
[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
を類題も含めてといた記録のメモ

# 標準入力例

```python
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
b, c = map(int, input().split())
# 文字列の入力
s = input()
# 出力
print("{} {}".format(a+b+c, s))
```

# 練習１
[ABC 081 B - Shift Only]()

## 問題

```
黒板に 
N個の正の整数 
A1,...,ANが書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

黒板に書かれている整数すべてを，2で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．
```

## 入力例

```
3
8 12 40
```

## 解答
これは自力で解けなかったので
解答を見ながら解説を加えながらといた。

```python

# 整数の入力
length = int(input())
numbers = map(int, input().split())
#リストを使うと下記のように出力される。
#print(list(numbers))
#[5, 6, 8, 10]

#これをこのままmap関数で一つずつ処理をしてあげたい

#引数が配列、何回処理できるか返す関数を作る 
def how_many_times_divisible(n):
	#回数をまずは０で定義
	count = 0
    #一つずつ処理される入ってきた値が割り切れなくなるまで
	while n % 2 == 0:
		#2でわる
		n = n / 2
		#回数を一上げる
		count = count + 1
    #割れなくなったら返す
	return count
  
#最大で何回操作を行うことができるかなので、帰ってきた値の中で一番小さい数を出力する
ans = min(map(how_many_times_divisible,numbers))

#答え
print(ans)
```

## 課題

- pythonのmap関数のことをわかっていなかった
- 最後のminが便利すぎる思いつかない
- 関数は難しく考えずに何回割れるかだけを考えると良い


# 練習2
[ABC 068 B - Break Number](https://atcoder.jp/contests/abc068/tasks/abc068_b)

```
高橋君は 2で割れる数が好きです。

正整数 Nが与えられるので、1以上 N以下の整数のうち、最も 
2で割れる回数が多いものを求めてください。答えは必ず1つに定まります。

なお、2で割っていき、何回あまりが出ずに割れるかを、2で割れる回数と呼ぶことにします。
```

## 入力例

```
7
```

## 作った解答

```python

# 整数の入力
numbers = int(input())
#　数に合わせてリストを作る
number_list = []
for num in range(numbers):
	number_list.append(num+1)

#引数が配列、何回処理できるか返す関数を作る 
def how_many_times_divisible(n):
	#回数をまずは０で定義
	count = 0
    #一つずつ処理される入ってきた値が割り切れなくなるまで
	while n % 2 == 0:
		#2でわる
		n = n / 2
		#回数を一上げる
		count = count + 1
    #割れなくなったら返す
	return count
  
#map(how_many_times_divisible,number_list))で最大何回割れるかをそれぞれ数えてリストにする
#print(list(map(how_many_times_divisible,number_list)))
#[0, 1, 0, 2, 0, 1, 0]
list_how_many_times_divisible = list(map(how_many_times_divisible,number_list))
#この中で一番大きい値の番号をだす
index_number = list_how_many_times_divisible.index(max(list_how_many_times_divisible))

#答えはインデックス番号と実際の値がずれるため+1をする
ans = index_number + 1
print(ans)
```

### 参考文献
最初に見つかった最大値のインデックスを取得する方法がわからなかったので調べた
https://hibiki-press.tech/learn_prog/python/max_min_index/586

# 練習３
[ABC 102 B - Maximum Difference](https://atcoder.jp/contests/abc102/tasks/abc102_b)

## 問題

```
長さ Nの整数列 Aが与えられます。 
Aの（添字の）異なる 2要素の差の絶対値の最大値を求めてください。
```

## 出力例

```
4
1 4 6 3
```

## 回答例

```python

# 整数の入力
numbers = int(input())
#２つ目の標準入力をいれる
# こんなかんじではいる[1, 4, 6, 3]
list_numbers = list(map(int, input().split()))

#maxの値を入れる
#最初は０で定義しておく
max = 0


# for文で回して一個ずつ確かめる
for number in range(numbers):
	
	for number2 in range(numbers):
		result = list_numbers[number]-list_numbers[number2]
        #絶対値なので０未満だったらマイナスつけておく
		if result < 0:
			result = -1*result
        #いままで出てきたどの結果よりも大きい値であればmaxを更新する
		if result > max:
			max = result

print(max)
```

## 課題

- テストは通ったけどfor文を二回使っているので計算量的によろしくない気がする
- 二回使わずに解く方法はないだろうか・・・・

# 練習3

[ABC 113 B - Palace]()

```
ある国で、宮殿を作ることになりました。
この国では、標高が xメートルの地点での平均気温は T−x×0.006度です。

宮殿を建設する地点の候補は N個あり、地点 iの標高はHiメートルです。
joisinoお姫様は、これらの中から平均気温がA度に最も近い地点を選んで宮殿を建設するようにあなたに命じました。
宮殿を建設すべき地点の番号を出力してください。
ただし、解は一意に定まることが保証されます。
```

## 入力例

```
2
12 5
1000 2000
```

## 解答

```python
# 宮殿を建設する地点の候補はN個
N = int(input())

# T気温の基準 A:理想の気温
T, A = map(int, input().split())

#それぞれの標高
heights = list(map(int, input().split()))

#理想の値を定義しておく
ideal = 1000
#場所の位置の番号を記録
place = 0


# for文で回して一個ずつ確かめる
for number in range(N):
	#平均気温を求める
	average_temperature = T - heights[number]*0.006
    
    #理想との絶対値の差はどれくらいか
	difference = average_temperature - A
	if difference < 0:
		difference = -1*difference
	
    #理想に最も近い地点はどれか　絶対値が一番小さい値はどれか
	if  difference < ideal:
      	#理想の場所の気温
		ideal = difference
        #理想の場所の番号
		place = number

#配列の番号と実際の番号がずれるため+1している
print(place+1)
```

# 練習4
[ABC 072 B - OddString](https://atcoder.jp/contests/abc072/tasks/abc072_b)

## 問題

```
英小文字からなる文字列 sが与えられます。前から数えて奇数文字目だけ抜き出して作った文字列を出力してください。 ただし、文字列の先頭の文字を1文字目とします。
```

## 入力例

```
atcoder
```

## 解答

```python

#文字列を取得する
strings = list(input())

#for文で奇数番目を取り出す
for number in range(len(strings)):
  if number % 2 == 0:
    #改行なしにする
    print(strings[number], end ="")
```

# 練習５
[ABC 053 B - A to Z String](https://atcoder.jp/contests/abc053/tasks/abc053_b)

## 問題

```
すぬけくんは文字列 sの連続した一部分(部分文字列という)を取り出して先頭が A であり末尾が Z であるような文字列を作ることにしました。 
すぬけくんが作ることのできる文字列の最大の長さを求めてください。
 なお，sには先頭が A であり末尾が Z であるような部分文字列が必ず存在することが保証されます。
```

## 入力例

```
QWERTYASDFZXCV
```

## 解答

```python
#文字列を取得する(QWERTYASDFZXCV)
strings = list(input())

#Aの一番小さいインデックス番号
place_smallest_A= 200000
place_largest_Z= 0

#for文で一番小さいインデックスのAを取り出す
for number in range(len(strings)):
  if strings[number] == "A":
    if number < place_smallest_A:
      place_smallest_A = number
      
#for文で一番大きいインデックスのZを取り出す
for number in range(len(strings)):
  if strings[number] == "Z":
    if number > place_smallest_A:
      place_smallest_Z = number

#A~Zの間でスライスする
ans = strings[place_smallest_A:place_smallest_Z+1]
#配列の長さを答える
print(len(ans))

```

# 練習6

[ABC 095 B - Bitter Alchemy](https://atcoder.jp/contests/abc095/tasks/abc095_b)

##問題

```
パティシエの赤木さんは、「お菓子の素」という粉のみを材料として 
N種類のドーナツを作ることができます。これらのドーナツはドーナツ 
1、ドーナツ2 、...、ドーナツNと呼ばれます。ドーナツ i(1≤i≤N)を 
1個作るには、お菓子の素miグラムを消費する必要があります。なお、0.5個など整数でない個数のドーナツを作ることはできません。

いま、赤木さんはお菓子の素をX
 グラム持っています。これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。ただし、来客の味の好みは様々なので、次の条件を守ることにしました。

N種類のドーナツそれぞれを少なくとも 1個は作る。
このとき、最大で何個のドーナツを作ることができるでしょうか？お菓子の素を使い切る必要はありません。また、この問題の制約のもとでは、条件を守ることは必ず可能です。
```

## 入力例

```
3 1000
120
100
140
```
## 私が作った解答

```python

# Number_of_donuts:ドーナッツのN個 gram_of_sweets:お菓子のもとXグラム
Number_of_donuts, gram_of_sweets = map(int, input().split())

#各ドーナッツに必要なグラムのリスト
list_gram = []

#最大作れるドーナッツの数(予め一個ずつはつくるからその数はいれておく)
count = Number_of_donuts

#ドーナッツの個数ごとに標準入力を受け付ける
for number in range(Number_of_donuts):
  #あとで計算しやすいのでIntにしておく
  list_gram.append(int(input()))
  
#一個は絶対作る必要があるのでとりあえず一回は引く
for number in range(Number_of_donuts):
  gram_of_sweets = gram_of_sweets - list_gram[number]
  
#ドーナッツの一番小さい使用量のやつで何個作れるかを計算する
while gram_of_sweets > min(list_gram):
  gram_of_sweets = gram_of_sweets - min(list_gram)
  count = count + 1
  
print(count)
```

なんかテストが通らない・・・ので模範解答を参照する

## 模範解答
全く無駄がない感じがすごい

```py
N, X = map(int, input().split())
m = []
for i in range(N):
  m.append(int(input()))
print(N + (X - sum(m)) // min(m))
```

## 課題
- リストのsumとminの使い方がわかっていなかった
    - 普通にリストをこれに入れればいいって便利すぎる
- 余剰の使い方
- 最後の計算の仕方がダメだった

## 書き直した解答

```python
# Number_of_donuts:ドーナッツのN個 gram_of_sweets:お菓子のもとXグラム
Number_of_donuts, gram_of_sweets = map(int, input().split())

#各ドーナッツに必要なグラムのリスト
list_gram = []

#最大作れるドーナッツの数(予め一個ずつはつくるからその数はいれておく)
count = Number_of_donuts

#ドーナッツの個数ごとに標準入力を受け付ける
for number in range(Number_of_donuts):
  #あとで計算しやすいのでIntにしておく
  list_gram.append(int(input()))

#絶対作る数はNumber_of_donuts,あとは余った粉で最大限つくればいい
print(Number_of_donuts+(gram_of_sweets - sum(list_gram)) // min(list_gram))

```