Kaggleコンペでは忘れずに「Final Submission」を選ぼう
「Santander Customer Transaction Prediction」コンペが、残り5日になりました。過去最多だった7,198 teams参加の「Home Credit Default Risk」コンペを超え、現時点でも8,650 teams参加と過去最多になっています。
このコンペが「メダルが獲得できるKaggleコンペ初参戦」という方も多いかもしれません。本記事では、最終的な成績を決める際に使われる自分の提出を選ぶ方法を説明します。
「Final Submission」とは？
Kaggleでは、1日当たりコンペごとに定められた回数の提出（submit）を実施することができます。そのたびに「Score」が付けられ順位表に反映されますが、こちらはあくまで「public Leaderboard(LB)」に関する情報です。一般にtestデータはpublic/privateに二分割されており、最終的な成績はprivate部分の結果で判定されます。
では自分が日々提出したもののうち、全てでPrivate部分の結果が計算されるかというと、そうではありません。全提出の中からコンペごとに定められた個数の提出のみを選ぶ必要があります。この情報は「Rules」タブや「My Submissions」タブに記載があるので、ご確認ください。
例えば、「Santander Customer Transaction Prediction」コンペでは次のような情報が書かれています（和訳は筆者）。
You may select up to 2 submissions to be used to count towards your final leaderboard score. If 2 submissions are not selected, they will be automatically chosen based on your best submission scores on the public leaderboard. In the event that automatic selection is not suitable, manual selection instructions will be provided in the competition rules or by official forum announcement.
（あなたは、最終的なLBに使われるスコアを計算するための提出（submit）を2つまで選択できます。 2つが選択されていない場合は、public LBでのScore上位が自動的に選択されます。）
Your final score may not be based on the same exact subset of data as the public leaderboard, but rather a different private data subset of your full submission — your public score is only a rough indication of what your final score is.
（最終成績は、public LBではなく、private LBに基づいて決まります。public LBのScoreは、大まかな指標にすぎません）
You should thus choose submissions that will most likely be best overall, and not necessarily on the public subset.
（したがって、public LBのScoreだけではなく、より汎用的にベストな可能性が高い提出を選択すべきです）
どうやる？
https://www.kaggle.com/c/santander-customer-transaction-prediction/submissions
方法は簡単です。該当コンペの「My Submissions」タブを開き、「Use for Final Score」のチェックを入れるだけです。
上記のスクリーンショットでは、私がこのコンペに一度も提出していないので「No submissions to show」と表示されています。提出をしている人の画面は次のようになっているはずで、2つまで*1チェックを入れられます。
なお当然ですが、チェックを入れられるのはコンペ終了時点までです。午前9時終了のコンペの場合は、午前8時半などに改めて意図した「Final Submission」になっているか確認すると良いかと思います。
何を基準に決める？
これは非常に奥深い話で、議論は尽きません。
一般には「Trust CV」という標語が掲げられています。簡単に説明すると「public LBのスコアではなく、自分のCross Validationの値を信じよう」という意味です。最終成績はpublic LBではなくprivate LBに基づいて決まるので、private部分での性能を測るためにはCross Validationの値の方がより汎用的な指標になるという話です*2。
最近はほぼ全てのコンペで、終盤になると「何をFinal Submissionに選ぶか？」というdiscussionが投稿され、活発に議論されている印象があります。コンペの特性に応じた議論が交わされているので、このような投稿も参照して「Final Submission」を選ぶと良いかと思います。
おわりに
本記事では、最終的な成績を決める際に使われる自分の提出を選ぶ方法を説明しました。
数カ月真面目に取り組んだコンペが「Final Submission」のミスで望まない結果になってしまうと、悔やんでも悔やみきれません*3。
多くの方には「何を今更」という内容だったかもしれませんが、1人でも本記事が参考になった方がいれば嬉しいです*4。
*1:個数はコンペによって異なる場合があります
*2:「Cross Validationとは何か？」という方は下記記事をご参照ください。upura.hatenablog.com
*3:こんな事例も・・・ amalog.hateblo.jp
*4:本記事は「PetFinder.my Adoption Prediction」コンペで「Final Submission」を選択し忘れた方の呟きを受けて執筆しました
まさかここに来てこんな悲劇あるとはなぁ…。こんな犠牲者また出さないためにもu++さんの記事にちょこっとでも載せて頂ければ…。（ボソッ）
いや〜いないかこんなやつ！
Kaggle入門記事をQiitaに書きました
先日「Kaggleに登録したら次にやること ～ これだけやれば十分闘える！Titanicの先へ行く入門 10 Kernel ～」という記事の初版を公開しました。
初めてQiitaに記事を書いたのですが、ありがたいことにTwitter含め大きな反響を頂きました。
新年度に心機一転Kaggleに入門したいという方に向けて、書きました。まだ未完成な部分もありますが、随時更新していきます。
— u++ (@upura0) 2019年3月31日
===
Kaggleに登録したら次にやること ～ これだけやれば十分闘える！Titanicの先へ行く入門 10 Kernel ～ https://t.co/Eyu5zf6svs #Qiita
本記事では、Qiita記事では割愛した執筆の経緯について述べます。
きっかけ
執筆のきっかけの一つは、次のツイートでした。
今人々が一番求めてるもの「kaggleに登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」
— ほげふが (@hogeandfuga) March 26, 2019
この投稿は、競技プログラミングのコンテストサイト「AtCoder」の入門の決定版となったQiita記事に倣った、いわば「ネタツイート」です。ただRT・いいね数も多く、一定の需要があるように感じられました。
需要あるっぽいので、各位頑張りましょう。 https://t.co/LLRkpO3RNd
— HoxoMaxwell🌸 (@Maxwell_110) March 26, 2019
実は私は以前から、このような記事の執筆を検討していました。
これ何回か書こうとしたんですが、結局何書けば良いか分からなくなってお蔵入りしてます。。。どんな情報が載ってると嬉しい感じでしょうか🤔 https://t.co/Ds6NG07myC
— u++ (@upura0) March 26, 2019
その際は良い切り口が思い浮かばずにお蔵入りになりましたが、これを機に、もう一度腰を据えて執筆してみようという考えに至った次第です。
Kaggleの入門記事で意識した切り口
上述したAtCoderの入門記事は、Googleで「AtCoder 入門」と検索した際に一番最初に出てくるなど、入門の決定版となっています。
僕自身も多分に漏れず、「競技プログラミングとは何か」も知らないところから、この記事でAtCoderに入門しました。そして「これでコンテスト出ても大丈夫！」と自信を持ち、実際のコンテストに参加し始めました。
これは私の持論ですが、勉強の類いはある程度基礎を学んだ段階で実践に飛び込み、自分の力不足を肌で感じながら必要な知識を学んでいくのが効率的だと思っています。その意味で「競技プログラミングに何となく興味ある」状態から「実際のコンテストに参加できる」状態まで自分を引き上げてくれるコンテンツには非常に価値があると考えています。
今回改めてKaggleの入門記事の切り口を考えたとき、このようなAtCoderの入門記事の本質的な役割に気付きました。そして、力不足かもしれませんが、Kaggleにおいても同様の役割に注力した記事が書けないかと考えるに至りました。つまり「Kaggleに何となく興味ある」から状態から「実際のコンテストに参加できる」状態まで引き上げてくれるコンテンツが目標となっています。
おわりに
本記事では、先日初版を公開した「Kaggleに登録したら次にやること ～ これだけやれば十分闘える！Titanicの先へ行く入門 10 Kernel ～」という記事の執筆の経緯について述べました。現状まだ完成していない部分も多いですが、この記事で説明した目標を達成すべく、Kaggle入門者に向けたより良いコンテンツになるよう、随時更新を重ねていく予定です。
「累積和を何も考えずに書けるようにする！」をPythonで解く
「累積和を何も考えずに書けるようにする！」という記事に記載されていた計5問をPythonで解きました。Pythonだと、itertools.accumulateを利用することで1次元累積和が簡単に記述できます。
最近話題の「累積和」について色々書いてみました！！！
— けんちょん (@drken1215) March 28, 2019
累積和は、日経新聞が競技プログラマという存在を表現するときに「累積和などの高度なアルゴリズム的手法を自在に用いることができる」という表現をするくらい、アルゴリズマの代名詞的な雰囲気になってる！！！！！https://t.co/xh99JQfHFh
累積和の例題
問題 1： AOJ 0516 - 最大の和 (JOI 2006 本選 A)
from itertools import accumulate N, K = list(map(int, input().split())) A = list(map(int, input().split())) # 累積和 B = [0] + A B = list(accumulate(B)) ans = [] for i in range(N-3): ans.append(B[i+3]-B[i]) print(max(ans))
問題 2： AtCoder ABC 084 D - 2017-like Number
import math from itertools import accumulate def is_prime(n): if n == 1: return 0 for k in range(2, int(math.sqrt(n)) + 1): if n % k == 0: return 0 return 1 Q = int(input()) L = [0]*Q R = [0]*Q for i in range(Q): L[i], R[i] = list(map(int, input().split())) min_L = min(L) max_R = max(R) check = [] for i in range(min_L, max_R+1): if (i % 2 == 1): flg = (is_prime(i) and is_prime((i+1)/2)) else: flg = 0 check.append(flg) # 累積和 check = [0] + check check = list(accumulate(check)) for i in range(Q): print(check[R[i] - min_L + 1] - check[L[i] - min_L])
エラトステネスのふるいを利用する場合。
from itertools import accumulate # エラトステネスの篩 # is_prime := 1~nが素数か否か # table := 2~nのうち素数 def sieve(n): is_prime = [True for _ in range(n)] is_prime[0] = False for i in range(2, n+1): if is_prime[i-1]: j = 2 * i while j <= n: is_prime[j-1] = False j += i table = [i for i in range(1, n+1) if is_prime[i-1]] return is_prime, table Q = int(input()) L = [0]*Q R = [0]*Q for i in range(Q): L[i], R[i] = list(map(int, input().split())) max_R = max(R) is_prime, table = sieve(max_R) check = [0]*(max_R + 1) for i in range(0, max_R + 1): if (i % 2 == 1): if (is_prime[i-1] and is_prime[(i+1)//2-1]): check[i] = 1 # 累積和 check = [0] + check check = list(accumulate(check)) for i in range(Q): print(check[R[i] + 1] - check[L[i]])
問題 3： AtCoder ABC 122 C - GeT AC
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])
問題 4： AtCoder AGC 023 A - Zero-Sum Ranges
from itertools import accumulate import collections N = int(input()) A = list(map(int, input().split())) # 累積和 B = [0] + A B = list(accumulate(B)) # 個数を数える c = collections.Counter(B) cm = c.most_common() cnt = 0 for v in cm: if v[1] > 1: cnt += (v[1]*(v[1]-1)//2) print(cnt)
二次元累積和
問題 5: AtCoder ABC 005 D - おいしいたこ焼きの焼き方
N = int(input()) D = [list(map(int, input().split())) for i in range(N)] Q = int(input()) P = [int(input()) for i in range(Q)] # 2次元累積和 S = [[0 for i in range(N+1)] for j in range(N+1)] for i in range(N): for j in range(N): S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + D[i][j] val = [0]*(N*N+1) # val[v] := 面積が v の長方形領域の総和の最大値 for x1 in range(0, N): for x2 in range(x1+1, N+1): for y1 in range(0, N): for y2 in range(y1+1, N+1): area = (x2-x1)*(y2-y1) v = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1] val[area] = max(val[area], v) # val[v] := 面積が v 「以下」の長方形領域の総和の最大値 for i in range(0, N*N): val[i+1] = max(val[i+1], val[i]) for p in P: print(val[p])
AtCoder「エクサウィザーズ 2019」をPythonで解く
AtCoder「エクサウィザーズ 2019」に出て、2完でした。
ABCのA, B問題を全て埋めていた甲斐があり、3分で2完できました。C問題はTLEが取れませんでした。
昼休みに2問解いて、ABCのA, B埋め完了〜🎉C, Dも仕上げていくぞ💪 pic.twitter.com/KNsTUJsJ7a
— u++ (@upura0) March 22, 2019
A - Regular Triangle（100点）
- AとBとCが全部一致しているか否か
A, B, C = list(map(int, input().split())) if ((A == B) and (B == C)): print("Yes") else: print("No")
B - Red or Blue（200点）
- S内のR, Bの数をそれぞれ数えて比較
N = int(input()) S = input() R = S.count('R') B = S.count('B') if (R > B): print("Yes") else: print("No")
C - Snuke the Wizard（500点）
- 愚直に解いたらTLE
N, Q = list(map(int, input().split())) S = input() spell = [list(input().split()) for i in range(Q)] D = {} for i, s in enumerate(S): if s in D: D[s].append(i) else: D[s] = [i] G = [1 for _ in range(N)] loss = 0 for sp in spell: if sp[0] in D: for d in D[sp[0]]: if sp[1] == 'L': if d != 0: G[d-1] += G[d] else: loss += G[d] G[d] = 0 elif sp[1] == 'R': if d != (N-1): G[d+1] += G[d] else: loss += G[d] G[d] = 0 print(N - loss)
「典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ 」をPythonで解く
2月下旬に「典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ 」の前半7問をPythonで解きました。ABCのD問題で時折出題されるDPの感覚をザックリと掴むことができました。
1 ナップサック DP とは
問題 1: 最大和問題
n = int(input()) a = list(map(int, input().split())) # input # == # 3 # 7 -6 9 # == # dp[0] = 0 dp = [0] # DP for i in range(n): dp_i_1 = max(dp[i], dp[i] + a[i]) dp.append(dp_i_1) # print(dp) # == # [0, 7, 7, 16] # == print(dp[-1])
2 ナップサック問題
問題 2: ナップサック問題
N, W = list(map(int, input().split())) weight = [] value = [] for i in range(N): w_tmp, v_tmp = list(map(int, input().split())) weight.append(w_tmp) value.append(v_tmp) # initialize dp = [0 for _ in range(W + 1)] # DP for i in range(N): dp_tmp = [] for w in range(W + 1): if (w >= weight[i]): dp_next = max(dp[w-weight[i]] + value[i], dp[w]) else: dp_next = dp[w] dp_tmp.append(dp_next) dp = dp_tmp print(dp[-1])
3 部分和問題とその応用たち
問題 3: 部分和問題
N = int(input()) a = list(map(int, input().split())) A = int(input()) # initialize dp = [True if i==0 else False for i in range(A + 1)] # DP for i in range(N): dp_tmp = [] for j in range(A + 1): if (j >= a[i]): dp_next = (dp[j-a[i]] or dp[j]) else: dp_next = dp[j] dp_tmp.append(dp_next) dp = dp_tmp print(dp[-1])
問題 4: 部分和数え上げ問題
N = int(input()) a = list(map(int, input().split())) A = int(input()) # initialize dp = [1 if i==0 else 0 for i in range(A + 1)] # DP for i in range(N): dp_tmp = [] for j in range(A + 1): if (j >= a[i]): dp_next = (dp[j-a[i]] + dp[j]) else: dp_next = dp[j] dp_tmp.append(dp_next) dp = dp_tmp print(dp[-1])
問題 5: 最小個数部分和問題
N = int(input()) a = list(map(int, input().split())) A = int(input()) # initialize INF = 9999999999 dp = [0 if i==0 else INF for i in range(A + 1)] # DP for i in range(N): dp_tmp = [] for j in range(A + 1): if (j >= a[i]): dp_next = min(dp[j-a[i]] + 1, dp[j]) else: dp_next = dp[j] dp_tmp.append(dp_next) dp = dp_tmp if dp[-1] != INF: print(dp[-1]) else: print(-1)
問題 6: K個以内部分和問題
N, K = list(map(int, input().split())) a = list(map(int, input().split())) A = int(input()) # initialize INF = 9999999999 dp = [0 if i==0 else INF for i in range(A + 1)] # DP for i in range(N): dp_tmp = [] for j in range(A + 1): if (j >= a[i]): dp_next = min(dp[j-a[i]] + 1, dp[j]) else: dp_next = dp[j] dp_tmp.append(dp_next) dp = dp_tmp if dp[-1] <= K: print("YES") else: print("NO")
問題 7: 個数制限付き部分和問題
N = int(input()) a = list(map(int, input().split())) m = list(map(int, input().split())) K = int(input()) # initialize dp = [0 if i==0 else -1 for i in range(K + 1)] # DP for i in range(N): dp_tmp = [] for j in range(K + 1): if (dp[j] >= 0): dp_next = m[i] elif ((j < a[i]) or (dp_tmp[j-a[i]] <= 0)): dp_next = -1 else: dp_next = dp_tmp[j-a[i]] - 1 dp_tmp.append(dp_next) dp = dp_tmp if dp[-1] >= 0: print("YES") else: print("NO")
AtCoder Beginner Contest 122をPythonで解く
「AtCoder Beginner Contest 122」に出て、全完でした。A問題で誤読して2WAして号泣スタートでしたが、最後が精進していたDP問題だったので何とか取り戻せた形です。
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完でした。
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
好みの問題と言われるとそれまでですが🙄
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)
