Quora Programming Challenge 2021

公式サイト

全体の印象

  • 部分点がある
  • 最初の1問はやるだけ実装問題
  • 次に、いくつかの競プロ的問題
  • 最後にML(Machine Learning)問題がセットごとに2つあり、統計を使う

反省点

  • コンテストサイトからは順位表情報が見えないが、Quora上では「開始から1時間経過後のランキング」などが公開されていたのでそれを見て通しやすい問題を見極めればよかった
  • まずすべての問題に目を通す
  • ML問題はマラソン的なので試行錯誤の時間が必要で、ML以外をどれだけ速く片付けられるかが大事そう

レベル感

  • 各回500人ほど参加、水色の私でギリギリ50位になれない所まで行けたので、青以上なら50位以内に行けてTシャツGETできそう

問題文

結果 (full ranking)

他サイト

Div1

  • digest
    • 記事を誰にリコメンドするかという実装問題
  • escape
    • H=1000, W=1000程度のグリッドに壁と平地、始点終点、いくつかの監視員(x,y,r(監視範囲))が与えられる
    • 最短でゴールに行くために必要な距離は？(or print IMPOSSIBLE)
    • bfsを監視員分回すとTLEする
    • kusanoさんのblogによると「移動範囲の広いガードは先に、狭いガードは後に時間差で置いていき」なるほど！
    • multisource bfs (&時間差) って感じかな
  • Students
    • H=3000, W=3000のグリッドに生徒がいて、上下左右は仲良しなこともある（与えられる）
    • 仲良しは含まれないように最大何人選べるか？という問題
    • 連結成分ごとに見て、最大安定集合分選べそう。YES, 二部グラフを意識して辺をはってフローで一発

f:id:peroon:20210209093326p:plain

  • Walls
    • 人と壁が与えられる。全人を連結させるために必要な壁の破壊コストの最小値を求めよ
    • MSTではダメ。どうするんだ？シュタイナー木？Strong connectivity augmentation?
    • （順位表を見てパスすべき問題だったらしい）
  • Tourism
    • 木上を旅行する。頂点ごとにお金を貰う。辺でお金を支払う。最初に持っておくべきお金の最小値は？
    • 典型っぽいが... HLD?
  • (ML)Flipped Data
    • N個の特徴ベクトルのうちb個をflipしてしまった。それを見つけよという問題。b個は40%以下になるという制約がある
    • 平均と分散を求めておいて正規化し、平均からの逸脱度が高いものを選べば良さそう
  • (ML)Identifying Spammers
    • Spammer or notの0/1判定機械学習問題
    • 人ごとに、「訪れたページ：その時間」の組がいくつか与えられる
    • 時系列データ機械学習？
  • 428点なら50位

Div2

  • Connect4
    • ゲームの勝敗を判定する関数の実装
    • 制約も小さく、やるだけ
  • Treasure
    • DPだが、各マスに保持する場合の数は最大値のものだけでいいことに気づけばいい
    • dp[i][j] 場所(i,j)に最大値で到る場合の数
  • Data Center
    • どのビルをデータセンターにすればいいか？
    • チェビシェフ距離なので45度回転してマンハッタン距離にしてx,y分離し、x,yそれぞれ別々に解けるそう (チェビシェフとマンハッタンは45度回転で可換)

  • (ML)Broken Message
    • 各値の前後に出る値の統計をとっておく
    • 前も後ろも統計が使えるなら、2つの統計値を「掛け算」して判定する（確率で考えるとそうなる）。これで69点取れた
  • (ML)Malicious Data 
from scipy.stats import multivariate_normal # 多変量正規分布
...
# それに沿った乱数データを生成し、probabilityが低いものをfakeとして採用しているっぽい。これは慣れてないと厳しい...
for i in range(10000):
    a,b,c = np.random.uniform(-3,3),np.random.uniform(0,3),np.random.uniform(-3,3)
    if multivariate_normal.pdf([a,b,c], mean, cov) < 0.00089:
        X_fake.append((a,b,c))
assert len(X_fake) > 1000
X_fake = X_fake[:1000]

  • 387点なら50位