【Python・アンチパターン】多次元リストの初期化

多次元リストの初期化時に演算子*を利用すると、想定外の動きをするので、アンチパターンとして記載。

目的

初期化された多次元リストを生成する。

アンチパターン

演算子*を用いて、初期化された多次元リストを生成すると、想定外の挙動をする。

具体的な事象

# NG
b_list = [[0]]*3
print(b_list) #[[0],[0],[0]]
b_list[0].append(1)
print(b_list) #[[0,1],[0,1],[0,1]]

1. 演算子*を用いて、初期化された多次元リストを生成。

2. その後、生成されたリストの先頭要素だけに1を追加すると、同処理が何故か全要素に適用される。

解説

演算子*について

演算子*は、a. (数値, 数値)とb. (シークエンス, 整数)のように引数の型によって、以下のように作用が異なる。

1. (数値, 数値)：数値を共通の型に変換した後、掛け合わせた結果を返す。
2. (シークエンス, 整数)：シークエンスを整数回を繰り返した結果を返す。 ただし、整数が負の値の場合、空のシークエンスを返す。

b. (シークエンス, 整数)の処理内容について

シークエンス*整数の返す結果は、元のシークエンス上のオブジェクトのコピーではなく、同じオブジェクトへの参照のコピーである。

解決策

単純にfor文で繰り返すことで解決。

# OK
a_list = [[0] for _ in range(3)]
print(a_list) #[[0],[0],[0]]
a_list[0].append(1)
print(a_list) #[[0,1],[0],[0]]

参考

• pythonで空の多次元配列 - Qiita
• terminology - What is the x = [m]*n syntax in Python? - Stack Overflow
• 6. Expressions — Python 3.10.5 documentation

【AtCorderメモ・Python】チートシート

AtCoderに挑戦しているとき、毎回調べていることをメモする。

※本記事は、必要に応じて定期的に追記していく。

入力

よく使うもの

type of var	example	Python
str	"ab"	a = input()
str	"ab cd"	a, b = input().split()
list(str)	"ab cd ef"	a = list(input().split())
int	10	i = int(input())
int	10 20	i, j = map(int, input().split())
list(int)	10 20 30	i = list(map(int, input().split()))

参考

• 初心者向けAtcoder標準入力セット(Python) - Qiita

出力

Yes or No を１行で切り替え(内包表記)

flag = True #True:'Yes', False:'No' 
ans = 'Yes' if flag else 'No'
print(ans)

参考

• Pythonリスト内包表記の使い方 | note.nkmk.me

リストを単一文字列に変換（join）

#type: list(str)
str_list = ['d','o','g']
ans = ''.join(str_list)
print(ans) #'dog'
 
#type: list(int) *文字列への変換が必要
int_list = [1,2,3]
ans = ' '.join(map(str, int_list))
print(ans) #'1 2 3'

参考

• 【Python】 リストの文字列要素を連結・結合する（join） | Hbk project

その他

リスト内包表記

リスト内包表記でfor,if,elseを活用。

#for (map関数のようなイメージ)
a_list = [1,2,3]
x_list = [a_i*2 for a_i in a_list ]
print(x_list) #[2,4,6]
 
#for / if (map関数+filter関数のようなイメージ)
a_list = [1,2,3]
x_list = [a_i*2 for a_i in a_list if a_i%2==1]
print(x_list) #[2,6]
 
#for / if /else
a_list = [1,2,3]
x_list = [a_i*2 if a_i%2==1 else a_i*10 for a_i in a_list]
print(x_list) #[2,20,6]

参考

• Pythonリスト内包表記の使い方 | note.nkmk.me
• リスト内包表記の活用と悪用 - Qiita

多次元リストの初期化

多次元リストの初期化時に*を利用すると、想定外の動きをするので、アンチパターンとして記載。

# OK
a_list = [[0] for _ in range(3)]
print(a_list) #[[0],[0],[0]]
a_list[0].append(1)
print(a_list) #[[0,1],[0],[0]]
 
# NG
b_list = [[0]]*3
print(b_list) #[[0],[0],[0]]
b_list[0].append(1)
print(b_list) #[[0,1],[0,1],[0,1]]

参考

guarana001.hateblo.jp

多次元リストを複合キーでソート

多次元リストを複合キーでソートする方法を記載。

from operator import itemgetter
 
# (名前, 数学, 英語)の組み合わせ
data = [['A', 40, 100], ['B', 70, 100], ['C', 80, 40]]
 
#  キー①：英語、キー②：数学で降順にソート
data = sorted(data, key=itemgetter(2, 1), reverse=True)
# [['B', 70, 100], ['A', 40, 100], ['C', 80, 40]]

参考

• [Python] 多次元リストを複数キーでソートする - Qiita
• itemgetter/attrgetterでsortedのkeyをスッキリさせる - Qiita

【AtCorderメモ】AtCoder Beginner Contest 253

現在の目標は、茶色なのでABCの問題A~Dを安定的に解けること。

AtCoder Beginner Contest 253の問題A~Dの内容整理。

成績

感想

• 問題Cに時間をかけてしまい、3問(問題A,~,C)しか解けなかった。
• せめて、問題Dは解けたらな…

コンテスト成績証

項目	結果
順位	4748th / 8944
パフォーマンス	485
レーティング	476 → 477 (+1)

提出結果

問題	結果	得点	作業時間
A	AC	100	8:36
B	AC	200	17:18
C	AC←RE	300(1)	66:34
合計		600(1)

A. Median?

Point

• solution 1 : (a>=b)and(b>=c) or (c>=b)and(b>=a) かどうか？
• solution 2 : (a,b,c)をソートして, bが真ん中かどうか？
• solution 2 は、他の人の回答見て知った。上手い！！！

ソースコード

solution 1（クリックすると展開）

a,b,c = map(int, input().split())
flag = (a>=b and b>=c) or (c>=b and b>=a)
 
ans = 'Yes' if flag else 'No'
print(ans)

solution 2（クリックすると展開）

abc_list = list(map(int, input().split()))
b = abc_list[1]
abc_list.sort()
 
flag = abc_list[1] == b
ans = 'Yes' if flag else 'No'
print(ans)

B. Distance Between Tokens

Point

• マス目上のoを2つ探し、マンハッタン距離を計算
• マス目上の探索は、素直に二重ループするべきだった…涙

ソースコード

solution（クリックすると展開）

h,w = map(int, input().split())
t_point = []
 
for i in range(h):
    s_i = list(input())
    for j in range(w):
        if s_i[j] == 'o':
            t_point.append([i,j])
 
ans = abs(t_point[0][0]-t_point[1][0])+ abs(t_point[0][1]-t_point[1][1])
print(ans)

C. Max - Min Query

Point

• いつも悩まされるクエリとmultiset
• とりあえず、dictを使ったスタックで解いた。
• ただ、1から書き始めると時間が掛かるので、チートシートのようなものを作成した方が良さそう。
• 公式の解説を見ると、Pythonでも①平方分割②heapq③Binary Indexed Treeなどの方法があるらしい。 一度整理したい。

ソースコード

solution（クリックすると展開）

class Stack():
    def __init__(self):
        self.dict       = {}
        self.max_value  = -1
        self.min_value  = 10000000000
     
    #クラス変数を初期化
    def initialization(self):
        self.dict       = {}
        self.max_value  = -1
        self.min_value  = 10000000000
     
    #クラス変数の最大値・最小値をxに設定
    def set_max_min(self,x):
        self.min_value = x if self.min_value > x else self.min_value
        self.max_value = x if self.max_value < x else self.max_value     
     
    #クラス変数の最大値・最小値がxの場合、再設定
    def del_max_min(self,x):
        if self.min_value == x:
            self.min_value = min(self.dict.keys())
        if self.max_value == x:
            self.max_value = max(self.dict.keys())
     
    #クラス変数の辞書にxを追加
    def append(self,x):
        #クラス変数の辞書は、空かどうか
        if len(self.dict)>0:
            #クラス変数の辞書にxが含まれているかどうか
            if x in self.dict.keys():
                self.dict[x] = self.dict[x]+1
            else:
                self.dict[x] = 1
                self.set_max_min(x)
        else:
            self.dict[x] = 1
            self.set_max_min(x)
     
    #クラス変数の辞書からxを削除・減らす
    def pop(self,x,c):
        #クラス変数の辞書は、空かどうか
        if len(self.dict)>0:
            #クラス変数の辞書にxが含まれているかどうか
            if x in self.dict.keys():
                del_num = min(c,self.dict[x])
                self.dict[x] = self.dict[x] - del_num
                #クラス変数の辞書のxが無くなったかどうか
                if self.dict[x] == 0:
                    self.dict.pop(x)
                    if len(self.dict)>0:
                        self.del_max_min(x)
                    else:
                        self.initialization()

 
if __name__ == "__main__":
    stack = Stack()
    q = int(input())
    for _ in range(q):
        q_i = list(map(int, input().split()))
        if q_i[0]==1:
            x = q_i[1]
            stack.append(x)
        if q_i[0]==2:
            x = q_i[1]
            c = q_i[2]
            stack.pop(x,c)
        if q_i[0]==3:
            print(stack.max_value - stack.min_value)

参考

• Python | 辞書の長さ(要素数)を取得する
• Pythonで辞書の要素を削除するclear, pop, popitem, del | note.nkmk.me
• Pythonで辞書の値の最大値・最小値とそのキーを取得 | note.nkmk.me

D. FizzBuzz Sum Hard

Point

• 以下のように包除原理で整理できる(数式っぽく書く方法が分からんかった…涙)
  • (1,...,nのうち、Aの倍数でもBの倍数でもないものの総数)
  • = (1,...,nの総数) - (1,...,nのうち, Aの倍数 or Bの倍数の総数)
  • = (1,...,nの総数)
  • - (1,...,nのうち, Aの倍数の総数)
  • - (1,...,nのうち, Bの倍数の総数)
  • + (1,...,nのうち, AとBの最小公倍数の倍数の総数)
• 最小公倍数を直接計算できるlcmが使えないらしい
• //（整数除算）を意識しないと、値がずれるので注意

ソースコード

solution（クリックすると展開）

import math 
 
n,a,b = map(int, input().split())
c = a * b // math.gcd(a, b)
 
ans = (1+n)*n//2
ans -= (n//a)*(a+(n//a)*a)//2
ans -= (n//b)*(b+(n//b)*b)//2
ans += (n//c)*(c+(n//c)*c)//2
 
print(ans)

参考

• ·ñÌa
• Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me
• Pythonの算術演算子（四則演算、べき乗、リスト・文字列の結合など） | note.nkmk.me

【AtCorderメモ】AtCoder Beginner Contest 251

現在の目標は、茶色なのでABCの問題A~Dを安定的に解けること。

AtCoder Beginner Contest 251の問題A,Cの内容整理。 ※問題B,Dも整理できたら、追記する。

成績

感想

• 問題B,CがTLEなってしまい、2問(問題A,C)しか解けなかった(´；ω；｀)
• せめて、問題Bは解けたらな…

コンテスト成績証

項目	結果
順位	5025th / 7125
パフォーマンス	343
レーティング	480 → 466 (-14)

提出結果

問題	結果	得点	作業時間
A	AC	100	3:38
B	TLE←TLE	0(2)	?
C	AC←TLE	300(1)	?
合計		400(1)

A. Six Characters

Point

• 文字列(1~3文字)を繰り返して、6文字にする。

ソースコード

s=input()
 
s_int = len(s)
ans = s * (6//s_int)
 
print(ans)

C. Poem Online Judge

Point

• 先頭から条件付き最大値探索
• 探索の順番は、オリジナルかどうか？→最大値かどうか？
• (elem) in (list)が遅くTLEになるので、(elem) in (set)推奨(知らなかった…)

ソースコード

n = int(input())
 
s_used_set = set()
(max_index, max_rate) = (-1,-1)
 
for i in range(n):
    (s_i,t_i)=input().split()
    t_i = int(t_i)
      
    if s_i not in s_used_set:
        s_used_set.add(s_i)
         
        if t_i > max_rate:
            max_rate = t_i
            max_index = i+1

print(max_index)

参考

• 【Python】set型の基本と、死ぬほど遅い「hoge in list」からの脱却 | ゆとって生きたい。

【言葉メモ】初旬・上旬〜下旬・月初〜月末は、いつからいつまで？

ビジネスメールで度々登場する『月内の時期感を表す言葉（初旬・上旬〜下旬・月初〜月末など）』がいつからいつまでを表しているのか？を整理してみた。

『月内の時期感を表す言葉』のまとめ

初旬・上旬〜下旬は、期間が決まっているが、月初〜月末は人によって幅があり不明確。そのため、ビジネスメールでは、初旬・上旬〜下旬の方がベターではあるが、日程を共有する場合は具体的な日程を連携した方が無難…

初旬・上旬〜下旬：期間が明確

• 初旬・上旬：1日~10日
• 中旬：11日~20日
• 下旬：21日~30日

月初〜月末：期間が不明確

• 月初：  1日~10日･･･人によって幅ある
• 月央：11日~20日･･･人によって幅ある
• 月末：21日~30日･･･人によって幅ある

『月内の時期感を表す言葉』のイメージ

『月内の時期感を表す言葉』の詳細

『初旬・上旬〜下旬』の表す期間

『旬』は、時間の単位で10日間を表す。

旬（じゅん）は、時間の単位の1つで、10日間のことである。

（旬 (単位) - Wikipediaより引用）

そして、1つの月を10日間(旬)×３に分け、それぞれが『初旬・上旬〜下旬』で表され、次のように期間が明確になっている。

• 初旬・上旬：1日~10日
• 中旬：11日~20日
• 下旬：21日~30日

参考

• 旬 (単位) - Wikipedia

『月初〜月末』の表す期間

Weblio辞書で『月初』を調べると、次のように記載されているが、期間は明言されてない。

月の初め。その月の最初の頃。同じく月の半ば頃は「月央」、終わり頃は「月末」という。（月初(げっしょ)の意味や使い方 わかりやすく解説 Weblio辞書より引用）

また、他のサイトも期間を明言しておらず、『月初〜月末』の期間は人によって幅があり、期間が明確になっていない…とのこと。

• 月初：  1日~10日･･･人によって幅ある
• 月央：11日~20日･･･人によって幅ある
• 月末：21日~30日･･･人によって幅ある

参考

•  月初(げっしょ)の意味や使い方 わかりやすく解説 Weblio辞書 

• 「月末」「月初」はいつからいつまで - 社会人の教科書

• 月初とは何か？｜月初の過ごし方/月初日関数/月初と保険証-言葉の意味を知るならMayonez

【AtCorderメモ】AtCoder Beginner Contest 252

現在の目標は、茶色なのでABCの問題A~Dを安定的に解けること。

AtCoder Beginner Contest 252の問題A~Cの内容整理。 ※問題Dも整理できたら、追記する。

成績

感想

• 問題Cに時間をかけてしまい、3問(問題A,~,C)しか解けなかった。
• せめて、問題Dは解けたらな…

コンテスト成績証

項目	結果
順位	4616th / 9995
パフォーマンス	560
レーティング	466 → 476 (+10)

提出結果

問題	結果	得点	作業時間
A	AC	100	2:54
B	AC←WA	200(1)	16:54
C	AC←WA	300(1)	72:42
合計		600(2)

A. ASCII code

Point

• 文字列と数値(asciiコード)の変換

ソースコード

n = int(input())

ans = chr(n)
print(ans)

参考

• 【Python】文字列と数値（asciiコード）の変換まとめ - Qiita

B. Takahashi's Failure

Point

• list の最大値のインデックス取得
• list 同士の重複チェック
• list のインデックスは、0から始まる(ミスった涙)

ソースコード

n,k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
 
max_value = max(a_list)
a_list_idx = [idx+1 for idx, value in enumerate(a_list) if value == max_value]
 
chofuku_flag = len(set(a_list_idx) & set(b_list)) !=0
ans = 'Yes' if chofuku_flag else 'No'
print(ans)

参考

• ［解決！Python］リストの内包表記と「if」を組み合わせるには：解決！Python - ＠IT
• 2 つのリストに重複する要素を抽出する (set と＆) | まくまくPythonノート
• Pythonの三項演算子（条件演算子）でif文を一行で書く | note.nkmk.me

C. Slot Strategy

Point

• 問題文がよく分からん...(リール？, 表示されている文字？)
• (読解問題)同じ時間に押せるボタンは1つだけなので、押したい時間が被ったら10秒待たないとダメ。
• そこまで難しくないが、作業内容を整理する必要あり
• 2≤N≤100なので、全探索でもOK

ソースコード

import collections
 
n = int(input())
digit_index_lists = []
 
#各リールの0~9の数字が先頭になるまでにかかる時間
for i in range(n):
    s_list = list(map(int, list(input())))
    digit_index_list = []
    for j in range(10):
        digit_index_list.append(s_list.index(j))
    digit_index_lists.append(digit_index_list)
 
#0~9の数字が揃うまでの必要時間を計算
ans = 10000
for j in range(10):
    digit_index_lists_j = [x[j] for x in digit_index_lists]
    #数字が揃うまでの必要時間は、最遅のリールに依存
    tmp_max = 0
    conter = collections.Counter(digit_index_lists_j)
    for i_key in conter.keys():
        tmp = i_key + (conter[i_key]-1)*10
        if tmp_max < tmp:
            tmp_max = tmp
    
    if ans > tmp_max:
        ans = tmp_max
 
print(ans)

参考

• Python3 – リストの要素・行・列の抽出 – TauStation
• PythonのCounterでリストの各要素の出現個数をカウント | note.nkmk.me

【ゲーム日記】ELDEN RING #４

前回「忌み王モーゴット」を突破し、「王都ローデイル」から先に進めた。

今回の記事では、①東アルターの神授塔→②ロルドの大昇降機→③巨人たちの山嶺（→「火の巨人」にやられる）→④火山館→⑤「火の巨人」へのリベンジ→⑥巨人の火の釜、といった流れ。

ステータス・装備

「巨人たちの山嶺」・「火山館」を探索したためLV.85→LV.100になった。

前回と同じく「名刀月隠」ビルド（知力特化）。

攻略の流れ

前述の通り「忌み王モーゴット」突破してから、①東アルターの神授塔→②ロルドの大昇降機→③巨人たちの山嶺（→「火の巨人」にやられる）→④火山館→⑤「火の巨人」へのリベンジ→⑥巨人の火の釜、の順で進めた。

地図上の動き

「王都ローデイル」から道なりに進み、「巨人たちの山嶺」の「火の巨人」にボコボコにやられた。その後「火山館」に挑戦し「冒涜の君主ライカード」を討伐。「火の巨人」にリベンジし、「巨人の火の釜」に到達。

地図上の動き

①東アルターの神授塔

「忌み王モーゴット」を突破し、道なりに進む。すると、突然真っ暗な世界に連れていかれ、ボス「忌み双子」が登場。ボス「忌み双子」を倒すと、「東アルターの神授塔」に到達し、「モーゴットの大ルーン」を獲得。

モーゴットの大ルーン

ボス「忌み双子」

• 戦い方：「写し身の雫」を召喚し、戦技「束の間の月影」で一体ずつ討伐。
• 感想：突然、真っ暗な世界に連れていかれるので、結構驚いた。ただ、順番に登場するので、そこまで各個撃破は難しくない。あと、戦技「束の間の月影」で体勢を崩すので、そこまで苦労しなかった。

ボス「忌み双子」

②ロルドの大昇降機

「王都ローデイル」から外に出て道なり進むと、「メリナ」との会話の中で登場した「ロルドの大昇降機」に到達。「ロルドの大昇降機」前にボス「黒き剣の眷属」がいるが、そこまで強くないので、ゴリ押せる。

ロルドの大昇降機

ボス「黒き剣の眷属」

• 戦い方：「写し身の雫」を召喚し、戦技「束の間の月影」でゴリ押し。
• 感想：「写し身の雫」が強い！！

ボス「黒き剣の眷属」

③巨人たちの山嶺（→「火の巨人」にやられる）

「ロルドの大昇降機」を抜けるとそこは雪国だった。雪国こと「巨人たちの山嶺」を道なりに進んでいくと、ボス「凍てつく霧ボレアリス」（倒せなかった…）、侵入者「血の指翁」に遭遇。侵入者「血の指翁」を倒すと、最強と名高い「屍山血河」をゲット。ただ、ビルド的に装備できない…

進んだ先に、ボス「火の巨人」がいるが、お盆攻撃が強過ぎて20回ぐらい倒された。心が折れた…

巨人たちの山嶺

ボス「凍てつく霧ボレアリス」

• 戦い方：よく分からない…
• 感想：辺りがホワイトアウトする中、突然ドラゴン登場。他のドラゴンと同じように馬に乗りながら戦闘したが、ブレスが強過ぎる…

侵入者「血の指翁」

• 戦い方：通常の対人戦。ひたすら戦技「束の間の月影」
• 感想：一度攻撃を喰らうと、一気にやられてしまう。避けながら、戦技「束の間の月影」で攻撃するだけ。

ボス「火の巨人」

• 戦い方：よく分からない…
• 感想：最初の雪崩攻撃から始まり、お盆攻撃が強い。巨大な敵は、攻略方法がよく分からない、ノリと勢いで討伐してきたからなあ…

④火山館

ボス「火の巨人」に心が折れたので、未開の「ゲルミア火山」方向へ進めた。

「ゲルミア火山」を登っていくと、頂上に鎮座しているボス「降る星の成獣」を討伐。再び道なりに進めていくと、「火山館」に到着。

「火山館」に行くと、他世界に侵入しターゲットを討伐する依頼を受けられる。ターゲットを３人ぐらい討伐し、「火山館」の主人「タニス」と会話すると、他の場所に誘導される。誘導された場所には、ボス「冒涜の君主ライカード」がおり、ボコボコにされたが、なんとか討伐。

ボス「降る星の成獣」

• 戦い方：「写し身の雫」にヘイトが向いている間、「魔術：岩石弾」で遠距離から攻撃。
• 感想：当初は、近距離で戦技「束の間の月影」で攻撃していたが、岩石飛ばし攻撃＆突進攻撃に何度もやられたので、遠距離から魔術で攻撃する方針に変更。超簡単になった笑

ボス「冒涜の君主ライカード」

• 戦い方：「写し身の雫」を召喚し、専用武器「大蛇狩り」の戦技でひたすら攻撃。攻撃の回避は、死にながら体で覚えた…涙
• 感想：30回ぐらいやられて回避方法を覚え、なんとか倒せた。ボスが巨大で攻撃範囲も広過ぎるため、聖杯瓶を使い切ってギリギリの満身創痍だった。あと、専用武器「大蛇狩り」の戦技がカッコ良過ぎた。

ボス「冒涜の君主ライカード」

⑤「火の巨人」へのリベンジ

ボス「冒涜の君主ライカード」をなんとか突破し、Lv.100近くなったため、改めてボス「火の巨人」にリベンジした。刺し違えてギリギリな状態でなんとか突破。

ボス「火の巨人」

• 戦い方：YouTubeで戦い方を調べつつ、形態ごとに以下のように対応。
• 第1形態：基本は足元で、戦技「束の間の月影」で攻撃。お盆攻撃と炎攻撃の回避を両立するのが難しい。
  • 最初の雪崩攻撃：高台からジャンプで避ける。
  • お盆攻撃：足元で避ける。足元から離れると、速攻でお盆が迫ってくる。
  • 炎攻撃：追いかけてくるので、トレントで離れて回避。
• 第2形態：「写し身の雫」を召喚し、ヘイトが向いてないタイミングで戦技「束の間の月影」で攻撃。お盆攻撃はないが、炎攻撃が広範囲のため、ある程度の距離を保ちつつ隙を見て攻撃。
• 感想：40回ぐらいやられた…巨大なボスは、攻略方法がイマイチ分からない。第1形態のお盆攻撃にイライラが止まらなかったが、なんとか突破できた。

ボス「火の巨人」

⑥巨人の火の釜

「王都ローデイル」にて、NPC「メリナ」に示された目的地「巨人の火の釜」に辿り着いた。ただ、当初の目的だった黄金樹を燃やすため、NPC「メリナ」が犠牲になってしまった。ストーリー序盤から手助けしてくれたキャラのため、悲しかった…涙

巨人の火の釜イベント

次回のゲーム日記

以下のような項目に挑戦したい！

• 「巨人の火の釜」から先のストーリー
• ラニイベント進める
• ひたすら探索（これが一番楽しい！）