トップ > 競技プログラミング

ABC147 E Balanced Pathでbitset高速化を完全に理解する

競技プログラミング アルゴリズム

本番で通せなかったABC147のE問題『Balanced Path』について、反省していきたいと思います。

問題概要

H*Wのグリッドの各マスに数が2つ書かれている。グリッド上を(0,0)->(H,W)にy+1orx+1で移動するとき、経路上の各マスについて、いずれかを選び、「その合計と選ばなかったものの合計の差の最小値」を求めよ。

考察

第一感

  • マス数が小さい(H,W <= 80)
  • 各マスに書かれた数も小さい(0 <= A_ij <= 80, 0 <= B_ij <= 80)
    • したがって各マスごとの差も 0 <= |A_ij - B_ij| <= 80
  • グリッドを右or下で移動するので、左マスと上マスだけに依存するDPになりそう
  • 経路ごとに具体的な集合は持たなくても良い気がする
    • そのマスまで到達した際に、可能な差の絶対値だけを持っておけば良い気がする

取り組み

  1. 上記を実装する
    • TLE
    • 到達できる集合をsetで管理したので、各状態からの遷移先を計算するところでループが重かった
  2. 各経路について差の絶対値が80以下と仮定していい気持ちになる
    • 前半と後半が打ち消し合う場合、前半で打ち消した分と後半で打ち消した分で打ち消しあえるような気がした
      • これは誤り(考察不足)
    • サンプルが通り、反例を見つけられなかったので提出
      • TLEだったものが、WAに変わる
  3. 本番終了後Kiri8128さんの提出 #8864256を参考に考察

差が常に1マスの最大値(80)以下で遷移すると仮定できないのはなぜ

経路の各マスの差が15, 35, 45, 80, 15であるような経路を考えると、+++--という途中で差が80を越えるような経路と、-++-+という差が80を越えない経路が取れるため、常に差は80以下になる気がします。 が！これは誤りで前半でお互いに打ち消しあうと、後半で出てくるものが余ってしまうケースがあります。

WAになるケースが見つけられなかったのですが、Twitterで親切な方が教えて下さいました。

累積の差が80までとして、枝刈りする実装だと、例えばこのケースで落ちます。

2 4
0 0 0 0
0 0 0 0
60 60 40 40
60 40 40 40

前半と後半を組み合わせて作る小さなパーツで、更に全体の差を小さくできる場合の考慮ができていなかったですね。

高速化が本筋だった

結局TLE解の高速化が必要になります。今回はbitsetを使った高速化が必要だったようです。

数の集合をbit列で表すことで、集合全体への足し算をbit shiftとして表現することができます。
例: S = set([1, 2, 4]) => '0b1011' = 11。（集合の要素を足し算をしているのではなく、「i番目のビットが1⇒集合Sにiが含まれる」という表現です。）

Pythonだと 1<<2*80*80 といった長いbit列も大きな整数値として扱う事ができます。

正しい実装

MAX_DIFF = 80
h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
c = [[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]

sets = [[0 for j in range(w)] for i in range(h)]
sets[0][0] = (1 << MAX_DIFF+c[0][0]) | (1 << MAX_DIFF-c[0][0])
for i in range(1, h):
    sets[i][0] |= (sets[i-1][0] << MAX_DIFF+c[i][0]
                   ) | (sets[i-1][0] << MAX_DIFF-c[i][0])
for i in range(1, w):
    sets[0][i] |= (sets[0][i-1] << MAX_DIFF+c[0][i]
                   ) | (sets[0][i-1] << MAX_DIFF-c[0][i])
for i in range(1, h):
    for j in range(1, w):
        sets[i][j] |= (sets[i-1][j] << MAX_DIFF+c[i][j]
                       ) | (sets[i-1][j] << MAX_DIFF-c[i][j])
        sets[i][j] |= (sets[i][j-1] << MAX_DIFF+c[i][j]
                       ) | (sets[i][j-1] << MAX_DIFF-c[i][j])

s = bin(sets[h-1][w-1]+(1 << (h+w)*MAX_DIFF))
min_diff = 1 << MAX_DIFF
for i in range(len(s)):
    if s[-1-i] == '1':
        min_diff = min(min_diff, abs(i-(h+w-1)*MAX_DIFF))
print(min_diff)

最大誤差分オフセットすることで、[-80, (h+w)*MAX_DIFF]の範囲をbit列で表現しています。

まとめ

  • グリッドに対して左マス・上マスだけに依存するDPで書けると気付いたところはGood
  • 前半と後半を組みあせて小さなパーツを作るケースを思いつけなかったのはBad
  • bitset: 数の集合をある数に対応させる(各要素を各bitに対応させる)ことができる
    • bitが表現する要素が等間隔に並んでいる場合、bit shiftで集合全体への足し算・引き算が表現できる

この記事はCompetitive Programming (2) Advent Calendar 2019の12/8分の記事です。

なぜ"Colorful Hats 2"に35分も掛けてしまったのか。

競技プログラミング

Colorful Hats 2は三井住友信託銀行プログラミングコンテスト2019のE問題です。本番ではこの問題に35分かかったので、振り返りをします。

f:id:matsu7874:20191201225941p:plain 三井住友信託銀行はどこに競技プログラマ需要があるのでしょうか？気になりますね。

問題概要

a = [A[0:i-1].count(A[i]) for i in range(N)] が与えられるので、そのような A = [(R|G|B) for i in range(N)] として考えられるものの個数を求める問題です。

直感的に満たすべき条件

  • 各数は最大3回までしか出現しない。

サンプルを足す

例示されているサンプルがあまりに自明なので、小さなサンプルを追加します。

9
0 0 1 0 1 2 1 2 2
96

前から順番に割り当てられるものの個数を数えていくと3*2*2*1*2*2*1*2*1 = 96になり、素直にこれを実装するとACします。

n = int(input())
a = list(map(lambda x: int(x)+1, input().split()))
MOD = 1000000007

up = [0] * (n+1)
up[0] = 3
p = 1
for i in a:
    if up[i - 1] < up[i]:
        print(0)
        exit()
    p = (p * (up[i - 1] - up[i]) % MOD)
    up[i] += 1

print(p % MOD)

何が良くなかったのか

では、なぜ私は35分もこの問題に掛けてしまったのでしょうか。

1. 「3色だから3!で*6通り」と考えてしまった

3色を使う数え上げ問題を見て、反射的に3色の対称性から「3色だから3!で*6通り」と考えてしまいました。
この考えは各a[i]に注目して、取れる選択肢の数を掛けていく方法と相性が悪く、1つ目の 0 に注目した時点で RGB の3つから1つ選ぶということが表現されています。

2. 「途中までの状態数を足し算する？」と考えてしまった

012001122みたいな入力に対して、前半の012が3通り作れることと、残った色で後半の001122を8通り作れることは 独立 なので、掛け算で大丈夫です。
残った色の部分で重複しないように調整されています。

3. 「1色しか使わないとき、2色しか使わないときのことを考慮しないと」と考えてしまった

0に使える色の数を求めるときに、考慮しているので、1色だから*3とかしなくていいです。
2色だから1色余らせて、残りの2色は入れ替え可能だから*6とかしなくていいです。
それは各a[i]を処理するときに考慮しています。

まとめ

独立なんだから掛け算しろよ!!
マスター・オブ・場合の数でもやりますか……

HACK TO THE FUTURE 2020予選の参加記

競技プログラミング

2019/11/02に行われたHACK TO THE FUTURE 2020予選に参加しました。 解法はダイクストラ（曲がり回数100ゴールからの距離を負のコスト+4近傍のブロックの個数の2乗-ゴールからのマンハッタン-5)からの不要矢印削除で、最終成績は07:32に提出した4,941,365点で143位(参加者は841人)でした。

f:id:matsu7874:20191102230224p:plain

一瞬6位になりました。

問題概要

N*Nのグリット上に矢印をいくつか出して、ロボットをゴールさせ、ゴールしたロボット数と矢印の数に応じた点数を最大化する問題でした。

やったこと

00:05 48,047 print(0)

48,047点が得られます。正の点数を得ました。

00:33 4,374,029 幅優先探索

ビジュアライザを見てみるとゴールしていないロボットがいることが分かります。 ロボットのゴールに対する加点(1000点/ロボット)が矢印を置くペナルティ(-10点/矢印)よりも大きく、全てのマスに矢印を敷き詰めたとしても点数を改善できるため、実装します。 同じ矢印に囲まれている矢印は消しました。
ゴールから幅優先探索を行い、全てのロボットがゴールできるようにすると4,374,029点が得られます。 ゴール連結な全てのマスに矢印が置かれている状態になりました。

02:32 4,907,639 シミュレータの実装

シミュレータを実装しました。 テストケースを500ケースダウンロードしてきて、手元でまとめて回せるようにしました。

if [ -e summary.csv ] ; then
    mv summary.csv summary_old.csv
fi
echo "case,score,n_goaled,n_guide,n_visited" > summary.csv
for i in $(seq 0 499); do
    python httf.py < testCase/testCase_${i}.txt > testCase/testCase_${i}.out
    cat testCase/testCase_${i}.txt testCase/testCase_${i}.out | python simulator.py summary.csv testCase_${i}.txt
    if [ $(expr $i % 20) = 0 ] ; then
        echo "finished processing testCase/testCase_${i}.txt"
    fi
done
csvstat summary.csv

csvstatを使うと各カラムの合計と分散が簡単に得られます。

  1. "case"

        Type of data:          Text
        Contains null values:  False
        Unique values:         500
        Longest value:         16 characters
        Most common values:    testCase_0.txt (1x)
                               testCase_1.txt (1x)
                               testCase_2.txt (1x)
                               testCase_3.txt (1x)
                               testCase_4.txt (1x)

  2. "score"

        Type of data:          Number
        Contains null values:  False
        Unique values:         276
        Smallest value:        96,862
        Largest value:         99,165
        Sum:                   49,385,296
        Mean:                  98,770.592
        Median:                98,892.5
        StDev:                 374.902
        Most common values:    98,886 (12x)
                               98,893 (6x)
                               98,919 (5x)
                               98,876 (5x)
                               98,909 (5x)

  3. "n_goaled"

        Type of data:          Number
        Contains null values:  False
        Unique values:         3
        Smallest value:        98
        Largest value:         100
        Sum:                   49,930
        Mean:                  99.86
        Median:                100
        StDev:                 0.375
        Most common values:    100 (435x)
                               99 (60x)
                               98 (5x)

  4. "n_guide"

        Type of data:          Number
        Contains null values:  False
        Unique values:         45
        Smallest value:        130
        Largest value:         179
        Sum:                   78,091
        Mean:                  156.182
        Median:                156
        StDev:                 8.461
        Most common values:    155 (32x)
                               159 (31x)
                               158 (26x)
                               160 (25x)
                               156 (25x)

  5. "n_visited"

        Type of data:          Number
        Contains null values:  False
        Unique values:         111
        Smallest value:        400
        Largest value:         545
        Sum:                   236,206
        Mean:                  472.412
        Median:                472
        StDev:                 24.536
        Most common values:    459 (14x)
                               466 (13x)
                               465 (12x)
                               462 (11x)
                               489 (11x)

05:33 4,907,639 何をやっても点数が改善しません

  • bfs -> dfs
    • ドツボにはまるとパネルの消費が激しい

  • 特定パターンの改善をしたい

    →↓
    ○→ とか改善できないかなと思って実装をしていましたが、無理でした。

06:07 4,913,977 敷き詰めた後使わないマスを消す

ロボットに踏まれた回数を持っておいて、0回のものを削除しました。

07:19 4,938,045 bfs -> ダイクストラ

曲がり回数を最小化したい気持ちになったので、ダイクストラ法に切り替えました。

07:32 4,941,365 ダイクストラのパラメータを探す

ゴールの近くには矢印がたくさん置かれるので、遠くから真っ直ぐ向かってきてくれると嬉しい気持ちになったので、距離を負のコストに追加していました。 ブロックの多いゾーンは嫌な気持ちになったので、4近傍のブロック数をコストに追加しました。

この後は踏むマスの数を考えないといけないか……というところで時間切れです。

感想

これまでのマラソンマッチの中では、順位が良かったほうですが、探索が全くできず実行時間は２秒以上余らせてしまって、申し訳ない気持ちです。 本戦出場の皆さん頑張ってください。

解説放送を見て復習します。

コンテストの開き方(ゆるふわ競技プログラミングオンサイト編)

競技プログラミング

先日ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状という32人規模のオンサイトコンテストを開催したmatsu7874です。

というchokudaiさんのツイートを見たので、ゆるふわ競技プログラミングオンサイトについて、コンテスト準備の流れを書こうと思います。主にHackerRankでの開催を念頭においています。

ゆるふわ競技プログラミングオンサイト第1回は2019/02/09に開催していて、その時の記事はこちら。 また、今回のコンテストに関して、作問部分の様子はprd_xxxさんが下記のブログで書いてくれているので、ぜひ読んでください。

3ヶ月前

  • 日程を決める
    • 参加者層が重なる他のイベントと被らないように調査する
  • 会場スポンサーと懇親会スポンサーを探す
    • 私の場合は自社でやる承認をもらう
    • 想定参加者数・参加者層（社会人・学生）とざっくりとしたタイムテーブルがあるとよい
  • 告知を出す(connpassページを公開)
    • 初回は先着順にしてみた。特定のクラスタの参加者が多かったため、次回はある程度早い人の中で抽選とした。
    • ２回目は告知から3日後に抽選としてみた。2日目には32人の枠を超える応募があった。
  • GitHubにプライベートリポジトリを作る
  • CIの設定をする

2ヶ月前

1ヶ月前

  • テスターをお願いする
    • 私は青なので、自分より強くたくさんのコンテストに参加している人にお願いしています。

当月

  • 解説を用意する
  • HackerRankに問題を登録する
    • まあまあ時間がかかり、集中力の必要な作業なので、時間にゆとりを持ってやるべし。
      • Contestを作って、ModeratorsにWriter,Testerを登録
      • Manage ChallengesからChallengeを作成
      • Contestに"Add Challenge"
      • 全てのテストケースに想定解を返した場合のみACとしたい場合は、Binaryにチェックをつける。つけない場合は想定解と一致したテストケース数に応じた点数が与えられる。
      • ChallengeのModeratorsにもWriter,Testerを登録しておくと、いざというときに対応しやすい。
      • 問題のDetailsでLanguageをEnglishから変更すると、作業忘れによってある言語では修正が反映されないという事故が起こるので気をつける（複数言語用意しないならEnglish限定で良い）
      • Test CasesタブでSampleにチェックを入れておくと、提出前に動作確認できる機能がある
    • コンテスト名が数字のみだとコンテストが開催できない不具合があるっぽい？
  • 名札を用意する
    • 頑張って作る

当日

  • スタッフが最低二人は必要と思う
  • 会場設営
    • Wifi
    • 電源
    • テーブル・椅子
    • 名札
  • お菓子・飲み物を用意する
  • ピザ
    • 学生は人数/3くらいが丁度いい？
      • 人数/4だと秒で消える
    • 取るなら懇親会直前がいいよ
      • せっかくのピザが冷めてしまうため
  • コンテスト中はClar対応をする
  • 片付け
    • 懇親会の片付けは地味に大変

ざっとこんな感じでしょうか。今後、有志コンテストを開く方の参考になれば幸いです。

技術広報チームのリーダーになりました

最近、技術広報チームのリーダーになりました。技術イベントの会場提供・懇親会提供などやって行きたいと思っています。
作問したのでオンサイトイベントにしたい！という方がいらっしゃいましたら、Twitter/@matsu7874などで連絡いただけたら嬉しいです。
新宿駅直結なのでアクセスがいいオフィスで、机ありなら32人くらい、椅子だけなら60人くらい(詰めれば100人)入れる会議室があります。

Rimeの使い方 誤答の区別とHackerRank用の出力方法について

競技プログラミング

この記事では作問補助ツールRimeの使い方のうち、誤答の種類を区別する方法とHackerRank用のzipファイルの作り方を解説します。 その他の情報が欲しい方は、下記の記事と公式ドキュメントを読みましょう。ほとんどのことが書かれています。

f:id:matsu7874:20190821005037p:plain f:id:matsu7874:20190821005524p:plain
誤答の区別とHackerRank用の設定

誤答の種類（TLE, WA）を区別したい

Rimeは想定誤答をACしないことを確認するために、SOLUTIONファイルに challenge_case を設定することができます。

## Solution
script_solution(src='bruteforce.py', challenge_cases=[]) # shebang line is required

上記のように書くと、該当スクリプトが少なくとも1つ以上のケースでACにならないことを表明できます。
WAのみ、TLEのみという風に特定の結果になることを期待する場合は、 expected_verdicts に値を設定します。

TLE, ACのいずれかの結果になることを期待する場合は下記のように書きます。

## Solution
script_solution(src='bruteforce.py', challenge_cases=[]) # shebang line is required
expected_verdicts([TLE, AC])

※配列内は文字列ではなく、定数。

HackerRank用の出力を得たい

デフォルトでは rime pack の結果としてAtCoder用の出力が得られますが、HackerRank用のzipファイルも作成可能です。

  1. PROJECTファイルで #use_plugin('judge_system.hacker_rank') の # を外し、有効化
  2. rime pack 時に各問題ディレクトリの rime-out/hacker_rank 以下に hacker_rank.zip が作られる

私が競プロerと働きたい理由

競技プログラミング

競プロerとは

この記事で「競プロer」といえば、AtCoderとかCodeforcesとかのような、1~2時間で4~6問題に取り組む形式のコンテストに頻繁に参加しているプログラマのこととします。

競技プログラミングには、ゲームAI(CodingGame)とか最適化(TopcoderのMM)の分野もありますし、それらが得意な人とも働きたいですが、この記事ではスコープ外とします。

競プロerを特徴づける要素と業務にどう役に立つか

競プロerにもすごく強い人から初級者まで幅広い人がいるので、特徴を獲得するランクと特徴をまとめました。 競プロerに馴染みの深い色で言うと、SS=橙、S=黄色、A=青、B=水色です。

ランク 競プロerの特徴 業務上の役立ちポイント
S 難しい問題が解ける ほとんどの人が解決できない問題を、短時間で解決できる
S データ構造を適切に選択できる 計算リソースを大幅に削減することができる
A~S どう制約を変化させれば高速化できるか考えられる 現実の問題を考えるときに重要
A~S 高速化の勘所を把握している ロジックの高速化を短時間で行う事ができる
A アルゴリズムを適切に選択できる 闇雲に調べるより、圧倒的に時間短縮になる
B~A 時間をかければアルゴリズムのボトルネックが特定できる アルゴリズムの改善を始められる
B~A 日本語で書ける任意のロジックをC++で実装できる どう書けばいいか分からなくて悩むことがない
B 肌感覚で計算量の見積もりを行える 無限に終わらないクエリを投げなくて済む
B 短時間で実現したい処理を実装できる 高速に仮説検証を回せる
B 趣味としてプログラミングをしている 今後も成長が期待できる

Bまではどこの会社でも嬉しい特徴で、A以上は会社によってはオーバースペックでしょうか。

AtCoder Jobsを見てみる

AtCoderJobsの中途採用で要求ランクA以上の求人について、業務内容を見てみましょう。

要求 会社名 業務内容
S 株式会社科学計算総合研究所 数値計算、形状処理および機械学習
A 株式会社フィックスターズ 自動運転を実現するためのソフトウェア開発
A 株式会社フィックスターズ 機械学習アルゴリズムを利用したソフトウェア及びソリューションの開発
A 株式会社フィックスターズ マルチコアプロセッサの性能を最大限に引き出すソフトウェアの開発
A アスプローバ株式会社 スケジューリングアルゴリズムの改善
A フォルシア株式会社 膨大で複雑なデータを対象とする検索システムの構築
A 600株式会社 無人コンビニ『600』の開発
A SoundHound Inc. 音声認識プラットフォームの日本語対応

それぞれの求人ごとに特徴はありますが、実装難度の高い課題に取り組んでいますね。 高速化・高度なアルゴリズムだけではなく、純粋にC++を使いこなせるという部分も評価が高いようです。

要求B以下は、ゲームAIや最適化といった能力に秀でたプログラマを採用したい企業が多めでしょうか。

やはり、AtCoderJobsに求人を出している企業は競プロerを採用したいようですね！

つまり？

仕事できる同僚とワクワクする課題に向き合って働けるの最高やん？

宣伝

21卒向けサマーインターンを募集しています。今週末が募集締め切りです。

FORCIA Summer Internship 2019：フォルシア株式会社

『ナルハヤのつるぎ』を競技プログラマーが遊ぶ

ボードゲーム 競技プログラミング

『ナルハヤのつるぎ』という面白いゲームを手に入れたので、競技プログラミングの問題風にして遊んでみたいと思います。

『ナルハヤのつるぎ』とは？

6枚のカードを組み合わせてお題の剣を揃えるスピード系パズルゲーム。


【GM2019春】ナルハヤのつるぎ 紹介動画

問題風にする

１枚のカードには上下×裏表で4種類の絵柄が書かれている。 N枚のカードを並び替えて、お題と同じ絵柄を構成する

入力形式

  • 使うべきカードの枚数N
  • 各カードの絵柄が表上、表下、裏上、裏下の順で与えられる
    • 絵柄には180度回転したときに同じ模様になるもの(0)と異なる絵柄になるもの(-1,1)がある。
    • D=0が存在するSについて、D=-1,1は存在しない。
  • 作るべき剣の本数M
  • 各剣について
    • 長さL
    • 上から順に絵柄の種類と向き
N
S_11 D_11 S_12 D_12 S_13 D_13 S_14 D_14
...
S_N1 D_N1 S_N2 D_N2 S_N3 D_N3 S_N4 D_N4
M
L1
S_11 D_11 ... S_1L1 D_1L1
...
LM
S_M1 D_M1 S_M2 D_M2 ... S_MLM D_MLM

制約

  • 1 <= M <= N
  • N+M <= Lの総和 <= 2*N
  • 0 <= S < 8
  • -1 <= D <= 1

出力

  • カードiについて、剣Sの上からP番目に置く
    • カードをそのまま使う場合はR=0
    • カードを上下回転させる場合はR+=1
    • カードを裏表反転させる場合はR+=2
  • 上半分の絵柄が見える場合はU=1、見えない場合はU=0
  • 下半分の絵柄が見える場合はD=1、見えない場合はD=0
  • U=0かつD=0のカードが存在してはならず、同じ位置に複数のカードが=1で置かれてはならない。（無理なので）
S_1 P_1 R_1 U_1 D_1
...
S_N P_N R_N U_N D_N

構成する方法が複数ある場合はどれを出力しても良い。

例

3
0 0 1 1 0 0 2 1
3 0 2 1 4 -1 2 1
0 0 2 1 1 1 1 1
2
2
0 0 1 1
3
2 -1 1 1 1 1
1 1 0 1 1
2 1 1 1 0
2 2 2 1 1

1枚目のカードは剣1の先頭（位置1）にそのまま上も下も見える状態で置く。 2枚目のカードは剣2の先頭（位置1）に上下回転して上(2,-1)だけ見える状態で置く。 3枚目のカードは剣2の位置2に裏表反転して、上も下も見える状態で置く。

checkerを書く

// TODO: これはやるだけ

generatorを書く

// TODO: これはちょっとむずい

validatorを書く

// TODO: これはやるだけ

solverを書く

// TODO: Nいくつまで解けるだろうか？

まとめ

面白いゲームなので遊んでみてください。