Google CodeJamをVSC上でデバッグする

Qualification RoundはAtCoderのコードテストを間借りしてコーディングしたのだけど、やっぱりVisual Studio Codeを使いたい。

input()だけ書き換えて、printと想定解を目でみて比較すればよいのだけど、 'Case' → 'CASE' ': ' → ':' あたりでWAになったことがあるので、できればサンプルケースはコピペして実行したい。

ついでに、input()もコピペを間違えると怖いので、提出へもそのままコピペしたい。

ということで、真ん中にそのままコピペできるコード部を残して前後に挟むスクリプトを作った。

stdoutをredirectする方法は見つかったのだけど、自身のstdinに流し込む方法はなさそうなので、inputメソッドをgeneraterで書き換えている。sys.stdin()などinput()以外には対応していない。redirect_stdoutはwith文で使うことが多いようだが、インデントが残ってしまうのでenter()とexit()を使っている。#mainのセクションのみコピペすると幸せになれる、はず！

###########
# header #
###########
from contextlib import redirect_stdout
from io import StringIO
from difflib import Differ
from itertools import zip_longest as _zip_longest

with open('input.txt', 'r') as f:
    _input = f.read()

def input_generator(_input):
    for line in _input.splitlines():
        yield line

input_gen=input_generator(_input)
input = input_gen.__next__

captured_stdout = StringIO()
_redirect_stdout = redirect_stdout(captured_stdout)
_redirect_stdout.__enter__()

########
# main #
########

def solve(a,b):
    print(a+b)
    print(a)
    

T=int(input())
for _ in range(T):
    a=int(input())
    b=int(input())
    
    solve(a,b)


##########
# footer  #
##########
_redirect_stdout.__exit__(None, None, None)

with open('output.txt', 'r') as f:
    out = f.read()

for x,y in _zip_longest(captured_stdout.getvalue().splitlines(),
                out.splitlines()):
    print('\n'.join(Differ().compare([x],[y])))

使っているところはこんな感じ。input, outputともひとまずサンプルケースのコピペで良いし、必要があれば適宜自作のテストケースを書き加える。

Google Code Jam 2019 Qualification Round 全完でした

codingcompetitions.withgoogle.com

Foregone Solution

任意の一例を構築すれば良いだけなので適当に。

T = int(input())
N = [input() for _ in range(T)]

for i, n in enumerate(N):
  A = ''
  B = ''
  for d in n:
    if d=='4':
      A+='2'
      B+='2'
    else:
      A+=d
      B+='0'
  print('Case  #' + str(i+1) + ': ' + str(int(A)) + ' ' + str(int(B)))

You Can Go Your Own Way

深さ優先探索してみたらTest set1のみ通過するものの、Test set2(n<=1000)でTLE。 N*Nの正方形でこれも任意の一例を示せばよいだけなので、裏返すだけでよかった。

部分点解法

T = int(input())
N = []
L = []

for _ in range(T):
  n = int(input())
  l = input() #lydia's move
  N.append(n)
  L.append(l)

from collections import deque

for i, [n, l] in enumerate(zip(N,L)):
  # i: case i+1
  # n: n*n maze
  # l: lydia's move
  
  l_positions = [(1,1)]
  dq=deque()
  dq.append((0,(1,1),''))
  
  for l_direction in l:
    if l_direction =='E':
      l_positions.append((l_positions[-1][0] + 1, l_positions[-1][1] + 0))
    if l_direction =='S':
      l_positions.append((l_positions[-1][0] + 0, l_positions[-1][1] + 1))
  #print(l_positions)
      
  while dq:
    j, position, way = dq.pop()
    #print(i, n, l, j, position, way)
    
    if position == (n,n):
      print('Case #' + str(i+1) + ': ' + way)
      break
    
    if position!=l_positions[j]:
      if position[0] < n and position[1] <n:
        dq.extend([(j+1, (position[0]+1, position[1]), way+'E'),
                 (j+1, (position[0], position[1]+1), way+'S')])
      elif position[0] ==n:
        dq.append((j+1, (position[0], position[1]+1), way+'S'))
      elif position[1] ==n:
        dq.append((j+1, (position[0]+1, position[1]), way+'E'))
    else:
      if l[j] =='E' and position[1] < n:
        dq.append((j+1, (position[0], position[1]+1), way+'S'))
      elif l[j] =='S' and position[0] < n:
        dq.append((j+1, (position[0]+1, position[1]), way+'E'))  

満点解答

T = int(input())
N = []
L = []

for _ in range(T):
  n = int(input())
  l = input() #lydia's move
  N.append(n)
  L.append(l)
  
for i, l in enumerate(L):
  l=l.replace('S','_')
  l=l.replace('E','S')
  l=l.replace('_','E')
  
  print('Case #' + str(i+1) + ': ' + l)

Cryptopangrams

ユークリッドの互除法はmath.gcdで省力化。エッジケースをあまり考えずに実装して、test caseは通るものの、実際のtest setではRE．最初同じ文字が並ぶ場合を考慮していなかった。

T = int(input())
N = []
L = []
ciphertexts = []

for _ in range(T):
  n, l = list(map(int, input().split()))
  ciphertext = list(map(int, input().split()))
  N.append(n)
  L.append(l)
  ciphertexts.append(ciphertext)

from math import gcd
#from fractions import gcd

for i, [n,l,ciphertext] in enumerate(zip(N,L,ciphertexts)):
  # i: case i+1
  # n: maximum of prime, 101<=n<=10000(test1), 1e100(test2)
  # l: the length of the list of values in the ciphertext, 25<=l<=100
  # ciphertext: list of ints: (the prime for X) * (the prime for Y)
  
  prime_l=[]
  
  p1 = gcd(ciphertext[0], ciphertext[1])
  p0 = ciphertext[0]//p1
  prime_l.append(p0)
  
  for j in range(l):
    prime_l.append(ciphertext[j]//prime_l[j])
  
  cipher_dict={p:c for p, c in zip(sorted(list(set(prime_l))), 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')}
  
  print('Case #' + str(i+1) + ': ' + ''.join([cipher_dict[p] for p in prime_l]))

初めて2個めの数字が出てくる位置を検索して、同じ文字が並んでいる場合と、2つの文字が交互に並んでいる場合があることに注意しつつ微修正して無事通過。この初めて違う数字が出てくるインデックス、whileで回したのだけどもっとスマートな書き方がありそう。

T = int(input())
N = []
L = []
ciphertexts = []

for _ in range(T):
  n, l = list(map(int, input().split()))
  ciphertext = list(map(int, input().split()))
  N.append(n)
  L.append(l)
  ciphertexts.append(ciphertext)

#from math import gcd
from fractions import gcd

for i, [n,l,ciphertext] in enumerate(zip(N,L,ciphertexts)):
  # i: case i+1
  # n: maximum of prime, 101<=n<=10000(test1), 1e100(test2)
  # l: the length of the list of values in the ciphertext, 25<=l<=100
  # ciphertext: list of ints: (the prime for X) * (the prime for Y)
  
  prime_l=[]
  
  j=0
  while ciphertext[j]==ciphertext[j+1]:
    j+=1
  
  q = gcd(ciphertext[j], ciphertext[j+1])
  p = ciphertext[j] // q
  
  prime_l = [q if (k-j)%2 else p for k in range(j+1)]
  #print(ciphertext[j], ciphertext[j+1], p, q, prime_l)
    
  for k in range(l-j):
    prime_l.append(ciphertext[j+k]//prime_l[j+k])
  
  cipher_dict={p:c for p, c in zip(sorted(list(set(prime_l))), 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')}
  
  print('Case #' + str(i+1) + ': ' + ''.join([cipher_dict[p] for p in prime_l]))

Dat Bae

このタイトル、Data Baseからaとsが脱落したタイトルなのか。今気づいた。

Test set1のF=10までは比較的自然な発想。全ビットを見分けられるようなQueryを投げて、返りを適当に。n列目をnの2進数表記をして、それを1~F回目のqueryで1桁ずつ送るようにすると、返り値を列ごとに並べて2進数→intで列数に戻るので便利。 itertoolsとnumpyによる転置と、int('xxxx', 2)を駆使して実装。高級言語万歳。

from itertools import product
import math
import numpy as np

def solution():
    n, b, f = list(map(int, input().split())) # n of workers, broken workers, lines
    m = min(f, math.ceil(math.log2(n)))
    
    queries = np.array(list(product([0,1], repeat = m))[:n]).T
    responses = []
    
    for i in range(m):
        print(''.join(queries[i].astype('str')), flush=True)
        responses.append([int(s) for s in input()])
    responses = np.array(responses)
    
    correct = [int(''.join(r.astype('str')), 2) for r in responses.T]
    broken = [str(_) for _ in range(n) if _ not in correct]
    
    print(' '.join(broken), flush=True)
    assert(input()=='1')
    
t = int(input())
for _ in range(t):
    solution()

そうはいってもこれだとF=5に対応できない。B<=15という意味深な条件があるが…。

16個選ぶとかならず1個は生きてるビットがあることに気づく。116, 016と16個ずつ並べれば個々の戻り列は、どの16個の中にあるか特定できるので、そのなかで残りの4列を2⁴=16に使って解ける。

from itertools import product, groupby
import math
import numpy as np

def solution():
    n, b, f = list(map(int, input().split())) # n of workers, broken workers, lines
    
    f=5    
    
    # 1st line
    r = (n+31)//32
    print((('0'*16+'1'*16)*r)[:n], flush=True)
    response=input()
    broken_in_blocks = [len(list(g)) for k, g in groupby(response)]
    
    # 2nd - 5th line
    r = (n+15)//16
    query4_16 = np.array(list(product([0,1], repeat = 4))).T
    queries = np.tile(query4_16, (1,r))[:,:n]
    #print(queries)
    responses = []
    
    for i in range(f-1):
        print(''.join(queries[i].astype('str')), flush=True)
        responses.append([int(s) for s in input()])
    
    responses = np.array(responses)
    
    l=0
    correct = []
    for i in range(r):
        m = broken_in_blocks[i]
        correct.extend([i*16 + int(''.join(x.astype('str')), 2) for x in responses[:,l:l+m].T])
        l+=m
    
    broken = [str(_) for _ in range(n) if _ not in correct]
    print(' '.join(broken), flush=True)
    assert(input()=='1')
        
t = int(input())
for _ in range(t):
    solution()

整数問題で商にmath.ceilを使ってはいけない？

n/m以下の整数を使いたいときはn//mを使えばよいが，n/m以上の最小の整数に相当する演算子は存在しない．

そこで，横着してmath.ceilを使うと，答えがずれることがある．

ABC046 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report atcoder.jp

誤り解法

import math

N=int(input())

T=1
A=1
for _ in range(N):
  t,a=list(map(int, input().split()))
  m = max(int(math.ceil(T/t)), int(math.ceil(A/a))))
  T = t*m
  A = a*m
  #print(T,A)
  
print(T+A)

これをするとtest caseのうち4件でWAとなる．

# 略
def divceil(a,b):
  if a%b==0:
    return a//b
  else:
    return a//b + 1

# 略
  m = max(divceil(T,t), divceil(A,a))

これならok．

T/tの部分が浮動小数点で計算されるので，割り切れるような場合であっても精度の末尾のところで微妙にずれる のだろうと推測．

ABC-047C - 一次元リバーシ / 1D Reversi をpythonで解く

atcoder.jp

リバーシにおいて同じ色の1個の石も2個の石も等価なので，まずは同じ色の並んだ部分を1個の石に置き換えると，あとは1個ずつひっくり返していくしかないのでその長さ-1が答えとなる．

解法1 np.diffを使う

import numpy as np

S=input()
S=np.array([1 if s=='B' else 0 for s in S])

answer = np.abs(np.diff(S)).sum()
print(answer)

AC @ 334ms

変化点を見つけるためには差分系列を取れば良い．01からなるndarrayに変更しておけば，np.diffで差分をとって，その絶対値の和をとれば良い．

経過時間はimport numpyに時間がかかっている．

解法2 itertools.groupby

from itertools import groupby

S=input()
answer = -1
for _ in groupby(S):
  answer+=1

print(answer)

AC @ 32ms itertools内のgroupbyは値が切り替わるたびに値を送出するiterater．sort済みの配列に対して使われることが多いが，このように単に連続する値をグループ化したいときにも使える．iteratorなので回しきらないと全体数がわからないのがネックだが，逆に複雑な処理が必要な場合も有効かも．

for文のところは，リスト内包表記でも書けてちょっと早くなる（AC @28ms）

from itertools import groupby

S=input()
answer = sum([1 for _ in groupby(S)]) -1

print(answer)

解法3 実直に

S=input()

answer=0
prev=S[0]
for s in S:
  if s!=prev:
    answer+=1
  prev=s

print(answer)

AC @33ms いろが変わるたびにanswerを+1する．

個人的にはnumpyの解法が好き．

AtCoderのランク感

最近ちょこちょことAtCoderをやっている．

以下のblogでも引用されているように， kumagi.hatenablog.com

何度も言うけど競プロは向き不向きあるし、競プロ出来なくてもITエンジニアとしてやっていけるから、競プロ必須だとは思わない方がいいよ。
ただ、「ABCのC問題」が解けない人はやっぱITエンジニアとしてはどの分野であろうと全く信用しないし、そこまでは解けるようにしておくべき。

— chokudai(高橋 直大)🍆🍡 (@chokudai) June 28, 2018

ということでABCのC問題が解けないとお話にならないらしいが，C問題難しいorz．となっていた．

ただ，この投稿，よくよく見ると2018年6月末の投稿．これは～ABC100あたりまでの話．自分が解けなかったのはABC100以降が多く，ABC100以前は8割くらいは自力で解けている感じ．

最近のABCのC、ちょっと難しすぎるし、「これが出来ないとエンジニアとして信用できない」なんてレベルでは全然なくなりつつあるので、もうちょい簡単にしてーってオーラを発してWriterに分かってもらおうとしている

— chokudai(高橋 直大)🍆🍡 (@chokudai) March 27, 2019

とりあえずC埋めぐらいはして水色になりたい．

AtCoder Beginner Contest 122 Dを漸化式で解く

A-Cの3完．Dは解けず．64個書き出せば解ける，とは思ったのだがそこから手が進まず．動的計画法を使いこなせていない．

以下は解説を見てから．最後3桁についての場合の数で漸化式． 邪道かもしれないけど，正規表現を使うと場合分けが減って楽．

import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
    memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))

そして，このABCとは関係ないけどAtCoderはnumpyが使えるらしいということを知ったのも今日の収穫．

to/do ・DP全般 ・DFS、BFS、グラフDFS、グラフBFS ・union-find ・ヒープ，スタックなど ・グラフ，二分木など ・ダイクストラ法、ベルマンフォード法

O'Reilly「機械学習のための特徴量エンジニアリング」を読んだが期待ハズレだった

2020.1.15 追記：特にテーブルデータにおける「特徴量エンジニアリング」であれば，『Kaggleで勝つデータ分析の技術』が良かった．特徴量設計は試行錯誤の面も大きいのだけど，実際のコンペの場面でどのように考えて特徴量設計をおこなっているかや，上位陣のsolutionに対する考察なども載っていて参考になる．

機械学習のための特徴量エンジニアリング ―その原理とPythonによる実践 (オライリー・ジャパン)

Kaggle Grand Master推薦，といった帯がついて話題になっていたので読んでみた．

結論から言うと，正直なところ期待はずれだった．ネットでは良書との評判も高いので，逆にちょっと煽ったタイトルにしてしまった．． 特徴選択を期待していたのだが，そこは範囲外だった．

対象読者としては，logistic regressionやSVM，MLPなどの理論を学んだけどその先はやったことないというあたりの層か．でもそういう人って「特徴量エンジニアリング」と聞いて読みたいと思うのかな？

期待していたこと

・非線形な効果を持つような特徴量や，周期的な変化をする特徴量（曜日や月・季節）をどう使うか．それぞれどんなモデルと親和性が高いか．

・外れ値への対応

・欠損値への対応

・決定木以外のモデルにおいて，間隔が一定でない順位尺度の特徴量をどう使うか．

・離散化するのであればその閾値はどう設定するか．gini係数なのか，エントロピーなのか．bin数はどう決めるか．

・交互作用項への対処．例えば都道府県ごとの何らかの予測をするときに，人口データと面積データがあったとして人口密度を特徴量として加えるか否か．和や差であればほとんどのモデルで捉えられると思うが，和や差であってもそれが価値を持つなら特徴量として加えたほうが良いのか．モデルごとに捉えやすい交互作用が違うのではないか（2つの特徴量の積や商を捉えられるか，また2乗項や3乗項などの非線形作用を捉えられるか否か）と思うが，実際に明示的に加えた場合とそうでない場合の実験結果など．

・ロジスティック回帰やGBDTなど個々のモデルに分けて，特徴量設計のベストプラクティス

残念ながら，上記のような情報はほとんど得られなかった．

実際の中身

・連続変数のスケーリング各種．

・離散化の閾値については固定幅か分位数かを紹介するくらい．

・カテゴリカル変数のビンカウンティングは知らなかったので良かった．が，targetのleakになるので実際には使いづらそう..．

・categorical embeddingについては言及なし

・特徴選択については1ページのみ．フィルタ法（閾値をつかって有用でない特徴量を削減する），ラッパー法（特徴量のサブセットを使って実際にモデルを学習し，精度を比較することで使用すべき特徴量か判断する），組み込み法（決定木など，モデルの学習プロセス自体に特徴量選択が組み込まれている）の簡単な紹介のみ．「特徴選択の詳細については本書の範囲を超えます．」とのこと．

・テキストの特徴量抽出：BoWとTF-IDFの計算方法．

・画像の特徴量抽出：SIFTおよびHOGという古典的な特徴量計算方法．そしてAlexNetのごくごく簡単な紹介．

感想

・このタイトルとこの厚さの本で，テキストや画像は要らない．別の本を読む．

・「特徴選択の詳細は本書の範囲を超える」ってそれは...．有用でない特徴量を作り出しては害悪しかないので，特徴量の有用性をどう評価するかは特徴量エンジニアリングにおいて極めて重要で，ほぼほぼ表裏一体と思うのだけど．そこを放棄して，ただいかにモデルに突っ込むかだけの浅い議論になってしまっている．

・特徴量エンジニアリング≒特徴選択くらいの勢いで期待していたので，ほんとに残念だった．

・特徴量選択についてのGuynoの論文を知ることができたのは良かった．

・画像からCNNで特徴抽出するとして，それをどう他の特徴量と組み合わせるかについてはあまり示唆がなかった．KaggleのPetFinderコンペのように，画像とともに複数の特徴量が与えられて，それらを合わせて何かを予測するタスクがある．画像部分にCNNをかけて，他の特徴量との合流させてMLPをかけるのか，画像だけからtargetを予測するモデルを組んで，stackingするような形でその予測値を2段めの入力として利用するのかなどいくつか方法があると思うが，そういったことへの示唆がほしかった．（もちろんno free lunchで試行錯誤になるのだろうが，実例とともにどうやって比較検証したかを載せてくれるとありがたかった．）

・もっと具体的な事例を紹介してほしかった．

・たぶん対象読者としては，一度も機械学習モデルを組んだことがない人，なのかも．Kaggleで投稿したことあるくらいの人には，恐らくあまり読む価値ない気がする．