AtCoder Beginner Contest 122をPythonで解く

「AtCoder Beginner Contest 122」に出て、全完でした。A問題で誤読して2WAして号泣スタートでしたが、最後が精進していたDP問題だったので何とか取り戻せた形です。

atcoder.jp

A - Double Helix（100点）

• 4通りの場合分け
• 対応を空目して2WAしたので、明日メガネを購入しに行きます

b = input()

if b == 'A':
    ans = 'T'
elif b == 'C':
    ans = 'G'
elif b == 'G':
    ans = 'C'
elif b == 'T':
    ans = 'A'

print(ans)

B - ATCoder（200点）

• 部分文字列を全列挙し、ACGT文字列か否かを判定
• ACGT文字列か否かの判定は愚直に（どうすれば改善できた？）
• もっと綺麗に書ける気もするが、Aでしくじった余波で汚いコードに

S = input()
N = len(S)

alp = 'BDEFHIJKLMNOPQRSUVWXYZ'

cnt = []

for i in range(0, N):
    for j in range(i, N+1):
        tmp = S[i:j]
        flg = 1
        for a in alp:
            if a in tmp:
                flg = 0
        if flg:
            cnt.append(len(tmp))

print(max(cnt))

C - GeT AC（300点）

• TLE①：部分文字列を全列挙し、str.count('AC')
• TLE②：先にSのどの2文字が'AC'に一致するかを調べてフラグを立てておき、l, rの値に応じてフラグを合計する
• l, rの値に応じてフラグを合計する部分を累積和で高速化

from itertools import accumulate


N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

flg = []
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

D - We Like AGC（400点）

• Cの時点でTLEしたので、最初から全探索は頭になかった
• 「ABCのD問題はDPのD」らしい
• 愚直に全パターンを走査していき、違反したら0にする

N = int(input())
M = 10**9 + 7

dp = [
    [[[1 if i==0 else 0 for i in range(N-2)] for j in range(4)] for k in range(4)] for l in range(4)
]

dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[1][0][2][0] = 0

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[j][k][l][m+1] %= M
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

復習

B問題

`set(S) <= set('ACGT')` とかする気がします。

— ざぶろう (@zaburo_ch) March 24, 2019

S = input()
N = len(S)

alp = 'ATCG'
cnt = []

for i in range(0, N):
    for j in range(i, N+1):
        tmp = S[i:j]
        if set(alp) >= set(tmp):
            cnt.append(len(tmp))

print(max(cnt))

AtCoder Grand Contest 031 AをPythonで解く

「AtCoder Grand Contest 031」に出て、1完でした。

atcoder.jp

A - Colorful Subsequence（200点）

• 総当たりで解くとTLE
• アルファベットを1文字ずつ数え上げて計算する

N = int(input())
S = input()

M = 10**9 + 7
cnt = [0] * 26

for i in range(N):
    cnt[ord(S[i]) - ord('a')] += 1

ans = 1
for i in range(26):
    ans *= (cnt[i] + 1)
    ans %= M

print(ans - 1)

復習

cnt[ord(S[i]) - ord('a')]の部分、cntをdefaultdictで持っておくと実装がスッキリしますよ
好みの問題と言われるとそれまでですが🙄

— 杏仁まぜそば (@an_nindouph) March 16, 2019

befs-anne.hatenablog.com

from collections import defaultdict


N = int(input())
S = input()

M = 10**9 + 7
count_dict = defaultdict(int)

for s in S:
    count_dict[s] += 1

ans = 1
for v in count_dict.values():
    ans *= (v + 1)
    ans %= M

print(ans - 1)

Kaggleでメダルが獲得できるコンペか否か確認する

コンペのトップページの「Tiers」部分の表記で確認できます。

例えば、メダルが獲得できるpetfinderコンペでは、次のような表記です。

https://www.kaggle.com/c/petfinder-adoption-prediction

一方で、メダルが付与されないコンペでは、次のような表記になっています。

https://www.kaggle.com/c/titanic

なお、Kaggleのコンペには、いくつかの分類があります。一概には言えませんが、ある程度この分類でもメダル獲得の可否が判断できます。

• Common Competition Types
  • Featured
  • Research
  • Getting Started
  • Playground
• Other Competition Types
  • Recruitment
  • Annual
  • Limited Participation

www.kaggle.com

日本語訳は、次の記事にまとまっていました。

www.kokokocococo555.com

Kaggle CareerCon とは

はじめに

4月16〜18日に開催される「Kaggle CareerCon 2019」の早期受付が始まりました。昨年には「Kaggle CareerCon 2018」も開催されていたのですが、私が本格的にKaggleを始めたのは2018年のGWなので、きちんと認知できていませんでした。

本記事では「Kaggle CareerCon」について調べたことや関連リンクなどをまとめます。

Kaggle CareerCon とは

Kaggle CareerCon 2019の公式サイト*1に記載されている説明を以下に引用します（和訳は筆者）。

Kaggle CareerCon is a totally free, totally digital three-day event that's all about helping new data scientists land their first data science jobs.

（Kaggle CareerConは、完全無料、完全にオンラインで3日間開催されるイベントです。データサイエンティストを目指す方が最初のデータサイエンスの仕事を始めるのを手助けします）

Kaggle CareerCon 2018のFAQ*2には、以下のような補足もあります（和訳は筆者）。

Our sessions are tailored to those in search of their first data science job. That being said, a lot of the topics discussed will be helpful to a much broader audience–from those just considering the field, to mid-career data scientists looking for new challenges and opportunities.

（セッションは、最初のデータサイエンスの仕事を求めている方向けです。 しかし議論されるトピックの多くは、単にデータサイエンス分野を検討している方から、新しい環境を探している中堅のデータサイエンティストまで、より幅広い方に役立つでしょう）

Kaggle CareerCon 2018

Kaggle CareerCon 2018は、2018年3月20〜22日に開催されました。

www.kaggle.com

当日の模様はYouTubeで生配信され、専用のSlackも用意されたそうです*3。YouTubeはアーカイブが残っています。Kaggleによると、約17000人が参加登録したとのことです。

www.youtube.com

Kaggle CareerCon 2019

現在は、参加の早期受付を開始した段階です。

www.kaggle.com

セミナーやワークショップの実施が予定されているとのことです。

また開催に先立って「CareerCon 2019 - Help Navigate Robots」というコンペが3月13日（協定世界時）に始まりました。エントリー締切は4月4日、コンペ終了は4月11日です。

www.kaggle.com

上位100位に入った人には、このイベントならではの「賞品」が用意されています。最大チームサイズは1（つまりはソロ参加限定）のコンペです。

The top 100 will have the opportunity to send their resumes directly to any hiring company of their choosing that’s featured in our 2019 CareerCon Digital Career Fair.

（上位100人の方は、ご自身のレジュメを「2019 CareerCon Digital Career Fair」で紹介されている企業に直接応募する権利を得ます）

おわりに

本記事では「Kaggle CareerCon」について調べたことや関連リンクなどをまとめました。

昨年踏襲ならばYouTubeで動画も公開されるようですし、面白そうなコンテンツだけでも眺めてみようと思います。

*1:www.kaggle.com

*2:www.kaggle.com

*3:www.kaggle.com

AtCoder Beginner Contest 121をPythonで解く

「AtCoder Beginner Contest 121」に出て、3完でした。

atcoder.jp

C問題まで順調に解けたのですが、D問題でTLEした後、O(1)の解法が分かりませんでした。

A - White Cells（100点）

• h個の行とw個の列をそれぞれ一番端まで動かしても答えは変わらない

H, W = list(map(int, input().split()))
h, w = list(map(int, input().split()))

print((H-h)*(W-w))

B - Can you solve this?（200点）

• 要件通りに実装

N, M, C = list(map(int, input().split()))
B = list(map(int, input().split()))
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

def main():
    cnt = 0
    for i in range(N):
        val = C
        for j in range(M):
            val += A[i][j] * B[j]
        if val > 0:
            cnt += 1
    return cnt

print(main())

C - Energy Drink Collector（300点）

• 安い店から買い尽くしていく
• 多重リストのソートで実装

from operator import itemgetter


N, M = list(map(int, input().split()))

a = []
for i in range(N):
    a.append(list(map(int, input().split())))

def main():
    b = sorted(a, key=itemgetter(0))
    # print(b)
    m = 0
    cost = 0
    for i in range(N):
        # print(b[i])
        if (m + b[i][1]) <= M:
            m += b[i][1]
            cost += (b[i][0] * b[i][1])
        else:
            cost += (b[i][0] * (M-m))
            return cost
    return cost

print(main())

D - XOR World（400点）

• 次の実装がTLEになって、思考停止

from functools import reduce
from operator import xor


A, B = list(map(int, input().split()))

def main():
    val = []
    for i in range(A, B+1):
        val.append(i)
    ans = reduce(xor, val)
    return ans

print(main())

復習

D問題

• 愚直に実験していけば、規則性が見いだせた
• きちんと手を動かして考える大切さを改めて実感した

A, B = list(map(int, input().split()))
 
def get(x):
    return [x, 1, x + 1, 0][x % 4]
 
def main():
    return get(B) ^ get(A - 1)
 
print(main())

ブレインパッド「白金鉱業 Meetup Vol.6」にて「技術アウトプットを支える技術」の題目で発表しました

本日、ブレインパッド主催「白金鉱業 Meetup Vol.6」に登壇しました。

brainpad-meetup.connpass.com

題目は「技術アウトプットを支える技術」で、社会人として働きながら技術アウトプットを出そうとしている理由、そのために心掛けているTipsを紹介しました。

下記が僕以外の発表内容・発表者です。非常に豪華なメンバーの中に混ぜていただき、光栄でした。このような身に余る貴重な機会を頂けたのも、間違いなく日々のアウトプットのおかげです。今後とも、精進していきたいと思います。

ロボット事業における機械学習エンジニアという仕事について

Alejandro Gonzalez さん / GROOVE X株式会社

医療xDeep Learningの課題と展望について

菅原 洋平 さん / Preferred Networks, Inc. (PFN)

togetter.com

コルモゴロフ-スミルノフ検定を利用した特徴量選択

はじめに

えじさんの下記記事を読んで「コルモゴロフ-スミルノフ検定を利用した特徴量選択」が気になりました。自分なりに簡単に手を動かしてみたので、備忘録としてまとめておきます。

amalog.hateblo.jp

元になったdiscussionの投稿はこちらです。

www.kaggle.com

コルモゴロフ-スミルノフ検定を利用した特徴量選択

コルモゴロフ-スミルノフ検定とは

Pythonでは「scipy.stats.ks_2samp」で実行できます。

docs.scipy.org

This tests whether 2 samples are drawn from the same distribution.

日本語にすると「2つの集合が同じ分布から生まれたか否かを検定する」くらいでしょうか。

特徴量選択にどう活用する？

Kaggleでの特徴量選択に当たって、目的の一つは「testデータの予測に有用な特徴量を選択する」ことです。

ここで、trainデータの予測で言えば、正解の目的変数の値が分かっているので、何が有用な特徴量なのかは評価しやすいです。つまり、trainデータとtestデータで分布が似ている特徴量は、testデータの予測においても有用か否かを評価しやすいです。

逆に言えば、trainデータとtestデータで分布が似ていない場合は、仮にtrainデータの予測で良い評価を得ている特徴量でも、testデータの予測に有用か否かは判断がつきません。そのため、コルモゴロフ-スミルノフ検定を実施し、trainデータとtestデータで分布が似ていない特徴量を選択しないという手段が考えられます。

Kaggle Kernel

trainデータとtestデータの分布が違いそうな「Santander Value Prediction Challenge」のデータを利用しました。

実装の全容はKaggle Kernelとして公開しています。

www.kaggle.com

最初に、trainデータとtestデータを読み込み、予測に使わない列は削除しました。

train = pd.read_csv('../input/train.csv')
test = pd.read_csv('../input/test.csv')
train.drop(['target', 'ID'], inplace=True, axis=1)
test.drop(['ID'], inplace=True, axis=1)

あとは、discussionに貼られたコードをそのまま利用できます。このコードではp値が0.1以下の特徴量を list_discarded に格納しています。

from tqdm import tqdm
from scipy.stats import ks_2samp
list_p_value =[]

for i in tqdm(train.columns):
    list_p_value.append(ks_2samp(test[i] , train[i])[1])

Se = pd.Series(list_p_value, index = train.columns).sort_values() 
list_discarded = list(Se[Se < .1].index)

おわりに

本記事では、コルモゴロフ-スミルノフ検定を利用した特徴量選択を紹介しました。えじさんと同様に、僕もこのテクニックは手持ちに加えておこうと思います。