BrainPadプログラミングコンテスト記念LT会2025_社内イベント&問題解説

2025年6月25日に実施した、BrainPadプログラミングコンテスト2025 開催記念LT会でのブレインパッド田口の登壇スライドです。

イベントURL
https://brainpad.connpass.com/event/359630/

コンテストURL
[BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046） - AtCoder]
https://atcoder.jp/contests/ahc046

Transcript

1. BrainPadプログラミングコンテスト開催記念LT会 BrainPadプログラミングコンテスト2025 社内イベント&問題解説 2025年6月25日
2. 2 ©BrainPad Inc. Strictly Confidential 自己紹介 入社 田口 雅也 Taguchi Masaya 2024年新卒入社 職種 専攻 数学（最適化アルゴリズム） # DC計画問題 # 逆凸計画問題 趣味 • ドラム • 温泉 • 旅行 案件 • 2024年7月〜：配送計画問題 データサイエンティスト
3. 3 ©BrainPad Inc. Strictly Confidential アジェンダ 1. プログラミングコンテストを協賛するにあたって社内で実施したイベント 2. BrainPadプログラミングコンテスト2025（AHC046）問題&解法紹介
4. ©BrainPad Inc. Strictly Confidential プログラミングコンテストを協賛するにあたって社内で実施したイベント
5. 5 ©BrainPad Inc. Strictly Confidential AtCoder社のコンテストに初協賛し BrainPadプログラミングコンテスト2025 （4/26 15:00-19:00 AtCoder Heuristic Contest 046） を開催しました！
6. 6 ©BrainPad Inc. Strictly Confidential コンテスト開催記念社内イベント 未経験者も気軽に参加できるワークショップと交流会を開催し、コンテスト参加へのハードルを下げるとと もに、社内のコミュニケーション促進を図りました。 ✓ 実際に問題を解くことで、コンテスト参加へのハードルを下げる ✓ ヒューリスティックコンテストの概要を知り、興味を持ってもらう コンテスト開催記念ワークショップ コンテスト開催記念交流会 ✓ 競プロerと未経験者との交流
7. 7 ©BrainPad Inc. Strictly Confidential 社内勉強会（b2b：BrainPad to BrainPad） ブレインパッドでは年間300回以上の社内勉強会（b2b）が開催されています。AIやデータサイエンス、エン ジニアリングに関わる最先端の知識・技術などを、日常的に学ぶことができます。 ブレインパッド社内勉強会一覧（抜粋） Kaggle：LLMコンペ振り返り 因果推論勉強会 LLM論文レビュー会 ベイズ最適化をゼロから 競技プログラミングは本当に役に立つのか？ 1on1をどうやっているか 職務経歴書の変遷お見せします asano/アサノ「2023年のブレインパッドの社内勉強会を公開！！！」
8. 8 ©BrainPad Inc. Strictly Confidential 勉強会兼交流会（白金鉱業Meetup） ブレインパッドのデータサイエンティスト/機械学習エンジニアが社外のデータ系の仕事をしている人と交流 したい！と始まった勉強会兼交流会イベントです。 白金鉱業Meetupイベント一覧（抜粋） AIエージェント データマネジメント 数理最適化 効果検証 若手データサイエンティスト交流会 実務におけるLLM、あるある課題共感し合おう！ ダイナミックプライシング データサイエンティストが集まる夜 白金鉱業Meetup Vol.15 効果検証 開催レポート | DOORS DX 登壇の様子 イベント後の懇親会
9. 9 ©BrainPad Inc. Strictly Confidential オウンドメディアの紹介 DOORS @doors_brainpad ブレインパッド公式技術メディア 生成AI・LLMやデータサイエンスプロジェクトについて発信しています！ OpenBP @Open_BrainPad 会社の神資料を公開するプロジェクト 統計学の資料がITmediaとNIKKEIリスキリングに取り上げられました！ 白金鉱業FM @shirokane_fm 会社のみんなでやっているpodcast 高校の放送部的なノリでデータサイエンスについて語っています！
10. ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025（AHC046） 問題&解法紹介
11. 11 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜問題 ◼ 問題概要（Skating with Blocks） • 20×20のマス目からなるスケートリンクがある。スケートリンク の外部はすべてブロックで覆われており、通過できない。初期状態 では、スケートリンクの内部にブロックは存在しない。 • あなたは初期位置におり、各ターンでは上下左右のいずれかの方向 を指定し、「行動パターン」のいずれか1つを選んで実行できる。 • できる限り少ないターン数で1~39のすべての目的地を順番通りに 訪れよ。ただし、目的地を訪れたと判定されるには”移動”でそのマ スに到達するか、”滑走”でそのマスに停止する必要がある。 ◼ 行動パターン 移動 滑走 変更 指定した方向に隣接する マスへ1マス移動する。 指定した方向へ、ブロッ クにぶつかるまで直線的 に滑走する。 指定した方向に隣接する マスに対し、ブロックを 設置/除去する。 既にブロックがある 場合は除去 20×20のマス目からなるスケートリンク BrainPadプログラミングコンテスト2025（AtCoder Heuristic Contest 046）
12. 12 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（1/8） 今回は「変更」を使用しないで解く方法を紹介します。 20×20のマス目からなるスケートリンク 初期位置 (3, 7) 目的地 (14, 16) 考え方 まず最初に、現在の状況を確認します。 • 初期位置：（3, 7） • 最初の目的地：（14, 16） この2点間を最短で移動するための経路を考えます。
13. 13 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（2/8） 「移動」のみで最短経路を考えます。 20×20のマス目からなるスケートリンク 考え方 ① (“右”の”移動”)×9 ② (“下”の”移動”)×11 初期位置 (3, 7) 目的地 (14, 16) まず最初に、現在の状況を確認します。 • 初期位置：（3, 7） • 最初の目的地：（14, 16） この2点間を最短で移動するための経路を考えます。 最短経路は複数考えられますが、以下はその一例です。 • ① “右”に9回”移動”し、 • ② “下”に11回”移動”する 20 ターン
14. 14 ©BrainPad Inc. Strictly Confidential 右方向への移動について2パターンを右図に示しています。 この図からも分かるように、右図のケースでは「滑走 + 移動」を活用した方が、必要なターン数を少なく抑える ことができます。 BrainPadプログラミングコンテスト2025｜解法（3/8） 今回の問題は、できる限り少ないターン数で1~39のすべての目的地を順番に訪れることが得点に直結します。 ここからは、ターン数を削減するために滑走を利用した効率的な移動方法をご紹介します。 考え方 (“右”の”移動”)×9 初期位置 (3, 7) 初期位置 (3, 7) ① (“右”の”滑走”)×1 ② (“左”の”移動”)×3 “移動”のみ “滑走” + “移動” 9 ターン 4 ターン 移動 滑走 指定した方向に隣接する マスへ1マス移動する。 指定した方向へ、ブロッ クにぶつかるまで直線的 に滑走する。
15. 15 ©BrainPad Inc. Strictly Confidential 下方向への移動について2パターンを右図に示しています。 この図からも分かるように、右図のケースでも「滑走 + 移動」を活用した方が、必要なターン数を少なく抑える ことができます。 BrainPadプログラミングコンテスト2025｜解法（4/8） 同様に、下方向の移動も滑走を活用した方が必要なターン数を少なく抑えることができます。 “移動”のみ “滑走” + “移動” 目的地 (14, 16) 目的地 (14, 16) 位置 (3, 16) 位置 (3, 16) (“下”の”移動”)×11 (“下”の”滑走”)×1 (“上”の”移動”)×5 11 ターン 6 ターン 考え方 移動 滑走 指定した方向に隣接する マスへ1マス移動する。 指定した方向へ、ブロッ クにぶつかるまで直線的 に滑走する。
16. 16 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（5/8） 「滑走」を活用したことで必要なターン数を抑えることができました。 初期位置 (3, 7) 目的地 (14, 16) ② (“左”の”移動”)×3 ① (“右”の”滑走”)×1 ③ (“下”の”滑走”)×1 ④ (“上”の”移動”)×5 10 ターン 「滑走」を活用した方法 「移動」のみを活用した方法 ① (“右”の”移動”)×9 ② (“下”の”移動”)×11 初期位置 (3, 7) 目的地 (14, 16) 20 ターン
17. 17 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（6/8） 方向を切り替える位置は、現在の位置と目的地が分かれば求めることができます。 これを利用して「移動のみ」と「滑走 + 移動」の移動回数をそれぞれ求めることができます。 (1, 0) (1, 2) 目的地 (4, 2) (1, 0) (1, 3) 目的地 (4, 3) “移動”のみが最適なケース (“滑走” → “移動”)が最適なケース 2回の”移動” 3回の”移動” 1回の”滑走” & 2回の”移動” 1回の”滑走” & 1回の”移動”
18. 18 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（7/8） 方向を切り替える位置を一般化したものです。 現在の位置が(𝑖0 , 𝑗0 )、目的地が(𝑖1 , 𝑗1 )の場合、方向を切り替える位置は(𝑖0 , 𝑗1 )になります。 (𝒊𝟎, 𝒋𝟎) (𝒊𝟎, 𝒋𝟏) (𝒊𝟎, 19) 目的地 (𝒊𝟏, 𝒋𝟏) (𝒋𝟏 – 𝒋𝟎 )回の”移動” 1回の”滑走” & (19 – 𝒋𝟏 )回の”移動” ◼ 擬似コード 考え方 「移動のみ」と「滑走 + 移動」の移動回数を右図のよう に計算し、値が小さい移動方法を採用します。
19. 19 ©BrainPad Inc. Strictly Confidential BrainPadプログラミングコンテスト2025｜解法（8/8） 今回紹介した解法で実装したときのアニメーション※ 今回紹介した解法で実装したコードはこちら ※PDF形式ではアニメーションをご覧いただけません。
20. 株式会社ブレインパッド 106-0032 東京都港区六本木三丁目1番1号 六本木ティーキューブ TEL：03-6721-7002 FAX：03-6721-7010 www.brainpad.co.jp info@brainpad.co.jp 本資料は、未刊行文書として日本及び各国の著作権法に基づき保護されております。本資料には、株式会社ブレインパッド所有の特定情報が含まれており、これら情報に基づく本資料の内容は、貴社以外の第三者に開示されること、また、本資料を評価する以外の目的で、その 一部または全文を複製、使用、公開することは、禁止されています。また、株式会社ブレインパッドによる書面での許可なく、それら情報の一部または全文を使用または公開することは、いかなる場合も禁じられております。 ©BrainPad Inc.