東京海上日動 プログラミングコンテスト2020

はじめに

この記事では、東京海上日動 プログラミングコンテスト2020のA~C問題を解説します。

A - Nickname

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a

1
2
S = input()
print (S[:3])

B - Tag

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b

ABの大小関係を意識しなくていいようにA<Bとなるように入れ替えます。入れ替えても答えが変わらないことは明らかです。

1
2
3
4
5
6
7
8
9
a, v= map(int,input().split())
b, w= map(int,input().split())
t = int(input())
if b < a:
a,b = b,a
if a+v*t >= b+w*t:
print('YES')
else:
print('NO')

C - Lamps

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c

いもす法を用いることで操作O(N)でできます。

これだと、全体の計算量がO(KN)となり間に合わないように思いますが、実際はK回も操作を行わずとも早い段階で全ての電球の明るさがNとなることがわかります。シミュレーションをしてみると、Nが最大で全ての電球の初期の光の強さを0としても操作は41回で十分です。

この解放でPyPyで提出することでACできます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import itertools
N, K = map(int,input().split())
A = list(map(int,input().split()))
K = min(41,K)
for k in range(K):
imos = [0] * (N+1)
for n in range(N):
a = n - A[n]
b = n + A[n]
a = max(0,a)
b = min(N-1,b)
imos[a] += 1
imos[b+1] -= 1
csum = list(itertools.accumulate(imos))
A = csum[:-1]
A = [str(a) for a in A]
print (' '.join(A))

関連記事

過去のABC解説記事です。

  • ABC169
    • A-F問題を解いています。
  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年6月13日
  • 最終更新日:2020年6月13日

AOJ1167 ポロック予想

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

重複ありのナップザック問題です。正四面体数を計算していきながら、動的計画法を行います。
Pythonだと時間が厳しいため、本質的ではない高速化が必要でした。

状況によるのかもしれませんが、今回の場合は組み込み関数のminを自前の実装に書き換える事で3倍程度速くなり、TLEを回避できました。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def main():
ans = []
N = 10**6
dp = [10**10]*(N+1)
dp_odd = [10**10]*(N+1)
dp[0] = 0
dp_odd[0] = 0

for i in range(1,10**3):
w = i*(i+1)*(i+2)//6
if N<=w:
break
for n in range(N-w):
# dp[n+w] = min(dp[n]+1,dp[n+w]) # TLE
new = dp[n] + 1
if new < dp[n+w]:
dp[n+w] = new
if w&1==1:
for n in range(N-w):
#dp_odd[n+w] = min(dp_odd[n]+1,dp_odd[n+w]) # TLE
new = dp_odd[n] + 1
if new < dp_odd[n+w]:
dp_odd[n+w] = new

while(1):
S = int(input())
if S==0:break
ans.append([dp[S],dp_odd[S]])
for a,b in ans:
print(a,b)
if __name__ == '__main__':
main()

記事情報

  • 投稿日:2020年6月13日
  • 最終更新日:2020年6月13日

パ研杯2019 3D パ研軍旗

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d

この問題は動的計画法を用いて解くことができます。

方針

左の列から順に評価をしていきます。n列目の色がcであるとき、塗り替えの最小値をdp[n][c]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = int(input())
S = []
col = {'R':0, 'B':1, 'W':2, '#':-1}
for i in range(5):
s = input()
ls = list(s)
ls = [-1] + [col[e] for e in ls] # 最も左の列にダミーを入れて奥
S.append(ls)
dp = [[0]*3 for _ in range(N+1)]



for n in range(N):
for i in range(3):
cnt = 0
for j in range(5):
cnt += (S[j][n+1] != i)
K = [0,1,2]
K.remove(i) # 同じ色は隣合えない
dp[n+1][i] = min(dp[n][K[0]] + cnt, dp[n][K[1]] + cnt)
print (min(dp[-1]))

記事情報

  • 投稿日:2020年6月12日
  • 最終更新日:2020年6月22日

JOI2015予選D シルクロード

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_d

この問題は動的計画法を用いて解くことができます。

方針

都市nm日目にいるとして、疲労度の最小値をdp[n][m]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N, M = map(int, input().split())
D = []
C = []
for n in range(N):
d = int(input())
D.append(d)
for m in range(M):
c = int(input())
C.append(c)

dp = [[10**10]*(M+1) for _ in range(N+1)]
for m in range(M+1):
dp[0][m] = 0
for n in range(N):
for m in range(M):
dp[n+1][m+1] = min(dp[n+1][m], dp[n][m]+D[n]*C[m])
print (dp[-1][-1])

記事情報

  • 投稿日:2020年6月11日
  • 最終更新日:2020年6月11日

JOI2013予選D 暑い日々

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d

この問題は動的計画法を用いて解くことができます。

方針

d日目に服nを着た場合のスコアをdp[d][n]として記録します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
D, N = map(int,input().split())
T = []
for d in range(D):
T.append(int(input()))
A = []
B = []
C = []

for n in range(N):
a,b,c = map(int,input().split())
A.append(a)
B.append(b)
C.append(c)

dp = [[-10**8]*N for _ in range(D+1)] # 最大値を求める問題で、初日のスコアが0になるので-infで初期化

for d in range(D):
t = T[d]
for n in range(N):
if A[n] <= t <= B[n]:
if d==0:
dp[d+1][n] = 0 # 初日はスコアが加算されない
continue
for m in range(N):
dp[d+1][n] = max(dp[d][m] + abs(C[n]-C[m]),dp[d+1][n])
print (max(dp[-1]))

記事情報

  • 投稿日:2020年6月10日
  • 最終更新日:2020年6月10日

JOI2012予選D パスタ

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d

この問題は動的計画法を用いて解くことができます。

方針

iを一日前に食べjを二日前に食べているような、n日目までのパターン数をdp[n][i][j]として表します。

一日前、二日前が存在しない場合もあるので、ダミーのパスタとして0を用います。すなわちdp[0][0][0]=1として初期化します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
MOD = 10**4
N, K = map(int, input().split())
A = [0] * N
for k in range(K):
a, b = map(int, input().split())
A[a-1] = b
dp = [[[0]*4 for i in range(4)] for j in range(N+1)]
dp[0][0][0] = 1
for n in range(N):
for i in range(4):
for j in range(4):
for k in range(1,4):
if A[n]!=0 and A[n]!=k: # パスタが指定されているのにkが違えばスキップ
continue
if k != i or i != j: # 三日連続ではない場合
dp[n+1][k][i] += dp[n][i][j]
dp[n+1][k][i] %= MOD

ans = 0
for i in range(4): # 最終日、全ての状態の分を足す
for j in range(4):
ans += dp[-1][i][j]
ans %= MOD

print (ans)

記事情報

  • 投稿日:2020年6月9日
  • 最終更新日:2020年6月9日

JOI2011予選D 1年生

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d

この問題は動的計画法を用いて解くことができます。

方針

左からn個の数字を使ってmを実現できる組み合わせの数をdp[n][m]として計算していきます。

コード

A[0]を取り出している意図ですが、これはA[0]=0の場合に対処するためです。この操作をせずにdp[0][0]=1としてしまうと、最初のn=0のループの後に、dp[1][0]=2となってしまいます。(一つ目の数字であるにも関わらず、同じ場所dp[0][0]を参照して二度もらってしまう。)

あるいは、DPの更新部分で条件式を

1
if m+A[n] >= 0:
1
if n>0 and m+A[n] >= 0:

のように書き換えても良いでしょう。

1
2
3
4
5
6
7
8
9
10
11
12
13
N = int(input())
A = list(map(int, input().split()))
M = 20
dp = [[0]*(M+1) for _ in range(N-1)]
dp[0][A[0]] = 1
A = A[1:]
for n in range(N-2):
for m in range(M+1):
if m-A[n] >= 0:
dp[n+1][m] += dp[n][m-A[n]]
if m+A[n] <= M:
dp[n+1][m] += dp[n][m+A[n]]
print (dp[-1][A[-1]])

記事情報

  • 投稿日:2020年6月8日
  • 最終更新日:2020年6月8日

Python3でQuine(自己言及プログラム)

はじめに

以下のようなスクリプトを作成し、Python3で実行してみてください。プログラミングの力がある方は、実行前にどういった出力になるかを考えてみてください。

1
_='_=%r;print(_%%_)';print(_%_)

Quine

先ほどのスクリプトを実行すると、ソースコードそのものが出力されます。このようなプログラムのことをQuine、自己言及プログラムと呼びます。ただし、通常以下のようなプログラムはQuineと見なされません。

  • 空のスクリプト
  • ファイル入力を取るスクリプト

空のスクリプト

多くの言語では空のスクリプトを実行することができます。この時、当然標準出力には何も出力されないため、ソースコードそのものが出力となるスクリプトと言えます。といっても、これではあまりにも面白みがなく、Quineとは見なさないのが一般的です。

ファイル入力を取るスクリプト

スクリプトそのものを読み込んで、標準出力するスクリプトもQuineとは見なされません。確かに、これも何でもありになってしまいます。

1
2
3
import sys
f = open(sys.argv[0])
print (f.read().rstrip())

冒頭のコードの解説

はじめにお見せしたコードはやや難解です。これでどうしてQuineが実現できるのか考えてみます。

1
_='_=%r;print(_%%_)';print(_%_)

%rの意味

まずは、Pythonにおけるprintf形式の文字列書式化について復習しましょう。C言語などを触ったことがある方は見慣れた書式ですね。

以下のようなスクリプトがあるとします。

1
2
price = 1100
print('合計は'+str(price)+'円です')

printf形式の文字列書式化で書き換えると

1
2
price = 1100
print('合計は%s円です' % price)

このように、文字列の出力の中に変数の値を用いたい場合に利用できます。

さて、今の例で%sとした箇所はPythonオブジェクトをstr()で変換することを表しています。そのため、priceが数値型であっても文字列型であっても結果は変わりません。

1
2
price = 1100
print('合計は%s円です' % price)
1
2
price = '1100'
print('合計は%s円です' % price)

ただし、%dとした場合はpriceが文字列型だとエラーとなるので注意してください。

1
2
price = 1100
print('合計は%d円です' % price)
1
2
price = '1100'
print('合計は%d円です' % price) # これはエラー

さて、話を冒頭のスクリプトに戻します。スクリプトでは%sが用いられていました。

1
2
3
price = '1100'
print('合計は%s円です' % price)
print('合計は%r円です' % price)
1
2
合計は1100円です
合計は'1100'円です

このように%rとした場合はシングルクォート付きで出力されます。これは、%sとした箇所はPythonオブジェクトをrepr()で変換するためです。本題からそれてしまうため、reprの詳細についてはここでは解説しません。

さて、実際に%sの挙動を追ってみます。ここでは簡単のために以下のように一部文字を書き換えます。

1
_='_=%r;print(_%%_)';print(_%'A')

実行結果は以下のようになります。

1
_='A';print(_%_)

Aがシングルクォート付きで出力されていますね。

次に、print(_%%_)について解説します。printf形式の文字列書式化で以下のようなことが実現できると学びました。

1
2
print('消費税は10%です')
print('消費税は%sパーセントです' % 10)
1
2
消費税は10%です
消費税は10パーセントです

しかしながら、以下のスクリプトはエラーとなります。

1
print('消費税は%s%です' % 10) # これはエラー

これはprintf形式の文字列書式化を用いた場合、%を出力したければエスケープをする必要があるためです。

1
print('消費税は%s%%です' % 10)
1
消費税は10%です

これでOKです。

まとめ

さて、これで必要な材料は揃ったので、最後にもう一度冒頭のスクリプトの流れを追います。

1
_='_=%r;print(_%%_)';print(_%_)

まず、セミコロンの手前までで、変数_に代入を行います。変数_には文字列_=%r;print(_%%_)が格納されています。

続いて、print(_%_)で変数_を出力します。ただし変数内でprintf形式の文字列書式化%rが用いられています。この箇所は一旦保留して[?]としましょう。

なので出力は以下のようになるはずです。%の数が減ることに注意してください。

1
_=[?];print(_%_)

さて[?]には、変数_の中身が代入されます。%rですのでシングルクォートが付きます。

1
_='_=%r;print(_%%_)';print(_%_)

スクリプトそのものと全く同じ出力となりましたね。

記事情報

  • 投稿日:2020年6月7日
  • 最終更新日:2020年6月7日

AOJ1166 迷路と命ず

この記事で使うアルゴリズム

幅優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

この問題は幅優先探索を用いて解くことができます。

方針

幅優先探索を行うことで最短経路を求めることができます。幅優先探索はキューを用いて実装できますが、ゴールに到達する前にキューが空になった場合は到達不可能ということになります。

この問題のような迷路を解く問題では、移動可能かどうかを判定する際に壁の有無を参照すれば良いです。周囲には全て壁が配置されていることとして、壁の有無の判定を訪問フラグの判定より先に行うことで、配列外参照をケアしなくてよく実装が簡単になります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

def solve(W,H,ver,hor):
dist = [ [0]*W for _ in range(H)]
dist[0][0] = 1
q = deque()
q.append((0,0)) # スタート地点をenqueue
while(q):
y, x = q.popleft()
if y==H-1 and x==W-1:
break
else:
for dx, dy in dxdy:
if (dx==-1 and ver[y][x]==0) or (dx==1 and ver[y][x+1] == 0) or (dy==-1 and hor[y][x]==0) or (dy==1 and hor[y+1][x]==0): # 通行可能か
if dist[y+dy][x+dx] == 0: # 未訪問か
q.append((y+dy,x+dx))
dist[y+dy][x+dx] = dist[y][x] + 1 # 距離を記録
return dist[H-1][W-1]
ans = []
while(1):
W, H = map(int,input().split())
if W==0 and H==0:
break
ver = [] # 垂直方向の壁
hor = [] # 水平方向の壁
hor.append([1]*W) # 一番上の壁(スタート地点から始めるので、入口を塞いで問題ない)
for i in range(2*H-1):
bar = list(map(int,input().split()))
if i%2==0:
ver.append([1]+bar+[1]) # 一番左と右にも壁を設置
else:
hor.append(bar)
hor.append([1]*(W+1)) # 一番下の壁(ゴール地点につけば終了するので、出口を塞いで問題ない)
ans.append(solve(W,H,ver,hor))

for a in ans:
print(a)

記事情報

  • 投稿日:2020年6月7日
  • 最終更新日:2020年6月7日

BLEUスコアとは? Pythonでのスクラッチ実装

BLEUスコアとは

BLEUスコアは機械翻訳の結果を評価するための指標です。値は0~1の間の実数です。

参考によると、目安は下記のようになります。

1
2
3
4
5
6
7
0.1以下	ほとんど役に立たない
0.1~0.2 主旨を理解するのが困難である
0.2~0.3 主旨は明白であるが、文法上の重大なエラーがある
0.3~0.4 理解できる、適度な品質の翻訳
0.4~0.5 高品質な翻訳
0.5~0.6 非常に高品質で、適切かつ流暢な翻訳
0.6以上 人が翻訳した場合よりも高品質であることが多い

以下のように定義されます。

ただし、

1
2
3
4
5
H: システム翻訳文集合
R: 参照翻訳文集合
N: N-gramの長さ(4が用いられる場合が多い)
tn: 任意のN-gramトークン
closest_len(R): システム翻訳文の長さに最も近い参照翻訳文の長さ

を表します。

語順の相関に基づく機械翻訳の自動評価法から引用させていただきました。

NLTK

BLEUスコアはnltkに実装されています。システム翻訳文集合の要素数が1の場合、nltk.translate.bleu_score.sentence_bleuを利用します。

1
2
import nltk
nltk.translate.bleu_score.sentence_bleu(references, hypothesis)

システム翻訳文集合の要素数が複数ある場合、nltk.translate.bleu_score.corpusを利用します。

1
nltk.translate.bleu_score.corpus_bleu(list_of_references, hypotheses)

スクラッチで実装

今回はこれをスクラッチで実装します。テストのために、nltk.translate.bleu_score.sentence_bleuを用います。

システム翻訳文集合(hypothesis)は一つのシステム翻訳文のみを含むとして実装します。一つのシステム翻訳文に対して参照翻訳文の集合(references)が対応します。

Brevity Penalty

適合率Pnは、翻訳文の長さが短いほど高くなる傾向があります。BLEUスコアでは、それを補正するためにBP(Bravity Penalty)を導入します。参照翻訳文に対して、システム翻訳文の長さが短い場合にペナルティを与えます。

ハマったポイント

NLTKではclosest_lenを以下のように実装しています。例えば、システム翻訳文の長さが5の場合、参照翻訳文の長さが4でも6絶対値は1となりますが、絶対値が最小の長さを与えるのは長さが小さい方、すなわち4の時となるように実装しているようです。

1
2
3
4
ref_lens = (len(reference) for reference in references)
closest_ref_len = min(
ref_lens, key=lambda ref_len: (abs(ref_len - hyp_len), ref_len)
)

そのためfor文を用いて最小値を更新する実装をした場合、結果が一致しない場合があるので注意が必要です。

N-gram

スライスを利用することでN-gramを実装します。

1
2
3
4
5
for i in range(1,N+1):
lh = []
for k in range(len(hypothesis)-i+1):
lh.append(' '.join(hypothesis[k:k+i]))
ch = Counter(lh)

count

標準ライブラリのcollections.Counterを用いると良いです。

1
from collections import Counter

コード全体

テストコードも含めた全コードです。NLTKのバージョン3.2.5でテストが通ることを確認しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import unittest
import numpy as np
import nltk
import math
from collections import Counter

def bleu_score(reference, hypothesis, weights=[1/4]*4):
if len(hypothesis) == 0:
return 0
N = min(4,len(hypothesis))
ref_lens = (len(ref) for ref in reference)
closest = min(
ref_lens, key=lambda ref_len: (abs(ref_len - len(hypothesis)), ref_len)
)
bp = min(1, math.exp(1-closest/len(hypothesis)))

sm = 0
for i in range(1,N+1):
lh = []
for k in range(len(hypothesis)-i+1):
lh.append(' '.join(hypothesis[k:k+i]))
ch = Counter(lh)
s = 0
for t in ch:
mn = 0
max_count = 0
for ref in reference:
lr = []
for k in range(len(ref)-i+1):
lr.append(' '.join(ref[k:k+i]))
cr = Counter(lr)
max_count = max(max_count, cr[t])
mn = min(ch[t], max_count)
s += mn / len(lh)
if s==0:
if i==1:
return 0
else:
pass
else:
sm += weights[i-1] * math.log(s)
return bp*math.exp(sm)


class TestBleu(unittest.TestCase):
def setUp(self):
np.random.seed(0)

def test_hand_craft_case(self):

nltk_score = nltk.translate.bleu_score.sentence_bleu(reference, hypothesis)
my_score = bleu_score(reference, hypothesis)
print (nltk_score, my_score)
self.assertAlmostEqual(nltk_score, my_score)

def test_random_case(self):
for i in range(1000):
vocab = np.array(['a','b','c','d','e'])
n_word = np.random.randint(10)
n_ref = np.random.randint(1,5)
idx = np.random.choice(len(vocab), n_word)
hypothesis = vocab[idx].tolist()
reference = []
for j in range(n_ref):
n_word = np.random.randint(10)
idx = np.random.choice(len(vocab), n_word)
ref = vocab[idx].tolist()
reference.append(ref)

nltk_score = nltk.translate.bleu_score.sentence_bleu(reference, hypothesis)
my_score = bleu_score(reference, hypothesis)
self.assertAlmostEqual(nltk_score, my_score)

if __name__ == '__main__':
unittest.main()

記事情報

  • 投稿日:2020年6月6日
  • 最終更新日:2020年6月6日