第12回 Asprova プログラミングコンテスト （AtCoder Heuristic Contest 053） 8位解法
>100 Views
September 26, 25
スライド概要
コンテスト後の懇親会で使用したスライドです。
ᓚᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᘏᗢ
関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.1M
各ページのテキスト
第12回 Asprova プログラミングコンテスト （AtCoder Heuristic Contest 053） “Random Sum Game” 8 位解法 2025/09/26 表彰式・懇親会 hitonanode
2 問題概要 • 正の整数列 をあらかじめ宣言してください • その後、50 個の目標値 が与えられるので、各 に近い値 を宣言した数の部分和で作ってください。ただしそれぞれの数は一度しか使えません … …
今回の内容について • 既に AHC053 のページに投稿した解説もご参照ください • https://atcoder.jp/contests/ahc053/editorial/13877 3
後半パートの貪欲アルゴリズム 以下の単純なルールベース手法（以降「例の貪欲」と呼ぶ）が良好に動く • は降順ソートしておき、先頭の要素から順に、現在目標値に対する不足が 以上のも のがあれば、その中で不足が最小のものに割り当てていく • Q. なぜ「最小のもの」に割り当てるのですか？ • A. いろいろ実験するとこれがよい • A. 最大のものに割り当てていくと、全てを均等に削っていくことになり、のち のち空きに収まらない要素が出てきてしまいやすい 4
数列 の構築方法 • 今回の問題は は事前に決められるので、計算時間をかけてよい • そこで、以下の手続きで構築する • 最初にたくさんのテストケースを手元で生成する • （空の配列）から始め、以下の操作を 500 回やる • 現在の を使って各テストケースに「例の貪欲」を適用する • 「例の貪欲」適用後の空き状況から、 に「いい感じの」値の要素を追加する • どうやって？ 5
6 追加する値の決め方 「例の貪欲」後の最大の空きを各テストケースで計算、それを最も多く削れる要素を追加 テストケース1 テストケース2 テストケース3 （最大長方形） テストケース4
構築された • 先頭 50 要素は に含まれる値の分布（片対数表示） 以上となる • 51 要素目以降は概ね指数的だが、51〜90 要素目あたりは若干上振れしている？ • → いわゆる「 以上 50 個 + 指数減衰 450 個」方針について、指数減衰の最初の 方は少し上振れさせておいた方がよかったりする？（未検証） 7
謎（微妙な点） • 「何個のテストケースを生成するか」がパラメータになってしまっている • 特に最初の 50 要素は基本的に「各 の全テストケースにわたる最小値」になるの で、テストケース数を増やすと最初の 50 要素の値が小さくなっていく • 自分が色々試した感じでは、1,000 個くらいがちょうどよかった • たまに大失敗するが、大失敗込みでスコアの平均値が最良 • 後半パートで真面目に探索したり、少々の超過を許容するともっとよくなるかも 8