| 問題 | 日時 | 時間 | 概要と目標 | 入出力 | スコア | 解説リンク |
|---|---|---|---|---|---|---|
|
2026/05/16 15:00 |
4時間 |
概要: 20×20倉庫にループ状のベルトコンベアを最大N2個設置し、各コンベアを回転させて箱を搬出口へ運び、番号の小さい順にすべて搬出する問題。 目標: 各マスが属するコンベア数を高々2個に抑えつつ長さ2以上のループを設置し、最大105回の回転操作で全箱をできるだけ少ない手数で搬出する。 |
入力: Nと初期配置ai,jが与えられる。全ケースでN=20、aは0からN2-1までの順列。 出力: まずコンベア数Mと各ループの座標列を出力し、続いて操作回数Tと各操作のコンベア番号mt、方向dtを出力する。 |
全N2箱を搬出できれば106+round(106log2(105/T))点。未完了時は搬出割合で得点。 |
|
|
|
2026/04/26 15:00 |
4時間 |
概要: 10本の出発線に乱れて並ぶ100両の車両を、待避線との間で連続ブロックとして移動し、同一ターン内の移動経路が交差しない制約の下で各出発線をID順に並べ直す問題。 目標: 最大4000ターンで、出発線rにID 10rから10r+9の車両を先頭から順に配置する。1ターンに複数移動できるが、同じ線の重複使用と移動経路の交差は禁止。 |
入力: Rと各出発線の初期車両ID Yr,cが与えられる。全ケースでR=10、IDは0から10R-1の順列。 出力: ターン数Tの後、各ターンの移動数Ktと、各移動 type i j k を出力する。typeは出発線から待避線、または逆方向。 |
完全一致なら100R+4000-T点。未完成時は車両ごとに正しい出発線1点、位置も正しければ追加9点。150ケース合計。 |
||
|
2026/04/03 19:00 |
240時間 |
概要: 色付き餌が散らばるN×N盤面で蛇を動かし、食事でしっぽ色を伸ばし、胴体を噛みちぎると後半が餌に戻る性質を使って、最終的な蛇の色列を好みの色列に近づける問題。 目標: 最大100000手のU/D/L/R操作で餌を食べたり蛇を切ったりし、最終的な長さkと色列cを好みの列dに近づけつつ、操作列も短くする。 |
入力: N, M, C、好みの色列d、初期盤面fが与えられる。Nは8-16、MはN2/4から3N2/4、Cは3-7。 出力: 各ターンの移動方向を表すU/D/L/Rを1行ずつ出力する。Uターンや盤面外移動は指定できない。 |
絶対スコアはT+10000×(E+2(M-k))で小さいほど良い。ケース内順位から順位スコアを計算し、その合計で評価。 |
||
|
2026/03/14 15:00 |
4時間 |
概要: 200×200の全区画をキング移動でちょうど一度ずつ訪問するツアーを作る問題。k日目に訪れた区画の住民数Ai,jにkを掛けた好感度が得られる。 目標: 縦・横・斜めに隣接する区画だけを連続して訪問するハミルトン路を作り、住民数の大きい区画をできるだけ後半の日に訪問して総好感度を最大化する。 |
入力: N=200固定。各区画の住民数Ai,jが与えられ、1からN2までの整数の並び替えになっている。 出力: N2行で訪問順の座標(ik,jk)を出力する。全座標は相異なり、連続2点はキング隣接である必要がある。 |
V=Σk×Aik,jkに対しround(V/N2)点。100ケース合計で評価。 |
||
|
2026/03/01 13:00 |
6時間 |
概要: 20×20盤面を警備するロボット群を有限オートマトンで制御するチーム戦3問構成の問題。ロボットは前方に壁があるかと内部状態に応じて、直進・右折・左折と次状態を決める。 目標: 導入するロボット数K、各ロボットの状態数mk、初期位置・向き、遷移規則、追加壁を設計し、全マスが周期的に警備される条件を満たしつつ導入コストVを小さくする。 |
入力: N=20固定。問題A/B/Cごとに異なるコスト係数AK, AM, AWと、既存の横壁v・縦壁hが与えられる。 出力: ロボット数、各ロボットの状態数・初期位置・初期方向・状態ごとの遷移、最後に追加壁の01文字列を出力する。 |
係数AK,AM,AWで計算される導入コストVに対し、1+round(106×max(0,log2((AK(N2-1)+AMN2)/V)))点。 |
|
|
|
2026/02/13 19:00 |
240時間 |
概要: 複数プレイヤーの陣取りゲームをプレイヤー0として戦うインタラクティブ問題。各マスには価値とレベルがあり、移動後に占領・強化・攻撃・反撃が発生する。 目標: AIプレイヤーと同時に行動する各ターンで、自領土経由で到達可能な移動先を選び、価値の高い領土の獲得・強化・奪取を通じて自分のスコアS0をAI最大スコアより大きくする。 |
入力: 初期入力としてN, M, T, U、各マス価値Vi,j、各プレイヤー初期領土が与えられる。各ターン後に全駒位置、所有者、レベルが返る。 出力: 各ターンでプレイヤー0の移動先(tx0,ty0)を出力し、flushする。移動先は到達可能領土または隣接マスでなければならない。 |
round(105×log2(1+S0/SA))が絶対スコア。各ケースで最大絶対スコアとの比により相対評価。 |
||
|
2026/02/01 19:00 |
4時間 |
概要: ショップとアイスの木からなる無向グラフ上を移動し、木でW/Rのアイスを収穫してコーン文字列を作り、ショップへ納品して在庫集合の種類数を増やす問題。木は行動2でWからRへ変えられる。 目標: 直前の移動元へ戻れない制約の下で最大T=10000手移動し、ショップごとの納品文字列集合Siの種類数合計をできるだけ増やす。 |
入力: N=100, K=10, T=10000。グラフの辺、各頂点の座標が与えられる。頂点0..K-1がショップ、K以降が木。 出力: T行以下で、移動先頂点vを出力するか、現在のWの木をRに変える行動として-1を出力する。 |
Σ|Si|がそのまま得点。150ケース合計で、得点は大きいほど良い。 |
||
|
2026/01/10 15:00 |
4時間 |
概要: 20×20盤面に2枚ずつ置かれた同番号カードを、移動・拾う・置く操作で山札上でペアにして消していく問題。山札の上2枚が一致すると自動で取り除かれる。 目標: 盤面上を移動しながらカードを拾ったり一時的に置いたりして、全カードを盤面と山札から消す。操作上限内で、評価対象となる移動回数をできるだけ少なくする。 |
入力: N=20固定。各マスのカード番号ai,jが与えられ、0からN2/2-1までの各番号がちょうど2回現れる。 出力: 操作列を1文字ずつ出力する。移動はU/D/L/R、カードを拾う操作はZ、置く操作はX。 |
全消去ならN2+2N3-K点、残りX枚ならN2-X点。Kは移動回数。150ケース合計。 |
||
|
2025/12/14 15:00 |
4時間 |
概要: LevelとIDを持つ機械群を500ターンで強化し、りんご生産を最大化するインクリメンタルゲーム。低Level機械はりんごを生産し、高Level機械は下位機械の台数を増やす。 目標: 各ターンで機械jiを強化するか何もしないかを選び、強化コストと将来の複利的な生産増を見比べて、最終ターン後のりんご数Sを最大化する。 |
入力: N=10, L=4, T=500, K=1固定。Level 0の生産能力Ajと各機械の初期コストCi,jが与えられる。 出力: ちょうどT行、強化する機械のLevel iとID j、または何もしない場合は-1を出力する。 |
Tターン後のりんご数Sに対しround(105×log2S)点。150ケース合計で評価。 |
|
|
|
2025/11/29 15:00 |
4時間 |
概要: トーラス平面上を等速で動く300個の点を、任意時刻に結合して10個のサイズ30の連結成分へまとめる問題。結合コストはその時刻の点間距離で、距離が小さいタイミングを選ぶ必要がある。 目標: 時刻0からT-1の間にN-M回の結合を指定し、最終的にちょうどM=10個、各サイズK=30の成分を作りながら結合距離の総和Dsumを小さくする。 |
入力: N=300, T=1000, M=10, K=30, L=105固定。各点の初期位置(x,y)と速度(vx,vy)が与えられる。 出力: ちょうどN-M行、各行に結合時刻tと点i,jを出力する。同一成分内の再結合は不可。 |
round(106×log2(L×(N-M)/(Dsum+1)))点。150ケース合計で、得点は大きいほど良い。 |
||
|
2025/11/07 19:00 |
240時間 |
概要: 壁のあるグリッド上のロボットを、マス色と内部状態だけに依存する遷移規則で動かし、指定された目的地列を順に訪問させる問題。初期色配置、色数C、状態数Q、遷移規則を設計する。 目標: 位置そのものを参照できない制約の下で、色の塗替えと内部状態遷移を使い、ステップ上限T以内に全目的地を順に訪問しつつ、使用する色数Cと状態数Qの和を小さくする。 |
入力: N, K, T、横壁v・縦壁h、K個の目的地座標が与えられる。Nは10-20、KはNからN2。 出力: 使用色数C、状態数Q、初期盤面色、そして各(色,状態)に対する塗替え色・次状態・移動方向の遷移規則を出力する。 |
全K目的地を訪問できた場合はC+Qが絶対スコアで小さいほど良い。未達の場合は大きなペナルティが付く。 |
||
|
2025/10/19 19:00 |
4時間 |
概要: 200個の宝箱を素手または開封済み宝箱から得た武器で攻撃し、すべて開ける問題。各武器には耐久値があり、武器wで宝箱bを攻撃するとAw,bだけ硬さを減らす。 目標: 武器の入手順、耐久値、宝箱ごとのダメージ効率を考慮して攻撃手順を決め、すべての宝箱をできるだけ少ない攻撃回数で開ける。 |
入力: N=200、各宝箱の硬さHi、武器耐久Ci、武器iで宝箱jを攻撃したダメージAi,jが与えられる。 出力: 各攻撃について、使う武器番号Wtと宝箱番号Btを出力する。素手の場合はWt=-1。 |
攻撃回数Tに対しΣHi-T+1点。150ケース合計で、得点は大きいほど良い。 |
||
|
2025/09/19 19:00 |
240時間 |
概要: 入口から花を探す冒険者を、森の木を動かして誘導・妨害するインタラクティブ問題。冒険者は確認済みマスと暫定地図を使って目的地へ進み、既に確認された場所へ木を置くと失敗する。 目標: 各ターンで冒険者の視界・目的地選択・移動に応じて、未確認マスの木配置を調整し、花には必ず到達させつつ到達までの移動回数をできるだけ長くする。 |
入力: N、初期の森、入口、花の位置などが与えられ、ターンごとに冒険者位置や確認済み情報を受け取る。 出力: 各ターンで移動させる木の配置変更を出力する。確認済みマスへの不正配置や到達不能化は避ける必要がある。 |
花に到達するまでの移動回数が絶対スコアで、大きいほど良い。各ケースで最大絶対スコアとの比から相対評価される。 |
|
|
|
2025/09/13 19:00 |
4時間 |
概要: 事前にN枚のカードへ整数Aiを書き、後から生成され昇順に並べられたM個の巨大な目標値Bjに対し、カードを捨てたりM山へ分けたりして各山の和を近づける問題。 目標: Bjが分かった後、使用するカードとM個の山への割当を決め、各山の合計SjとBjの絶対誤差総和Eをできるだけ小さくする。 |
入力: N=500, M=50, L=1015-2×1012, U=1015+2×1012の固定情報と目標値Bが与えられる。 出力: 最初に各カードの値Aiを出力し、続けて各カードを捨てるか、どの山に入れるかを表す割当を出力する。 |
E=Σ|Sj-Bj|に対しround((20-log10(1+E))×5×107)点。150ケース合計。 |
||
|
2025/08/23 15:00 |
4時間 |
概要: 壁のある30×30グリッドを10台のロボットで掃除する問題。開始前に10個のボタンそれぞれについて、各ロボットの行動(U/D/L/R/S)を固定し、その後はボタン列だけで全マス訪問を目指す。 目標: ロボットごとに異なるボタン割当と、最大2N2回のボタン操作列を設計し、できるだけ少ない操作回数で全てのマスをワックスがけする。壁で移動できない場合はその場に留まる。 |
入力: N=30, M=10, K=10固定。各ロボット初期位置と、横壁v・縦壁hを表す01文字列が与えられる。 出力: K個のボタンに対する各ロボットの行動文字を出力し、その後に押すボタン番号の列atを出力する。 |
未訪問R=0なら3N2-T点、R>0ならN2-R点。150ケース合計で評価され、得点は大きいほど良い。 |
||
|
2025/08/01 19:00 |
240時間 |
概要: N種類のごみを正しい処理装置へ送るため、処理装置と確率的な分別器を平面上に配置し、交差や閉路を避けてベルトコンベアで接続する問題。分別器は種類ごとの確率pi,jで出口1/2へ振り分ける。 目標: 各ごみ種が対応する処理装置へ届く確率qiを高めるように、処理装置の割当、搬入口からの接続、分別器の設置種類と2出口の接続先を決める。ベルトコンベア同士は不正に交差せず、有向グラフは閉路を持たない必要がある。 |
入力: N, M, K、N個の処理装置設置座標、M個の分別器設置座標、K種類の分別器ごとの確率pi,jが与えられる。 出力: 各処理装置設置場所に置くごみ種、搬入口の接続先、各分別器設置場所について未設置または分別器種類と出口1/2の接続先を出力する。 |
絶対スコアはround(109×平均(1-qi))で小さいほど良い。各ケースで最小絶対スコアとの比による相対評価スコアを得る。 |
|
|
|
2025/07/16 09:00 |
10時間 |
概要: 壁のある30×30盤面でK台のロボットを目的地へ運ぶ問題。開始前に追加壁を置き、ロボットをグループ分けし、その後はグループ命令または個別命令で移動させる。 目標: 追加壁とグループ分けを活用し、最大K N2操作以内で全ロボットを目的地へ近づけ、できれば全員を目的地に到達させる。衝突や壁により移動しない場合がある。 |
入力: N=30固定、10≤K≤100。各ロボットの初期位置・目的地、既存の横壁v・縦壁hが与えられる。 出力: 追加壁の有無、各ロボットのグループ番号、続けて操作列(a,b,d)を出力する。aはグループ命令gまたは個別命令i。 |
操作回数Tと最終マンハッタン距離dkに対し、T+100Σdkが絶対スコア。小さいほど良い。 |
||
|
2025/07/06 19:00 |
4時間 |
概要: 40×40のスケートリンクで、ロボットが岩にぶつかるまで直進する。N²-M個の岩のないマスを並べた列Pを事前に宣言し、ロボットが4方向にランダム移動後、Piに岩を置く。ロボットが岩を置いた場所にいると潰されゲーム終了、いなければ1円獲得。獲得賞金の期待値を最大化する列Pを求める。 目標: 40×40のスケートリンクで、ロボットの動きを考慮しながら岩を置く順番を決め、ロボットが潰されずに最大の賞金を獲得できるようにする。ロボットは上下左右にランダムに移動し、岩にぶつかるまで直進する。最終的に獲得できる賞金の期待値を最大化することが目標。 |
入力: N=40固定、M個の岩（N²/10≤M≤N²/4）。Si,jは'#'が岩、'.'が空マスを表す。岩のないマスは一様ランダムに配置。 出力: 岩のないマスの順列P=(P0,P1,...,PN²-M-1)を出力。各Pi=(xi,yi)として座標を1行ずつ出力。 |
獲得賞金の期待値をEとし、round(10⁶×E/(N²-M-1))が得点。150テストケースの合計得点で評価。不正出力やTLEの場合は全体が0点。 |
||
|
2025/06/21 15:00 |
4時間 |
概要: 20×20マスのオフィスで、出入り口(0,0)から全てのダンボール箱を運び出す問題。箱は重さと耐久力を持ち、積み重ねて運べるが、移動時に上の箱の重量により下の箱の耐久力が減る。箱の耐久力が0以下になると潰れてWA。最大2×N³回の操作で全箱を運び出し、移動回数を最小化する。 目標: 20×20マスのオフィスで、出入り口(0,0)から開始して全てのダンボール箱を運び出すことが目標。箱は積み重ねて運べるが、移動時に上の箱の重量により下の箱の耐久力が減少するため、耐久力が0以下にならないよう注意が必要。 |
入力: N=20固定。wi,jは各マスの箱の重さ(1≤wi,j≤10³)、di,jは耐久力(10≤di,j≤3×10⁴)。(0,0)は0。 出力: 各操作を1文字で表す。操作1：'1'、操作2：'2'、移動：'U'/'D'/'L'/'R'。操作数をLとして、a0からaL-1を各行に出力。 |
移動回数をT、残り箱数をRとする。R>0の場合：N²-R、R=0の場合：N²+2×N³-T。移動回数が少ないほど高得点。150テストケースの合計得点で評価。 |
|
|
|
2025/06/20 20:00 |
2時間 |
概要: 20×20の盤面で「インクシューター」を使って床マスを塗りつぶす問題。移動でパワーが溜まり、インク発射で溜めたパワー分の距離を塗りつぶせる。発射後はパワーが⌊P/2⌋+1に減少。最大250回の行動で全床マスの塗りつぶしを目指し、塗り残しがあればN²-X点、全塗りできればN²+T-K点を獲得。 目標: 20×20の盤面で全ての床マスを効率的に塗りつぶすことが目標。インクシューターのパワー管理と移動・発射のタイミングを最適化し、最大250回の行動内で全床マスを塗りつぶす。全塗りできない場合は塗りつぶした床マス数を最大化する。 |
入力: N=20、壁マス数M（0≤M≤30）、最大行動回数T=250、初期位置(si,sj)、盤面S。'.'が床マス、'#'が壁マス。全床マスは連結。 出力: 行動回数Kを出力後、各行動を出力。移動：'1 d'、インク発射：'2 d'、パス：'3'。dは方向（U/D/L/R）。 |
塗り残し床マス数をX、行動回数をKとする。X>0の場合：N²-X点、X=0の場合：N²+T-K点。100テストケースの合計得点で評価。 |
||
|
2025/05/30 19:00 |
240時間 |
概要: 高橋画伯のアシスタントとして、CMYカラーモデルで表現される絵の具を調合する問題。N×Nのパレット上で仕切りを使ってウェルを作り、K種類のチューブ絵の具を使って指定されたH種類の色を順番通りに1グラムずつ作成する。絵の具は線形に混ざり、各ウェルには最大でマス数と同じグラム数を保持可能。仕切りの出し入れでウェルの合併・分割が可能。 目標: 指定された1000種類の目標色を順番通りに1グラムずつ正確に作成し、画伯に渡すこと。色の誤差を最小化し、かつチューブから絵の具を出す回数（コスト）を最小化することで高いスコアを目指す。作成順序は固定で変更不可。 |
入力: N=20（パレットサイズ）、K（チューブ数、4≤K≤20）、H=1000（目標色数）、T（最大ターン数、4000≤T≤64000）、D（チューブコスト、10≤D≤10000）、各チューブの色(C,M,Y)、各目標色(C,M,Y)。 出力: 初期仕切り配置：縦仕切りvi,jと横仕切りhi,jを0/1で指定。操作列：最大T行で各操作を指定（1:絵の具追加、2:取り出し、3:廃棄、4:仕切り操作）。操作2をちょうどH回実行必須。 |
絶対スコア = 1 + D×(V-H) + round(104×E)。Eはユークリッド距離による色誤差の和、Vは操作1の回数、Dはチューブコスト。絶対スコアが小さいほど良い。相対評価により最終得点が決まる。 |
||
|
2025/05/18 19:00 |
4時間 |
概要: 高橋君はN=36個の好きな文字列Si（a-fの6文字から構成、長さ6-12）とその好ましさPiを持つ。M=12個の状態を持つ確率的文字列生成モデル（LLM）を設計する。各状態には文字Ciを割り当て、状態間の遷移確率Ai,jを設定する。状態0から開始し、長さL=106の文字列を生成する際、好きな文字列が連続部分文字列として含まれる確率を最大化して期待値を高める最適化問題。 目標: 各状態への文字割り当てC0, C1, ..., CM-1と遷移確率行列Aを設計し、生成される長さL=106の文字列において、各文字列Siが連続部分文字列として1回以上現れる確率Qiを高めることで、好ましさの総和の期待値∑Pi·Qiを最大化する。 |
入力: N M L（N=36, M=12, L=106固定）、続いてN行でSi Piの組。Siはa-fの文字列（長さ6-12）、Piは好ましさ（1≤Pi≤17000）。 出力: M行で各状態の情報を出力。i行目：Ci Ai,0 ... Ai,M-1。Ciはa-fの文字、Ai,jは遷移確率（0-100の整数、行和=100）。 |
各文字列Siが連続部分文字列として1回以上含まれる確率をQiとし、round(∑i=0N-1 Pi · Qi)で計算。150個のテストケースの合計得点。 |
||
|
2025/04/26 15:00 |
4時間 |
概要: スケートリンク上のブロック操作と移動問題。N×N（N=20）のグリッドで、M（M=40）個の目的地を特定の順序で訪問する。プレイヤーは1マス移動、ブロックにぶつかるまで滑る、ブロックを追加・削除といった操作が可能。目的地では必ず停止する必要がある。初期状態では盤面上にブロックはなく、滑るとそのまま盤面の端まで移動してしまうため、ブロックを戦略的に配置して効率的に目的地を訪問することが課題。最小の手数ですべての目的地を訪れることが目標。 目標: N×N（N=20）のグリッド上でM（M=40）個の目的地を指定された順序で訪問し、使用するターン数を最小化する。最大許容ターン数は2NM（1600）。各目的地では正確に停止する必要がある。滑る、移動する、ブロックを追加・削除するといった行動を組み合わせる。 |
入力: N M（グリッドサイズ、目的地数）に続き、M個の座標（初期位置と目的地）。N=20、M=40で固定。 出力: 各ターンについて、アクション（M/S/Aで移動/スライド/ブロック追加を表す）と方向（U/D/L/Rで上/下/左/右を表す）を別の行に出力。 |
m |
||
|
2025/04/19 11:10 |
6時間 |
概要: 「Cooperative Trash Sorting (A)」は、2次元平面上に散らばった燃えるゴミ（X=100個）、燃えないゴミ（Y=0個）、リサイクルゴミ（Z=10～100個）を効率的に収集する問題。高橋くんと青木くんの2人が協力し、高橋くんは燃えるゴミを、青木くんは燃えないゴミを集める必要がある。リサイクルゴミは収集してはいけない。各人は両手でゴミ袋を持ち、線分を形成する。手を動かすと、その移動によって形成される三角形の領域内のゴミが収集される。 目標: 2人（高橋くんと青木くん）が協力して、指定されたタイプのゴミを効率的に収集する戦略を開発する。移動時間を最小化しつつ、すべての燃えるゴミと燃えないゴミを正しく収集し、リサイクルゴミには触れないようにする。 |
入力: X Y Z（各タイプのゴミの数）、各ゴミの座標 (xi, yi)。問題Aでは、X = 100（燃えるゴミ）、Y = 0（燃えないゴミなし）、Z = 10-100（リサイクルゴミ）。 出力: 両プレイヤーの手の初期位置と、複数の操作における手の動きの指示。 |
すべてのゴミが正しく分別され（X'個の燃えるゴミ + Y'個の燃えないゴミが収集され、Z'個のリサイクルゴミが残る）、かつ時間 T ≤ 108 の場合：round(106 × (1 + log₂(108/T)))。それ以外の場合：round(106 × (X'+Y'+Z')/(X+Y+Z))。 |
||
|
2025/03/28 19:00 |
240時間 |
概要: ある王国における道路ネットワーク計画問題。位置が不確かなN個の都市をM個のグループに分け、各グループ内で都市を道路で接続する。都市の正確な位置は不明だが、各都市の位置する可能性のある範囲（矩形）は既知。占い師（オラクル）を利用して都市間の接続最適化の情報を得ることができる。各グループ内で都市が連結になるように道路を建設し、総道路長を最小化することが目標。オラクルクエリを戦略的に利用して不確実性に対処しながら、効率的な道路ネットワークを設計する問題。 目標: N個の都市をサイズ指定されたM個のグループに分割し、各グループ内で都市を道路で接続して総道路長を最小化する。位置が不確かな都市に対し、オラクルクエリを活用して最適な接続を決定する。各グループは連結グラフを形成する必要がある。 |
入力: N個の都市（矩形座標範囲）、M個のグループ（必要な都市数）、およびオラクルクエリのパラメータが与えられる。 出力: 必要に応じたオラクルクエリの後、都市のグループ分けと各グループ内の道路接続を出力する。各グループ内で連結グラフを形成する必要がある。 |
スコアは109 × (最良絶対スコア/あなたの絶対スコア)。絶対スコアは建設されたすべての道路の長さの合計。 |
|
|
|
2025/03/16 19:00 |
4時間 |
概要: 社内の清掃当番表作成問題。N人の社員に清掃当番を割り当てる。各社員Xの次の清掃当番は「Xが奇数回目の清掃をした後はaX番の社員、偶数回目の清掃をした後はbX番の社員」というルールに従う。各社員iについて、目標当番回数Tiと実際の当番回数tiの差の絶対値の合計値を最小化することが目標。L回の清掃を行う当番表を社員0から始めて作成し、各社員iに対する整数値aiとbiを最適に決定する問題。 目標: 各社員iに対して、整数aiとbiを決定し、「社員Xが清掃した後、Xが奇数回なら社員aX、偶数回なら社員bX」というルールに従う当番表を作成する。目標当番回数と実際の当番回数の誤差を最小化する。 |
入力: N L（社員数、清掃回数）と各社員の目標当番回数T0～TN-1。(N=100, L=500,000, 0≤Ti≤10,000) 出力: 各社員iに対する2つの整数aiとbiをN行で出力。0≤ai, bi< N かつ ai ≠ i, bi ≠ i |
スコア = 106 - E。ここでEは誤差の合計 |t0 - T0| + |t1 - T1| + ... + |tN-1 - TN-1| |
||
|
2025/03/02 13:00 |
6時間 |
概要: 「Ore Rolling (A)」では、20×20のグリッド状の洞窟に岩、鉱石、穴が配置されている。各種類の鉱石は対応する穴に落とす必要がある。プレイヤーは洞窟内を移動し、鉱石を運んだり転がしたりして、できるだけ少ない行動数ですべての鉱石を対応する穴に落とすことが目標。岩はどの穴に落としても良いし、洞窟に残しておいても良い。問題Aでは、M=1（鉱石と穴の種類は1つのみ）で、'a'タイプの鉱石が40個、岩が40個配置されており、プレイヤーは穴'A'からスタートする。 目標: すべての鉱石をそれぞれ対応する穴に落とす。できるだけ少ない行動数で目標を達成することが求められる。 |
入力: 20×20のグリッド。小文字(a-z)は鉱石、大文字(A-Z)は穴、@は岩、.は空きマスを表す。問題Aでは、M=1、'a'タイプの鉱石が40個、岩が40個、穴'A'が1つ。 出力: 行動のシーケンス。各行動は「a d」の形式で、aは行動タイプ（1=移動、2=運搬、3=転がし）、dは方向（U,D,L,R）を表す。 |
すべての鉱石が正しい穴に落ちた場合：round(106×(1+log₂(10000/T)))（Tは行動数）。すべての鉱石が正しい穴に落ちなかった場合：round(106×(A/K))（Aは正しい穴に落ちた鉱石の数、Kは鉱石の総数）。 |
|
|
|
2025/02/14 19:00 |
240時間 |
概要: シミュレーションゲーム形式の鉄道会社経営問題。50×50のグリッド上で、人々の通勤を助けるために線路や駅を建設する。各ターンは「建設フェーズ」と「料金徴収フェーズ」からなり、建設フェーズでは線路と駅を建設でき、料金徴収フェーズでは通勤客から運賃を得る。人々は自宅と職場の間を、最も短いルートで移動しようとする。最適な鉄道ネットワークを構築し、800ターン後の資金を最大化することが目標。 目標: 50×50のグリッド上に戦略的に線路と駅を配置して効率的な鉄道ネットワークを構築し、人々の自宅と職場を接続する。通勤客から運賃を徴収して、最終的な資金を最大化する。各ターンでの行動（線路敷設、駅建設、待機）を800ターン分決定する。 |
入力: 最初の行: N M K T（グリッドサイズ、人数、初期資金、ターン数）。次のM行: 各人の自宅と職場の座標。 出力: T行、各行に1つのアクション: 線路敷設(p i j)、駅建設(0 i j)、または待機(-1)。 |
最終スコアは各テストケースの最良の解に対する相対値: round(109 × (あなたのスコア/最良のスコア))。予備テストは50ケース、システムテストは2000ケース。 |
|
|
|
2025/02/02 19:00 |
4時間 |
概要: 日本の節分の「鬼は外、福は内」をテーマにしたボードゲーム問題。N×N（N=20）のグリッド上に「鬼(Oni)」と「福(Fuku)」のコマが配置されている。行または列をひとマスずつシフトさせる操作を繰り返し、福をボード上に残したまま、すべての鬼をボードから追い出すことが目標。各操作では、行または列を選び、左/右または上/下にシフトさせる。シフトによってボードの端から外れるコマは取り除かれる。必要な操作回数をできるだけ少なくして、全ての鬼を追い出しつつ、福を残すことが課題。 目標: N×N（N=20）のグリッド上から、行または列をひとマスシフトさせる操作を使って、すべての鬼(Oni)のコマを取り除きつつ、すべての福(Fuku)のコマをボード上に残す。操作回数はできるだけ少なくすることが望ましい。 |
入力: N（=20）に続き、N行の初期ボード状態が与えられる。'x'=鬼、'o'=福、'.'=空きマスを表す。 出力: 操作をdirection-positionペアとして列挙: (L,i), (R,i), (U,j), (D,j)。最大で4N²回までの操作が可能。 |
すべての鬼を取り除き、すべての福が残る場合: 8N²-T。それ以外: 4N²-N(X+Y)。Tは操作回数、Xは残った鬼の数、Yは取り除かれた福の数。 |
||
|
2025/01/19 15:00 |
4時間 |
概要: クリスマスパーティーの会場装飾のために、グラフから根付き木を切り出す問題。各頂点は美しさの値を持ち、より高い位置（根からの距離が大きい位置）に美しい頂点があるほど会場は魅力的に見える。ただし、天井に当たらないよう木の高さ（根から最も遠い頂点までの距離）はH以下に制限される。与えられたグラフからすべての頂点を1つずつ異なる木に属するように根付き木を複数構築し、全ての木の魅力度の合計を最大化することが目標。 目標: 与えられたグラフから根付き木の集合を構築し、全ての頂点がちょうど1つの木に属し、全ての木の高さがH以下で、魅力度の合計（頂点の高さによる美しさの重み付け合計）を最大化する。異なる頂点を根とする複数の木を構築できる。 |
入力: 頂点数N、辺数M、高さ制限H、美しさの値A、辺の接続ui-vi、および頂点の座標xv, yvが与えられる。 出力: 各頂点vについて、その親頂点pvまたは根の場合は-1をスペース区切りで出力する: p0 p1 ... pN-1 |
スコア = 1 + 全ての木の魅力度の合計。木Tの魅力度 = T内のすべての頂点vについての和: (heightv + 1) × beautyv |
||
|
2024/11/29 19:00 |
240時間 |
概要: 不確実な寸法を持つN個の長方形が与えられ、これらを2次元空間に配置するパッキング問題。長方形の実際の寸法は正規分布に従う誤差を含む観測値として提供され、配置後にしか実際の寸法がわからない。長方形をT回の操作で配置し、包含箱（すべての配置された長方形を含む最小の長方形）の幅と高さの和を最小化する。ターンごとに長方形の観測された寸法が与えられ、利用可能な長方形から配置する長方形を選択し、回転させるかどうかを決定し、配置位置を指定する。 目標: 不確実な寸法を持つN個の長方形を2次元平面上に配置して、包含箱の幅と高さの和を最小化する。配置位置は推定と複数ターンにわたるフィードバックに基づいて決定する。未使用の長方形も最終スコアに影響するため、できるだけ多くの長方形を効率的に配置することが重要。 |
入力: 長方形の数N(30-100)、操作回数T(N/2-4N)、誤差の標準偏差σ(1000-10000)、観測された寸法w'i, h'iが与えられる。 出力: 各ターンで、配置するn個の長方形を指定し、各長方形について、インデックス、回転状態、配置方向、参照位置を出力する。 |
スコア = 包含箱の幅 + 高さ + 未使用の長方形の寸法の和。スコアが小さいほど良い。参加者間の相対評価で順位が決定される。 |
||
|
2024/11/10 15:00 |
4時間 |
概要: 2次元平面上に分布する「マサバ」と「マイワシ」を対象とした巾着網漁の問題。プレイヤーは最大50頂点の単純多角形（自己交差しない）の網を設計して、マサバをできるだけ多く、マイワシをできるだけ少なく捕獲することが目標。魚は座標平面上に点として配置され、多角形の内部に含まれる魚が捕獲される。頂点座標は整数で指定し、辺は2頂点間の線分で表される。この問題では、マサバとマイワシの分布の差を活かした最適な多角形の設計が求められる。 目標: 2次元平面上にN匹ずつ存在するマサバとマイワシについて、マサバをできるだけ多く、マイワシをできるだけ少なく含む単純多角形（自己交差しない、最大50頂点）を構築する。目標は多角形内のマサバの数からマイワシの数を引いた値に1を足した値（マサバ-マイワシ+1）を最大化すること。 |
入力: N（各魚種の数）と、N匹のマサバとN匹のマイワシの座標(x,y)が与えられる。すべての座標は0≤x,y≤105の整数。 出力: 多角形の頂点数(m)と、それに続くm個の頂点座標(x,y)を出力する。頂点は反時計回りに列挙し、有効な単純多角形を形成する必要がある。 |
多角形内にa匹のマサバとb匹のマイワシが含まれる場合、スコアはmax(0, a-b+1)。150テストケースの合計がトータルスコアとなる。 |
||
|
2024/10/04 19:00 |
240時間 |
概要: N×N格子上で、たこ焼きの運搬を行うロボットアームの設計と操作問題。ロボットアームは木構造で、関節と指先から構成される。指先でたこ焼きを掴み/放し、関節で回転し、全体として移動することができる。アームを使ってM個のたこ焼きを初期位置から目標位置に運ぶ。アームの設計は頂点数V以下の木構造として自由に決められるが、操作ターン数はできるだけ少なく済ませることが望ましい。 目標: 頂点数V以下の木構造のロボットアームを設計し、M個のたこ焼きを初期位置から目標位置に運ぶために必要な操作手順を最小ターン数で実行する。アームは全体移動、関節回転、掴む/放すの操作が可能。 |
入力: 格子サイズN×N、たこ焼きの数M、ロボットアームの最大頂点数V、2つのN×Nバイナリ行列（たこ焼きの初期位置と目標位置を表す）が与えられる。 出力: ロボットアームの構造（頂点数、親頂点ID、辺の長さ）、初期根の位置、および操作コマンド列（移動、回転、掴む/放す）を出力する。 |
全たこ焼きを運べた場合はターン数がスコア。運べなかった場合は105+1000×(M-M')。スコアは小さいほど良い。相対スコアは最小スコア/自分のスコア×109の切り捨て。 |
||
|
2024/09/15 19:00 |
4時間 |
概要: 炭酸飲料工場で甘さと炭酸の強さを持つ炭酸飲料を効率的に作成する問題。初期状態は(0,0)のみ持っており、既存の炭酸飲料から新しい炭酸飲料を作る操作を繰り返し、指定されたN種類の炭酸飲料を全て作成する。各操作は(x,y)から(x',y')を作るときにコスト(x'-x)+(y'-y)がかかる。 目標: N種類の炭酸飲料(Ai,Bi)をすべて作るような操作列のうち、コストの総和がなるべく小さいものを見つける。5N回以下の操作で、最終的にすべての指定された炭酸飲料が作成可能な集合Sに含まれるようにする。 |
入力: N=1000、各行にAi Biが与えられる。AiとBiはそれぞれ相異なり、少なくとも一つは0を含む。 出力: 操作回数M、各操作についてxm ym x'm y'mを出力。操作列により指定された炭酸飲料がすべて作成される必要がある。 |
得点 = round(106 × NL/(1+C))。ここでCはコストの総和、L = max{A1,B1,...,AN,BN}。 |
||
|
2024/08/23 19:00 |
240時間 |
概要: N個の都市とM本の道路からなる平面グラフ上での経路探索問題。各都市には赤または青の信号があり、配列AとBによって制御される。配列Aは初期設定できるが、配列Bは操作によって部分的に書き換える必要がある。信号が青の都市にのみ移動可能で、指定された順序で都市を巡ることが目的。都市は座標をもち、トラベラーXは初期位置(都市0)から各目的地に順に訪問する。目標は信号操作の回数を最小化すること。 目標: 旅行者が都市0から始め、T個の都市(t0, t1, ..., tT-1)を指定された順に訪問できるよう、信号制御用の配列Aを初期設定し、移動と信号操作（配列Bの更新）を最適に組み合わせて、信号操作の回数を最小化する。 |
入力: 都市数N(=600)、道路数M(N-1≤M≤3N-6)、訪問する都市数T(=600)、配列AとBの長さLA(N≤LA≤2N)とLB(4≤LB≤24)、道路情報(ui,vi)、訪問順序t0～tT-1、各都市の座標(xi,yi)。 出力: 1行目に配列Aの初期値（N以上LA以下の整数）をスペース区切りで出力。その後、信号操作（s l PA PB）と移動（m v）を交互に行い、旅行計画をすべて達成する。 |
旅行が成功し信号操作の回数がCの場合、絶対スコアCが与えられる。各テストケースで全参加者中の最小絶対スコアを自身の絶対スコアで割った値に109を掛けて四捨五入した値が相対スコアとなり、その和が提出の得点となる。 |
||
|
2024/07/21 15:00 |
4時間 |
概要: N×Nグリッドの畑に穀物の種を植える育種改良問題。各種は、M個の評価項目からなる非負整数ベクトルxで表され、種の価値はその合計V=Σx。各ターンでは、畑の全マスに種を植え、隣接する2つの種から各評価項目の値をランダム継承した新しい種が生成される。この種植え・収穫をT回繰り返し、手持ちの種の価値最大値をできるだけ大きくする。 目標: N×Nグリッドの畑に穀物の種を各ターンで配置し、隣接するマスの種から新しい種が生成される仕組みを利用して、T(=10)回の操作後に手持ちの種の価値(評価項目の合計値)の最大値を最大化する。 |
入力: グリッドの大きさN(=6)、評価項目数M(=15)、操作回数T(=10)、2N(N-1)個の種の評価項目ベクトルxk=(xk,0,...,xk,M-1)が与えられる。xk,lは0～100の整数。 出力: 各ターンで、N×Nグリッドの各マスに植える種の番号Ai,jをN×N行列として出力する。出力後は改行とflushを行う。次に新たに生成された2N(N-1)個の種の評価項目ベクトルが入力される。 |
最終的な手持ちの種の価値最大値W=max(V0,...,V2N(N-1)-1)を初期種の各評価項目の最大値の合計Σmax(xk,l)で割った値にround(106×)を適用した値。300テストケースの合計が得点となる。 |
||
|
2024/06/16 15:00 |
4時間 |
概要: N×Nマスの土地を整地するために、ダンプカーを操作して効率的に土砂を移動させる問題。各マスには高さが設定されており、初期状態では高さの合計が0である。ダンプカーは土砂を掘る（+d）、土砂を降ろす（-d）、隣接マスに移動（U/D/L/R）という操作が可能で、それぞれにコストが発生する。最終的に全てのマスの高さを0にすることが目標。 目標: 20×20マスの土地について、各マスの高さを0にするため、ダンプカーを使って土砂を効率的に移動させる。土砂を掘る・降ろすとdのコストが発生し、移動時はダンプカーの積載量dに応じて100+dのコストが発生する。最終的に全マスの高さが0となるよう、コストを最小化する操作列を求める。 |
入力: N(=20)と、各マス(i,j)の初期高さhi,j（-100≤hi,j≤100の整数値、総和は0）が与えられる。 出力: 各ターンの操作を表す文字列を出力する。土砂を掘る:「+d」、土砂を降ろす:「-d」、移動:「U/D/L/R」。操作数は最大100000ターン。 |
操作列の合計コストをcost、全マスの初期高さの絶対値の和をbase、最終的に高さが0でないマスがある場合のペナルティをdiff=100|hi,j'|+10000の和として、round(109×base/(cost+diff))の得点が得られる。150テストケースの合計が最終スコア。 |
||
|
2024/06/12 20:40 |
2時間 |
概要: コンサートの指揮者として、一列に並んだN人の演奏者の音量を調整する問題。演奏はT秒間続き、各時間ステップtで各演奏者iには理想的な音量V_{t,i}がある。指揮者は各時間ステップで1回、L～R番目の演奏者全員の音量を同時にdVだけ変更するコマンドを出すことができる。最初、すべての演奏者の音量は0であり、コマンドによって変更される。目標は、実際の音量と理想的な音量の差の絶対値の合計を最小化すること。 目標: 各時間ステップtで、L～R番目の演奏者に対して音量調整コマンドdVを発行し、全ての演奏者と全ての時間ステップにわたる実際の音量と理想的な音量との差の絶対値の合計を最小化する。 |
入力: N T に続き、T行のN個の整数。各整数は時間tでの演奏者iの理想的な音量V_{t,i}を表す。 出力: T行、各行に3つの整数Lt Rt dVt（演奏者の範囲と音量変更量）を各時間ステップごとに出力。 |
スコア = max(S₀ - S' + 1, 0)。S₀はコマンドなしの場合の総偏差、S'はあなたの解の偏差。 |
|
|
|
2024/05/17 19:00 |
240時間 |
概要: N×Nマスのコンテナターミナルで、N2個の番号付きコンテナを搬入口から適切な搬出口まで運ぶ問題。N台のクレーンを操作して、各マスに高々1つのコンテナを配置しながら、指定された順番に近い順でコンテナを搬出する。大クレーン1台はコンテナを高く持ち上げられるため、コンテナを掴んだ状態でも他のコンテナの上を通過できるが、N-1台の小クレーンはそれができない。 目標: N(=5)×Nマスのコンテナターミナルで、N台のクレーンを操作して、搬入口から入ってくるコンテナを、正しい搬出口から正しい順番で搬出する。短いターン数で処理し、転倒数（順番の逆転）や間違った搬出口からの搬出、未搬出コンテナを最小化する。 |
入力: マップサイズN(=5)と、各搬入口(i,0)からj番目に搬入されるコンテナの番号Ai,j（0〜N2-1の整数で全て異なる）が与えられる。 出力: 各クレーンの各ターンでの操作（P:掴む、Q:離す、U/D/L/R:移動、.:何もしない、B:爆破）を表す文字列を出力する。操作数は最大10000ターン。 |
絶対スコア = ターン数M0 + 102×転倒数M1 + 104×誤搬出数M2 + 106×未搬出数M3。各テストケースの全参加者中の最小絶対スコアを自身の絶対スコアで割った値（×109で丸め）の和が最終スコア。スコアは小さいほど良い。 |
||
|
2024/04/20 11:10 |
6時間 |
概要: 「Windy Drone Control (A)」では、2次元平面上のドローンを操作して10個の目的地を訪問する問題。ドローンは物理法則に従って移動し、ランダムな風の影響を受ける。各ターンではドローンを加速させるか、特定方向の壁までの距離を測定することができる。問題Aでは壁はなく、外側の境界のみ存在する。風の影響パラメータεは1～100からランダムに選ばれ、測定誤差パラメータδは0.01～0.20からランダムに選ばれる。 目標: 2次元平面上のドローンを操作して、10個の目的地を任意の順序で訪問する。風の影響を受けながら効率的に移動し、壁との衝突を避けつつスコアを最大化する。 |
入力: 目的地数N(=10)、壁数M(=0)、風の影響パラメータε、測定誤差パラメータδ、開始位置(sx, sy)、目的地座標(px, py)×N、壁の端点(lx, ly, rx, ry)×M 出力: 各ターンで「A ax ay」（加速）または「S bx by」（センサー測定）のいずれかを出力。加速の場合はaxとayの範囲は[-10, 10]、センサー測定の場合はbxとbyは単位ベクトル。 |
スコアは0から開始し、ターンごとに-2点、壁との衝突で-100点、初めて目的地に到達するごとに+1000点。5000ターン以内の最高スコアが最終スコアとなる。 |
||
|
2024/04/07 19:00 |
4時間 |
概要: N×Nマスの盤面に整数ai,jが設定されており、M個の3×3マスのスタンプ（各マスにはsm,i,jの整数が書かれている）を使って盤面の整数を増加させる問題。スタンプをK回まで盤面に押すことができ、押すとスタンプの各マスの値が対応する盤面マスの値に加算される。最終的な盤面の各マスの値を998244353で割った余りの総和を最大化する。 目標: 9×9マスの盤面上に、20種類の3×3マススタンプを最大81回押して、最終的な盤面の整数を998244353で割った余りの総和を最大化する。スタンプは盤面からはみ出してはならず、回転させることはできないが、同じスタンプを複数回使用したり同じ場所に押したりしてもよい。 |
入力: N=9（盤面サイズ）、M=20（スタンプ数）、K=81（最大スタンプ押下回数）と、盤面の初期値ai,j、各スタンプのマス値sm,i,jが与えられる。すべての値は0≤ai,j,sm,i,j≤998244352を満たす。 出力: スタンプを押した回数L(0≤L≤K)、各操作で選択したスタンプmlと押した盤面の左上座標(pl,ql)を出力する。各操作は0≤ml≤M-1、0≤pl,ql≤N-3を満たす必要がある。 |
最終的な盤面のマス(i,j)の値bi,jについて、各マスのbi,j mod 998244353の総和が得点となる。テストケースは150個あり、各ケースの得点の合計が最終スコアとなる。 |
||
|
2024/03/22 19:00 |
240時間 |
概要: 縦横Wのイベントホールを、パーティションを用いて複数の長方形区画に分割し、D日間にわたり各日N個の予約に長方形区画を貸し出す問題。各予約には希望面積ad,kがあり、実際の区画面積bd,kがad,kを下回ると100×(ad,k-bd,k)のコストが発生する。また、前日からパーティション配置を変更する際には、設置・撤去したパーティションの長さLd分のコストが発生する（ただし初日はL0=0）。 目標: 縦横1000のイベントホールで、D(5～50)日間にわたり各日N(5～50)個の予約に対して、希望面積を満たせなかった場合のペナルティとパーティション変更コストの合計を最小化するよう長方形区画を割り当てる。区画は軸平行で頂点は格子点上にあり、同日の異なる予約の区画は重複してはならない。 |
入力: 初期入力としてグリッドサイズW=1000、日数D(5≤D≤50)、各日の予約数N(5≤N≤50)、各日各予約の希望面積ad,kが与えられる。各日の希望面積は昇順であり、合計はW2以下。 出力: D日×N個の予約それぞれについて、割り当てる長方形区画の左上座標(id,k,jd,k)と右下座標(id,k',jd,k')を出力する。各長方形は0≤i |
D日間のコスト合計をCとすると、C+1が絶対スコア（小さいほど良い）。各テストケースの全参加者中最小絶対スコアを自身の絶対スコアで割った値（×109で丸め）の和が最終スコア。システムテストは2000ケース。 |
||
|
2024/03/03 13:00 |
6時間 |
概要: N×Nマスのグリッド上で、各マスには1からN2の数字がそれぞれ1つずつ書かれている。高橋君と青木君はグリッド上を移動しながら、現在位置の数字を交換することができる。隣接するマス間の壁の有無も考慮する必要がある。最終的に隣接するマス間の数字の差を最小化することが目標。高橋君と青木君の初期位置と、その後の行動（数字交換と移動）を決定する問題。 目標: N×Nマス（10≤N≤100）のグリッド上で、高橋君と青木君が移動と数字交換を行う。各マスには1〜N2の数字が書かれている。二人の初期位置と、最大4N2回の行動（交換・高橋移動・青木移動）を決定し、隣接するマス間の数字の差の二乗和を最小化する。 |
入力: t N、マス間の縦壁vi,j、横壁hi,j、各マスの数字ai,j（tは入力生成方法を表す整数で0≤t≤19） 出力: 高橋君と青木君の初期位置(pi,pj)(qi,qj)、その後の行動k回分を「数字交換の有無s、高橋君の移動方向d、青木君の移動方向e」の形式で出力 |
初期状態での隣接マスの数字の差の二乗和をD'、最終状態での二乗和をDとしたとき、max(1, round(106×log₂(D'/D)))点が得られる。t値ごとに10個ずつ、計200個のテストケース。 |
||
|
2024/02/09 19:00 |
240時間 |
概要: N×Nマスの島の地下にM個のポリオミノ型の油田が存在している。各マスの石油埋蔵量v(i,j)を「そのマスに含まれる油田の数」として定義する。操作として、(1)1マスを掘って埋蔵量を知る（コスト1）、(2)複数マスの埋蔵量の総和を占う（kマス選ぶとコストは1/√k、ただし結果に誤差が生じる）、(3)v(i,j)>0のマスを全て推測する（正解なら終了、不正解ならコスト1）の3種から選び、最大2N²回実行可能。 目標: N×Nマスの島で、M個のポリオミノ型油田がどのマスに存在するかを最小のコストで特定する。各操作のコスト(マスを1つ掘る:1、k個のマスの埋蔵量を占う:1/√k、間違った推測:1)を考慮して、v(i,j)>0となるマスをすべて特定する。 |
入力: 島の大きさN(10≤N≤20)、油田の個数M(2≤M≤20)、エラーパラメータε(0.01≤ε≤0.2)、各油田の形状がポリオミノとして与えられる。 出力: 操作の種類に応じて「q 1 i j」(1マス掘る)、「q d i1 j1 ... id jd」(d個のマスを占う)、「a d i1 j1 ... id jd」(v(i,j)>0のマスを推測)の形式で出力する。 |
v(i,j)>0のマスを全て特定できた場合、コストの総和をCとして、round(106×max(C,1/N))が絶対スコア。特定できなかった場合は109。各テストケースで全参加者中の最小絶対スコアを自身のスコアで割った値が相対スコアとなる。 |
||
|
2024/01/13 15:00 |
4時間 |
概要: N×Nマスのグリッド上にキーボード配列がある。各マスには英大文字が書かれており、指が初期位置から移動しながら文字を出力する。M個の文字列(縁起の良い単語)が与えられ、それら全てを部分文字列として含む文字列(縁起の良い文字列)を作りたい。指は1回の操作で任意のマスに移動して文字を出力でき、移動コストは|i-i'|+|j-j'|+1。総コストが最小となる操作列を見つける問題。 目標: N×Nグリッド上のキーボード配列において、指を移動して英大文字を出力する。M個の長さ5の文字列が与えられており、それら全てを部分文字列として含む文字列を作成する。移動コスト|i-i'|+|j-j'|+1（マンハッタン距離+1）が最小となるような操作列を5000回以内で求める。 |
入力: N M、初期位置(si,sj)、N行のキーボード配列Ai,j（各マスに書かれた英大文字）、M個の文字列t1〜tM（N=15、M=200に固定、各tkは長さ5） 出力: L回の操作それぞれについて、指定するマスの座標(il,jl)を出力する。 |
縁起の良い単語のうちSに部分文字列として含まれるものの個数をK、操作のコスト総和をTとしたとき、K |
||
|
2023/12/22 12:00 |
105時間 |
概要: 会社経営のシミュレーションゲーム。複数のプロジェクトに対して毎ターン手札から方針カードを選んで実行する。方針カードには「通常労働」「全力労働」「キャンセル」「業務転換」「増資」の5種類があり、プロジェクトの残務量を減らしたり、取りやめたり、将来の数値を2倍にしたりできる。プロジェクトが完了すると価値分の所持金が増え、カード購入時にはコスト分の所持金が減る。全ターン終了時の所持金を最大化する問題。 目標: 方針カードを戦略的に選択し、プロジェクトを効率的に完了させて、T(=1000)ターン後の所持金を最大化する。手札からカードを選んで使用し、プロジェクトの残務量を減らすか取りやめることで管理し、完了したプロジェクトの価値を得る。新たな方針カードを適切なコストで購入して手札を補充する。 |
入力: 最初に4整数N(手札枚数),M(プロジェクト数),K(カード提示枚数),T(ターン数)と、N枚の方針カード情報ti,wi、M個のプロジェクト情報hi,viが与えられる。 出力: 各ターンで、使用するカードのインデックスcとプロジェクトのインデックスmを出力し、続いて新しく選ぶカードのインデックスrを出力する。出力後は必ず改行とflushを行う。 |
各テストケースでの所持金を絶対スコアとし、相対評価スコア（109×自分のスコア÷最大スコア）の合計が最終スコアとなる。システムテストは3000ケース。 |
||
|
2023/12/01 19:00 |
216時間 |
概要: N×Nマスの盤面上で掃除ロボットが動く経路を最適化する問題。各マスには汚れやすさdi,jが設定されており、ロボットが移動すると移動先のマスの汚れが0になり、それ以外のマスの汚れはdi,jずつ増加する。(0,0)からスタートして全マスを訪問し(0,0)に戻る経路を繰り返したとき、定常状態での平均汚れ量を最小化する。 目標: N×Nマス（20≤N≤40）の盤面上で、マス間に壁がある場合もある。各マスには汚れやすさdi,jが設定されている。(0,0)から開始して全マスを訪問し(0,0)に戻る105以下の長さの閉路を作成し、この経路を無限に繰り返したときの定常状態での平均汚れ量を最小化する。 |
入力: N、各マス間の水平方向の壁hi,j、垂直方向の壁vi,j、各マスの汚れやすさdi,j（1≤di,j≤103） 出力: 掃除ルートを表す文字列。上下左右の移動をそれぞれU、D、L、Rで表す。 |
出力した掃除ルートにおける平均汚れをS̄としたとき、round(S̄)の絶対スコアが得られる。相対評価方式で、各テストケースごとに109×(最小絶対スコア/自分の絶対スコア)の相対スコアの和が最終得点。 |
||
|
2023/11/05 15:00 |
4時間 |
概要: n個のダンボール箱（番号1～n）がm個の山に積まれている。各山には同数の箱が積まれており、番号順に倉庫から運び出したい。箱を運び出すには、その上に積まれた箱を別の山に移動させる必要がある。一度に複数の箱を持ち上げて動かせるが、移動する箱の数+1の体力を消費する。全ての箱を番号順に運び出す際の体力消費を最小化する問題。 目標: n=200個の箱がm=10個の山に積まれている状態から、番号の小さい順に箱を運び出す。箱を運び出すには、その上の箱を別の山に移動させる必要がある。一度に複数箱を移動できるが、移動する箱の数k個につきk+1の体力を消費する。全ての箱を5000回以内の操作で運び出し、体力消費を最小化する。 |
入力: n m（箱の総数と山の数、n=200、m=10に固定）、m行のデータで各山に積まれた箱の番号（下から順に各行n/m個） 出力: 操作列を出力。(v,i)形式で、vは操作対象の箱番号、i=0なら箱vを運び出し、i>0なら箱vとその上の箱を山iに移動する操作を表す。 |
全ての箱を運び出せた場合、合計の体力消費量をVとして、max(1, 10000-V)の得点が得られる。スコアが大きいほど良い。全ての箱を運び出せなかった場合や不正な操作はWAとなる。 |
||
|
2023/10/14 12:00 |
199時間 |
概要: N個のアイテムがあり、各アイテムの重さは未知である。2つのアイテム集合の重さの総和を比較できる天秤を用いて、天秤の左右にアイテムを好きなだけ乗せ、重さの総和の比較結果を得る操作をQ回繰り返す。この情報を用いて、N個のアイテムをできるだけ重さの総和が等しくなるようにD個の集合に分割する問題。 目標: N個のアイテム（30≤N≤100）を、天秤を使ったQ回（2N≤Q≤32N）の重さ比較によって得られる情報のみを用いて、重さの総和ができるだけ均等になるようD個（2≤D≤N/4）の集合に分割する。分割後の各集合の重さの分散を最小化することが目標。 |
入力: 最初にN D Qが与えられる。その後、Q回のクエリで、天秤の左右に置くアイテム集合L, Rを出力し、「<」「>」「=」のいずれかの比較結果を受け取る。 出力: Q回のクエリではnL nR l0 ... lnL-1 r0 ... rnR-1の形式で出力。最後に各アイテムがどの集合に属するかをd0 ... dN-1の形式で出力。 |
各集合の重さの総和の分散をVとしたとき、1+round(100×√V)の絶対スコアが得られる。絶対スコアが小さいほど良く、テストケースごとの順位に応じた順位スコアの合計が最終得点となる。 |
||
|
2023/09/24 15:00 |
4時間 |
概要: n×nマスのグリッド上に表現された高橋市の地図が与えられる。市はm個の区からなり、c（1≤c≤m）番の色で塗られたマスはc番の区に対応する。2つのマスは辺を共有する場合に「隣接している」と定義され、同じ色で塗られたマス集合は連結である。市の外周はグリッドの外部であり、0番の色で塗られているとみなされる。各区の形状や大きさはさほど重要ではなく、隣接関係を正しく表現できればよい。条件を全て満たす地図のうち、色0のマスの数をできるだけ多くするような小さな地図を作成する問題。 目標: n×nマスのグリッド上に表現された高橋市の地図をもとに、以下の条件を満たす新しい地図を作成する。(1)全ての色c(0≤c≤m)について、色cのマスは連結である。ただし色0のマスは外部を経由して連結でも良い。(2)全ての色c,d(0≤c |
入力: n m（n = 50, m = 100に固定）、各マス(i,j)の色ci,j（1≤ci,j≤m）。 出力: 作成した地図の各マス(i,j)の色di,j（0≤di,j≤m）を出力する。 |
作成した地図に含まれる色0のマスの総数をEとしたとき、E+1の得点が得られる。得点が高いほど良い。 |
||
|
2023/09/03 10:00 |
178時間 |
概要: H×Wの長方形の農地があり、1×1の区画に分かれていて、一部の区画間には水路がある。土地の外周は柵で囲まれており、一箇所だけ出入口がある。K種類の作物を育てるための計画を立てる問題。作物kは遅くともSkヶ月目までに植え、Dkヶ月目に収穫する。作物を植えたり収穫したりする際は、出入口からその区画まで栽培中の区画や水路を通らずに到達できなければならない。各作物は一つの区画でのみ栽培でき、一つの区画では同時に一つの作物しか育てられない。なるべく多くの区画を有効利用することを目指す。 目標: H×Wの農地において、K種類の作物から選んだものをどの区画でいつ植えるかを決定する。作物kはSkヶ月目までに植え、Dkヶ月目に収穫する必要がある。作物の植え付けや収穫時には出入口からその区画まで水路や他の栽培中の区画を通らず到達できる必要がある。作物k毎のスコアはDk-Sk+1で、すべての作物のスコア合計を最大化する。 |
入力: T H W i0（T=100, H=W=20）、水路の情報（0/1の文字列）、作物数K、各作物の植え付け期限Skと収穫時期Dk（1≤Sk 出力: 植える作物数M、各作物の情報（作物番号k、植える区画(i,j)、植える月s）を出力。植える順序は任意。作物kを区画(i,j)で月sに植えるとき、条件を満たす必要がある。 |
ACとなったテストケースでは、植えた作物kごとにXk=Dk-Sk+1としたとき、得点は106×∑Xk/(HWT)。ACにならなかったテストケースの得点は0。システムテストでは全テストケースの得点の合計が最終得点となる。 |
||
|
2023/08/27 10:15 |
3時間30分 |
概要: 「Transit Warehouse」では、9×9のグリッド倉庫で物流最適化に取り組みます。倉庫には入口（0,4）が1つあり、N個の障害物（0≤N≤9）が配置されています。(D²-1-N)個のコンテナが一つずつ到着し、各コンテナには0からD²-2-Nまでの一意の番号が付いています。この番号は、コンテナを搬出する際の望ましい順序を示しています。コンテナの到着順序は、各コンテナが到着するまで不明です。プレイヤーは、各コンテナが到着したときにそれをどこに配置するかを決定する必要があります。全てのコンテナが配置された後、コンテナを搬出する順序を決定します。コンテナは空いている、かつアクセス可能（入口から隣接する空きマスを通じて到達可能）なマスにのみ配置できます。各マスには最大1つのコンテナしか置けません。搬出時も、コンテナは入口からアクセス可能である必要があります。 目標: コンテナの到着順序が事前にわからない状況で、各コンテナの最適な配置場所を決定し、その後の搬出順序を決めることで、理想的な搬出順序（0,1,2,...）からの逸脱（転倒数）を最小化する。 |
入力: 1行目：D N（Dは常に9、Nは障害物の数で0≤N≤9）。続くN行：障害物の座標（rik, rjk）。その後、各コンテナ到着ごとに：そのコンテナの番号tdが1行で与えられる。プレイヤーは次のコンテナの情報を得る前に、現在のコンテナの配置場所を出力する必要がある。 出力: 各コンテナについて：そのコンテナを配置する座標（pid, pjd）を出力。全コンテナが配置された後：搬出順序でのコンテナの座標を出力。 |
biをi番目に搬出されたコンテナの番号とし、B = b0...b_(D²-2-N)の転倒数とする。スコア = round(10⁹ × ((D²-N)(D²-1-N)/2-B)/((D²-N)(D²-1-N)/2))。転倒数が少ないほど（理想的な順序に近いほど）高スコアとなる。 |
||
|
2023/08/11 12:00 |
223時間 |
概要: L×Lのトーラス型グリッドと、グリッド上に配置されたN個の出口セルがある。N個のワームホールと出口セルは一対一対応しており、その対応関係を推定する。手順は3段階：「配置」ではグリッドの各セルに0～1000の整数値を設定。「計測」では最大10000回、任意のワームホールを選んで出口セルから指定した距離を移動し、そのセルの値にノイズを加えた値を計測する。「回答」では推定した対応関係を出力。配置時のコスト（隣接セル間の値の差の2乗和）と計測時のコスト（計測回数×距離）を小さくしつつ、正確に対応関係を推定する問題。 目標: L×Lのトーラス型グリッド上に配置されたN個の出口セルと、それぞれに対応するN個のワームホールの対応関係を推定する。グリッドの各セルに値を設定し、ワームホールを選んで対応する出口セルから移動後のセルの値を計測することで対応関係を判別する。配置時コストと計測時コストを最小化しながら、できるだけ正確に対応関係を推定する。 |
入力: L N S(Lはグリッドサイズ10～50、Nは出口セル数60～100、Sは計測値の標準偏差)と、N個の出口セル座標(Yi,Xi)。Sはi2(1≤i≤30)の形。座標は全て相異なり、辞書順。 出力: インタラクティブ形式。まず配置として各セルの値Pi,j(0≤Pi,j≤1000)を出力。続いて計測としてワームホール番号iと移動距離y,xを出力し、計測値を受け取る。最後に「-1 -1 -1」を出力した後、推定した対応関係E0～EN-1を出力する。 |
N個の回答のうち誤りだったものの数をWとすると、得点 = ⌈1014×0.8W/(配置時コスト+計測時コスト+105)⌉。各テストケースにおいて、相対評価スコア = round(109×自身の得点/全参加者中の最高得点)。 |
||
|
2023/08/06 22:00 |
2時間 |
概要: 「AtCoder Contest Scheduling (Online Version)」では、AtCoderがコンテストタイプを4種類から26種類（AAC～AZC、タイプ1～26として表示）に増やす計画を立てており、毎日1つのコンテストを開催する。ユーザーの満足度を最大化するために、各日にどのタイプのコンテストを開催するかを決定する問題。ユーザー満足度は外部要因により日々変動し、決定は逐次的（一日ずつ）に行う必要がある。 目標: ユーザー満足度を最大化するために、毎日のコンテストタイプを決定する。日々変動する満足度情報に基づき、逐次的に各日のコンテストタイプを選択する。 |
入力: 日数D（365固定）と26個の値ci（0-100）。各日には、26個の値sd,i（各コンテストタイプによる満足度の増加）が与えられる。 出力: 現在の日のコンテストタイプを表す単一の整数（1-26）。各日の決定後に出力して、出力をフラッシュする必要がある。 |
最終スコア：max(S-B+1, 0)。ここで、Sはあなたのスケジュールによる満足度、Bは単純な輪番スケジュール（ベースライン）による満足度。参加者間で相対的なスコアリングが行われる。システムテストでは1000のテストケースが使用され、暫定テストでは50のテストケースが使用される。 |
|
|
|
2023/06/25 15:00 |
4時間 |
概要: N(N+1)/2個のボールがN段のピラミッド型に並んでいる。各ボールには0～N(N+1)/2-1の数字が書かれており、各数字は1つずつ。1回の操作で6方向に隣接する2つのボールを入れ替えることができる。最下層を除くどのボール(x,y)も自身の直下にある2つのボール(x+1,y), (x+1,y+1)よりも小さい数字となるように、最大10000回の操作でボールを並べ替える問題。できるだけ少ない操作回数で条件を満たすような操作列を求める。 目標: N段のピラミッド型に並んだN(N+1)/2個のボールを、最下層を除くどのボール(x,y)も自身の直下の2つのボール(x+1,y), (x+1,y+1)より小さい数字になるように、6方向の隣接するボール同士の入れ替え操作で並べ替える。操作回数を10000回以内かつできるだけ少なくする。 |
入力: N=30（固定）。ピラミッドの各位置(x,y)にあるボールに書かれた数字bx,y（0≤bx,y≤464）が与えられる。同じ数字のボールは存在しない。 出力: 操作回数Kと、各操作で入れ替える2つのボールの座標(xi,yi), (x'i,y'i)のリスト。K≤10000を満たし、入れ替えるボールは6方向に隣接している必要がある。 |
操作回数をK、操作終了後に条件に違反しているボールのペアの数をEとする。E=0の場合は100000-5K点、E>0の場合は50000-50E点。 |
|
|
|
2023/06/20 20:30 |
2時間 |
概要: おもちゃの車が障害物にぶつかるまでまっすぐ進み、ぶつかると90度右に曲がるというシンプルなルールで動く問題。車は最終的に必ず無限ループに入る。n×nのグリッド上に初期障害物がある状態で、追加の障害物を配置して、無限ループに入るまでの走行距離を最大化することが目標。障害物を置けるのは、最初に空いているマスのみで、初期位置や既存の障害物がある場所には置けない。車の初期位置と向きは固定されており、グリッドの外には出られない（端にぶつかっても右に曲がる）。 目標: n×nのグリッド上で、初期障害物に加えて新たな障害物を配置し、おもちゃの車が無限ループに入るまでの走行距離を最大化する。車は障害物にぶつかると右に90度曲がり、それ以外はまっすぐ進む。 |
入力: グリッドサイズn、開始位置(si,sj)、n×nのグリッド（'#'は初期障害物、'.'は空きマス）。 出力: 新たに配置する障害物の総数m、続いてm行に各障害物の座標(i j)を出力。 |
スコア = round(106 × L/(4E))。Lは無限ループ開始までの走行距離、Eは初期の空きマス数。 |
|
|
|
2023/06/11 15:00 |
4時間 |
概要: N頂点M辺の重み付き平面無向グラフと住民K人の座標が与えられる。各頂点は放送局で、出力強度Piを0～5000の範囲で設定可能。各辺は通信ケーブルで、ON/OFFを設定できる。頂点1から電源ONのケーブルのみを通じて到達可能な放送局のみが出力強度Piの円形領域に放送を届けられる。ケーブルjをONにするとコストwj、放送局iの出力強度をPiにするとコストPi2が発生する。全住民に放送を届けつつ、総コストを最小化する問題。 目標: 全K人の住民に放送を届けるように、各放送局の出力強度（0～5000の整数）と各通信ケーブルのON/OFF状態を決定する。放送局（頂点）から出力強度Piの距離内にいる住民は放送を受信でき、放送可能な放送局は頂点1から電源ONのケーブルのみを経由して到達可能なものに限られる。総コスト（出力強度の二乗和＋使用ケーブルのコスト和）を最小化する。 |
入力: N=100（放送局数）、100≤M≤300（ケーブル数）、2000≤K≤5000（住民数）。頂点i座標(xi,yi)、辺j=(uj,vj,wj)、住民k座標(ak,bk)。 出力: P1 ... PN（各放送局の出力強度、0～5000の整数）、B1 ... BM（各ケーブルのON/OFF、1または0）。 |
全住民に放送が届いた場合はround(106×(1+108/(S+107)))点、n人にしか届かなかった場合はround(106×(n+1)/K)点。Sは総コスト。 |
||
|
2023/03/18 12:00 |
367時間 |
概要: Silhouette Block Puzzleというおもちゃを開発する問題。2組のシルエット（前面と右側から見た形）が与えられ、同じブロックセットを使って両方のシルエットを満たす立体を作成する必要がある。各ブロックは1×1×1の立方体がつながった形状で、回転は可能だが反転は不可。作成する3D形状は各頂点が整数座標で、ブロック同士は重なってはならない。ブロックは全て使い切らなくても良いが、大きいブロック少数で作れるほど評価が高い。 目標: 与えられた2組のシルエットを満たすブロックセットを作成し、それぞれの組み立て方を見つける。各ブロックは連結である必要があり、できるだけ少ない数の大きなブロックでシルエットを実現することが望ましい。 |
入力: D(5≤D≤14)：シルエット画像の大きさ、fi：i組目の前面シルエット、ri：i組目の右側シルエット。各シルエットはD×Dの01行列で、連結成分は1つのみ。 出力: n：ブロックの総数、bi：i組目のブロック配置を表すD×D×Dの三次元配列。各要素は0（空き）または1以上n以下の整数（ブロック番号）。 |
評価値 = round(109 × (r1 + r2 + Σ(1/vi)))、ここでriは使用しなかったブロックの体積の合計、viは両方の組で使用したブロックの体積。相対評価スコア = round(109 × (全参加者中の最小評価値)/(自身の評価値))。各テストケースのスコアの和が得点。 |
||
|
2023/03/05 13:00 |
342時間 |
概要: 「Container Loading」では、異なる大きさと特性を持つ荷物を効率的にコンテナに積み込む問題に取り組みます。コンテナはW×H×D（1120×680×600または1120×680×1200）の直方体で、四隅にはB×B×D（B=30）のブロックがあります。合計M種類の荷物があり、それぞれ寸法（wi×hi×di）、数量（ai）、回転可能か（fi）、上に荷物を積めるか（gi）の情報が与えられます。荷物は垂直に1つずつ積み込み、底面の60%以上が支えられている必要があります。荷物の積み込み順序は自由ですが、入力順に近いほうがより良いスコアとなります。目標は、積み荷の高さを最小化し、入力順からの逸脱を抑え、コンテナの高さDを超えないようにすることです。 目標: 異なる大きさと特性を持つ荷物をコンテナに効率的に積み込み、積み荷の高さを最小化し、入力順からの逸脱を抑え、コンテナの高さを超えないようにする。 |
入力: 1行目：W H D B N M（コンテナの幅、高さ、奥行き、コーナーブロックのサイズ、荷物の総数、荷物の種類数）。続くM行：各荷物タイプの情報（wi hi di ai fi gi）。wi、hi、diは荷物の寸法、aiは数量、fiは回転可能か（Y/N）、giは上に荷物を積めるか（Y/N）。 出力: N行：各行には荷物の情報「p r x y z」を出力。pは荷物の種類番号（0-indexed）、rは回転（0-5）、(x,y,z)は荷物の位置座標。 |
ペナルティ = 1000 + MaxHeight + OrderPenalty + FailurePenalty。MaxHeightは積み荷の最大高さ、OrderPenaltyは積み込み順序の入力順からの転倒数に1000を掛けた値、FailurePenaltyはMaxHeight≤Dなら0、そうでなければ1000000 + 1000×E（Eは高さDを超える荷物の体積の合計）。ペナルティが小さいほど良いスコアとなる。 |
||
|
2023/02/18 12:00 |
199時間 |
概要: N×Nのグリッド上にW個の水源とK個の家が存在する問題。各セルには頑丈さS_{i,j}の岩盤があるが、その値は入力では与えられない。岩盤を掘削して、水源から全ての家までの水道を作る必要がある。掘削では、パワーPを選び、体力C+Pを消費して岩盤の頑丈さをP減らす。頑丈さが0以下になると岩盤が破壊され、水が流れる。水源や水が流れているセルに隣接する破壊された岩盤にも水が流れる。 目標: 全ての家に水が流れるように岩盤を掘削し、消費する体力を最小化する。掘削はセルとパワーを選び、体力を消費して岩盤の頑丈さを減らすアクションを繰り返す。 |
入力: N=200（グリッドサイズ）、W=1〜4（水源数）、K=1〜10（家数）、C∈{1,2,4,8,16,32,64,128}（体力消費パラメータ）、水源と家の座標。テスト間の距離はround(400/(W+K))以上。 出力: インタラクティブ。各手番で「y x P」（座標と掘削パワー）を出力し、結果を入力として受け取る。結果は0（破壊できず）、1（破壊成功、まだ家に水が届いていない）、2（全家に水が届いた）のいずれか。 |
相対評価スコア = round(109 × (全参加者中の最小消費体力)/(自身の消費体力))。各テストケースのスコアの和が最終スコア。 |
|
|
|
2023/01/28 12:00 |
200時間 |
概要: 高橋市の道路補修工事の計画を立てる問題。N頂点M辺の平面無向グラフが与えられ、各辺の工事は1日で完了し、同じ日に最大K本の辺を同時に工事できる。D日間で全ての辺をちょうど1回ずつ工事する計画を立てる。工事中の辺は通行止めとなり、市民は迂回路を使わなければならず不満が生じる。各日の不満度は、全頂点ペア間の最短距離の増加量の平均として定義される。 目標: 工事全体に対する不満度（各日の不満度の平均）を最小化する。工事計画として、各辺を何日目に工事するかを決定する。 |
入力: N(500-1000)：頂点数、M(500-3000)：辺数、D(5-30)：日数、K(ceil(M/D) 出力: r1 r2 ... rM：各辺を何日目に工事するかを表す整数列（1≤ri≤D） |
不満度 = round(103×(1/D)×Σfk)。fkは各日の不満度で、頂点間の最短距離の増加量の平均。相対評価スコア = round(109×(全参加者中の最小不満度)/(自身の不満度))。各テストケースのスコアの和が最終スコア。 |
||
Hitachi Hokudai Lab. & Hokkaido University Contest 2022A - Scheduling of Agricultural Machinery Sharing 画像なし
|
2022/12/23 00:00 |
743時間59分 |
概要: 「農機シェアリング計画最適化問題」は、農業機械の共有計画を最適化する問題。複数の農家が保有する農機を効率的に共有し、各農家の作業を期限内に完了させることが目的。このタスクでは、静的な最適化が求められる。 目標: 限られた農業機械を複数の農家で効率的に共有するスケジュールを計画し、全ての作業を期限内に完了させながら総コストを最小化する。 |
入力: 農家の数、機械の数、各農家の作業内容と期限、各機械の作業能力とコストなどが与えられる。 出力: 各機械をどの農家がいつ使用するかという共有スケジュール。 |
全ての作業が完了する場合は作業コストの総和を最小化。作業が一部完了しない場合は完了した作業数を最大化。 |
|
|
2022/12/10 10:30 |
8時間 |
概要: 「Dowsing Rod（探査棒）」問題では、高橋という超能力者が無人島に埋められた50個の宝物の宝の地図を発見する。島は半径R=109の円形だが、宝物の正確な位置は不明である。高橋は「木の棒」を使って宝物を探す特殊な能力がある。棒を地面に立てると、近くに宝物がある場合は直立し、そうでない場合は特定の方向に倒れる（最も近い宝物の方向に関連）。この能力を使って、1000回の試行以内でできるだけ多くの宝物を見つけることが目標。 目標: 半径R=109の円形の島に埋められた50個の宝物をできるだけ多く見つける。「木の棒」を使って1000回までのクエリで宝物の位置を特定する。棒は宝物が近くにあれば直立し、そうでなければ最も近い宝物の方向に関連した方向に倒れる。このヒントを使って効率的に全ての宝物を見つけることが目標。 |
入力: 標準偏差σ（0.001 ≤ σ ≤ 0.100）が与えられる。各クエリごとに：出力として棒を置く座標(qx, qy)を指定すると、入力応答として「0 θ」（棒が方向θに倒れる）または「rk xk yk」（宝物が見つかった座標）が返される。 出力: 各クエリで、棒を置く座標(qx, qy)を出力する。 |
全ての宝物をQ≤1000クエリで見つけた場合：スコア = 10000-5Q。1000クエリ以内に全ての宝物を見つけられなかった場合：スコア = 100F（Fは見つけた宝物の数）。最終スコアは200テストケースの合計。コンテスト中の最高スコアが最終ランキングを決定する。 |
||
|
2022/11/11 19:00 |
216時間 |
概要: 整数MとエラーRate εが与えられたとき、4≤N≤100の範囲で頂点数Nを決定し、N頂点のグラフG0,G1,...,G_{M-1}を作成する問題。次に、100回のクエリを処理する。各クエリではN頂点のグラフHkが与えられる。Hkはある元のグラフG_{sk}に対し、εの確率で各辺を反転させ、さらに頂点の順番をランダムに並び替えたもの。Hkが元々どのグラフから生成されたかを予測する。 目標: 各クエリで与えられるグラフHkを元のグラフG_{sk}に正しく対応付けられるようなグラフのセットを作成し、グラフ識別の予測精度を最大化する。同時に、可能な限り小さいNを選ぶことも望ましい。 |
入力: 整数M(10≤M≤100)：出力グラフ数、実数ε(0.00≤ε≤0.4)：エラー率。各クエリでは、N(N-1)/2文字の01文字列で表されるN頂点のグラフHkが与えられる。 出力: 最初に頂点数N(4≤N≤100)と、M個のグラフG0,...,G_{M-1}をN(N-1)/2文字の01文字列で出力。各クエリに対しては、Hkがどのグラフから生成されたかの予測tkを出力。 |
スコア = round(109 × (0.9E)/N)、ここでEは予測が外れた回数。各テストケースのスコアは、相対評価方式（自身の得点/最高点 × 109）で計算され、その和が最終スコアとなる。 |
||
|
2022/10/30 15:00 |
4時間 |
概要: 10×10の格子状の箱に、100個のキャンディーを順番に入れていく問題。キャンディーは3種類の味があり、各キャンディーの味はあらかじめ分かっているが、どの位置に入るかは空いているマスからランダムに決まる。キャンディーを1つ受け取るたびに、箱を前後左右のいずれかの方向に1回だけ傾け、各キャンディーを端か他のキャンディーにぶつかるまで移動させる。 目標: 最終的に同じ味のキャンディー同士を可能な限り大きな連結成分にすること。連結成分とは、同じ味のキャンディーが前後左右につながっている集合。 |
入力: 最初に各キャンディーの味ft(1≤ft≤3)が100個与えられる。その後、各ターンで次のキャンディーが置かれる空きマスの位置ptが与えられる。 出力: 各ターンで箱をどの方向に傾けるかを、F(前)、B(後)、L(左)、R(右)の1文字で出力する。 |
スコア = round(106 × (連結成分の大きさの2乗の合計)/(各味のキャンディー数の2乗の合計))。200のテストケースの合計点が得点となる。 |
||
|
2022/09/17 15:00 |
340時間 |
概要: 方眼紙と鉛筆で遊ぶ一人ゲーム。N×Nの方眼紙の上に初期状態でM個の格子点に印が付いている。各ターンで、印のない点p1と印のある3点p2,p3,p4を選び、(1)4点が軸平行または45度傾いた長方形を形成し、(2)長方形の外周上に他の印がなく、(3)既存の長方形と辺を共有しない場合、p1に新たに印を付け長方形を描く。 目標: 最終的に印が付いている点の重み付き合計を最大化する。各点の重みは中心からの距離の2乗+1で定義され、スコアは印のある点の重み合計を全格子点の重み合計で割った値に定数を掛けたもの。 |
入力: N(31-61の奇数)：方眼紙の大きさ、M(N≤M≤N2/12)：初期の印の数、(xi,yi)：初期の印の座標(N/4≤xi,yi≤3N/4)。 出力: K：操作回数と、各操作で選んだ4点の座標(x_{i,1},y_{i,1}),(x_{i,2},y_{i,2}),(x_{i,3},y_{i,3}),(x_{i,4},y_{i,4})。 |
最終スコア = round(106 × (N2/M) × (印のある点の重み合計/全格子点の重み合計))。50のテストケースの合計点が得点。 |
||
|
2022/08/09 21:00 |
168時間 |
概要: N×Nのグリッドで表されるサーバ室には、K種類のコンピュータが100個ずつ置かれている。コンピュータを移動させた後、同種類のコンピュータ同士を直線のケーブルで接続し、クラスタを形成する。ケーブルは格子点に沿った直線で、他のコンピュータを通過できない。各クラスタは同じ種類のコンピュータだけで構成され、異種類のコンピュータを接続することはできない。 目標: コンピュータの移動と接続を行い、クラスタ内の同種類コンピュータの組み合わせ数から異種類コンピュータの組み合わせ数を引いた値である「サーバ室の処理性能」を最大化する。 |
入力: N×Nグリッドの初期状態。K種類のコンピュータが100個ずつ配置されている。 出力: 移動回数X、移動情報、接続回数Y、接続情報。移動と接続の合計回数は100×K以下。 |
サーバ室の処理性能が0より大きい場合はその値、そうでない場合は0点となる。 |
|
|
|
2022/07/03 15:00 |
4時間 |
概要: 原点を中心とした半径104の円形ケーキ上にN個のイチゴが乗っている。ケーキを高々K=100本の直線でカットできる。AtCoder歴がd年の出席者数adが各d=1,...,10について与えられており、ケーキをカットした結果、d個のイチゴが乗っているピースの数をbdとすると、合計min(ad,bd)個のピースを配ることができる。 目標: ケーキをK本以下の直線でカットし、できるだけ多くの出席者にピースを配れるようにする。各直線は2つの異なる整数座標(px,py)と(qx,qy)を通る線として指定する。 |
入力: イチゴの数N、カット回数上限K=100、AtCoder歴d年の出席者数ad(d=1,...,10)、イチゴの座標(xi,yi)。 出力: カット回数kとk本の直線を表す2点の座標(pxi,pyi)(qxi,qyi)を出力する。 |
配れるピース数の比率に基づき、round(106 × ∑min(ad,bd) / ∑ad)の得点が得られる。 |
||
|
2022/05/28 12:00 |
199時間 |
概要: N×Nの盤面上にN2-1枚のタイルが配置され、1マスの空きがある。各タイルには中心から上下左右の方向に線が伸びており、空きマスと隣接するタイルをスライド移動させて、タイル同士の線がつながる木を作る。スライドパズルのように空きマスにタイルを動かすことで、タイルを入れ替えることができる。 目標: 最大でT=2×N3回の操作を行い、線がつながって作られる木の大きさが最大になるような操作列を求める。完全な木（N2-1頂点）を作ることが保証されている。 |
入力: 盤面サイズN(6≦N≦10)、操作回数上限T=2×N3、各マスのタイル情報ti,j（16進数表記の0-9またはa-f）。 出力: 空きマスの上下左右に隣接するタイルをスライドさせる操作を表す、U, D, L, Rからなる文字列。 |
木の大きさがS、操作回数がKのとき、S |
||
|
2022/04/24 15:00 |
4時間 |
概要: 30×30マスに並んだ線路タイルが与えられる。タイルは8種類あり、それぞれ異なる形状の線路が描かれている。各タイルを90度単位で回転させることができ、タイルをつなげて環状線を作る。高橋くんは電車の模型を2台持っているので、できるだけ大きな環状線を2つ作る必要がある。 目標: 各タイルを反時計回りに0〜3回（90度単位）だけ回転させて、できるだけ長い2つの環状線を作る。環状線とは、辺を共有せずに閉じた線路のことを指す。 |
入力: 30×30マスの線路タイルの初期配置ti,j（0≤ti,j≤7）が与えられる。 出力: タイル(i,j)を反時計回りに90度回転させる回数ri,j（0≤ri,j≤3）を表す長さ900の文字列を出力する。 |
一番長い環状線の長さをL1、二番目に長いものをL2として、L1×L2の得点を得る。環状線が1以下の場合は0点。 |
|
|
|
2022/03/26 15:00 |
4時間 |
概要: 20×20マスの地図上で、自宅からオフィスへの通勤経路を示す文字列を作成する。高橋くんは忘れっぽいため、覚えている文字列の一部を忘れてしまうことがある。一部を忘れても高確率でオフィスまでたどり着けるような、頑強な経路を考える。確率pで各文字を忘れた状態で、不明な文字はランダムに選ばれる方向に移動する。 目標: 自宅からオフィスへの通勤経路を、上下左右の移動を表す長さ200以下の文字列として出力する。文字を忘れる確率pがある中で、オフィスに早く到達できる確率が高い経路を設計する。 |
入力: 自宅座標(si,sj)、オフィス座標(ti,tj)、忘れる確率p、および水平・垂直方向の壁の情報が与えられる。 出力: 上下左右を表す「U」「D」「L」「R」からなる長さ200以下の文字列。 |
オフィスに到着したターンtに対して401-tのスコアを得る（未到達は0点）。期待値E[S]を計算し、round(250000×E[S])が得点。 |
|
|
|
2022/02/12 12:00 |
343時間 |
概要: 30x30マスの部屋に、N匹のペット（10-20匹）とM人の人間（5-10人）が居る。各ターンで人間は何もしない、隣接マスを通行不能にする、または移動することができる。ペットは種類によって異なる規則で移動する。各ペットは人間のいるマスには移動できない。300ターン後、各人の満足度を最大化する問題。 目標: 各人が自分の周りに通行可能マスのみでつながる領域を作り、その中にペットが入らないようにすることで最大の満足度を得る。 |
入力: ペットのN匹の初期位置と種類、M人の人間の初期位置が与えられる。 出力: 各ターンで各人の行動を表す長さMの文字列を出力する。 |
各人の満足度 si=|Ri|/900×2(-ni) の平均値に108を掛けて四捨五入した値の合計。 |
||
|
2021/12/18 10:30 |
8時間 |
概要: 「ロボット掃除機のためのコードゴルフ」は、F社が開発中のロボット掃除機をプログラミングする問題。20×20の格子状の床を掃除するロボットは、基本コマンド（L:左回転90度、R:右回転90度、l:左回転45度、r:右回転45度、F:前進）と繰り返し構文を使用してプログラムされる。壁で区切られた床を効率的に掃除するためのプログラムをできるだけ短く記述することが求められる。 目標: ロボット掃除機をプログラミングして、20×20の格子状の床の全てのマスを5000時間単位以内に掃除する。できるだけ短いプログラムを作成することで高得点を獲得する。ロボットは指定された位置から上向きで開始し、各基本コマンドの実行に1時間単位を要する。 |
入力: ロボットの開始位置(si, sj)、水平壁情報(h)、垂直壁情報(v)が与えられる。 出力: 基本コマンド（L, R, l, r, F）と繰り返し構文を使用したプログラムを出力する。 |
プログラムが10,000文字以上または無効な場合：WA（不正解）。全てのマスが掃除された場合（M=N²）：スコア = N² + round(10⁸/(100+L))（Lはプログラムの文字数）。一部のマスが掃除されなかった場合（M |
|
|
|
2021/12/12 16:00 |
4時間 |
概要: 頂点数N=400、辺数M=1995の無向グラフが与えられる。辺の長さ情報が一つずつ与えられ、その都度その辺を採用するかどうかを決定する。最終的に全ての頂点が連結となるように辺を採用し、総長を最小化する問題。 目標: オンラインで与えられる辺の情報を基に、全頂点が連結になるように辺を選び、採用した辺の総長を最小化すること。 |
入力: N=400個の頂点座標と、M=1995本の辺の端点、各辺について一つずつその長さliが与えられる。 出力: 各辺について、採用する場合は1、採用しない場合は0を出力する。 |
最適な全域木の総長Bと採用した辺の総長Aの比率に基づき、round(108×B/A)の得点が得られる。 |
|
|
|
2021/11/14 16:00 |
4時間 |
概要: AtCoder社が運営するフードデリバリーサービスで、1000件の注文（レストランから配達先への配送）の中から50件を選び、配達員が効率的に配達するルートを決定する問題。各注文は二次元平面上の2点として表され、配達員はオフィス(400,400)から出発して戻る。 目標: 1000件の注文から50件を選択し、選んだ注文すべてを処理するルートを計画する。各注文についてレストランを訪れた後に配達先を訪れる必要があり、総移動時間を最小化することが目標。 |
入力: 1000件の注文情報(ai,bi,ci,di)。(ai,bi)はレストラン座標、(ci,di)は配達先座標。座標値は0〜800の整数。 出力: 選んだm=50件の注文番号と、n箇所の訪問地点からなる配達ルート。訪問地点は座標(xi,yi)で表す。 |
出力された配達ルートの総移動時間Tに対し、round(108/(1000+T))の得点が与えられる。 |
|
|
|
2021/10/10 13:30 |
4時間 |
概要: N×Nのボード上にK個のマークされた点があり、これらの点を連結するためにポリオミノを配置する問題。異なる形状のポリオミノが各々コストを持ち、マークされた点を全て連結するために必要最小限のコストでポリオミノを配置することが求められる。ポリオミノは重ならず、ボードの範囲内に収まるように配置する必要がある。 目標: N×Nのボード上でK個のマークされた点を連結するように、与えられたB種類のポリオミノを配置する。全てのマークされた点が連結されるように、かつ合計コストが最小になるようにポリオミノを選択・配置することが目標。 |
入力: N（ボードサイズ）、K（マークされた点の数）、B（ポリオミノのタイプ数）、マークされた点の座標、各ポリオミノの説明とそのコスト。 出力: 使用したポリオミノの数と、それらのタイプおよび位置。 |
スコア = round(108 / S)、ただしSは配置したポリオミノの合計コスト。マークされた点が連結されていない場合や、ポリオミノが重なる/ボードを超える場合はWA（不正解）。コンテスト中の最高スコアが最終ランキングを決定する。 |
|
|
|
2021/09/05 18:00 |
168時間 |
概要: N×Nマスの農場で野菜を収穫して資金を稼ぐ問題。初期資金は1で、収穫機を購入して農場に配置し、M個の野菜を収穫する。野菜はSi日目に区画(Ri,Ci)に出現し、Ei日目に消滅する。収穫機は購入または移動でき、収穫機のある区画に野菜があると収穫され、その価値Viに連結している収穫機の数をかけた資金を得る。最大T-1日間の行動で最終的な資金を最大化する問題。 目標: N×Nマス(N=16)の農場で、T=1000日間の行動を通じて資金を最大化する。各日は「収穫機の購入」「収穫機の移動」「パス」のいずれかを実行。収穫機は連結していると効率が上がり、野菜の価値×連結区画数の資金を得られる。M=5000個の野菜の出現・消滅タイミングを考慮して戦略を立てる。 |
入力: N M T、続いてM行の野菜情報 Ri Ci Si Ei Vi（区画座標、出現日、消滅日、価値） 出力: T行の行動を出力。購入の場合は「r1 c1」（配置座標）、移動の場合は「r1 c1 r2 c2」（移動元と移動先）、パスの場合は「-1」 |
T-1日目終了時にプレイヤーが所持している資金が得点となる。各テストケースの得点の合計が提出の得点。暫定テストは50個、システムテストは1000個のテストケースが用いられる。 |
||
|
2021/08/28 14:00 |
4時間 |
概要: 「魔法使いXの戦い」では、魔法使いXがN体のモンスターと戦います。各モンスターは強さAiを持ちます。Xは「パワーアップ」という魔法を使うことができ、これは位置pのモンスターを選び、位置qのモンスターを選び（同じモンスターでも可）、モンスターpの強さを(Ap + Aq) % Kに変更します（Kは上限値）。この魔法はM回まで使用でき、目標はモンスターたちの強さをできるだけ小さくすることです。特に、最終状態で高々1体のモンスターだけが非ゼロの強さである場合、ボーナス点としてM-（使用した魔法の回数）が加算されます。 目標: モンスターの強さをできるだけ小さくするために、「パワーアップ」魔法を戦略的に使用すること。理想的には、最大1体のモンスターを除いて全てのモンスターの強さをゼロにする。 |
入力: 1行目：N M K（空白区切りの整数）。2行目：A0 A1 ... A_{N-1}（空白区切りの整数、モンスターの強さを表す）。N = 300、M = 1000、K = 108。 出力: 最大M行。各行は2つの空白区切りの整数pi qiを含む。piは強さが変更されるモンスターの位置（0 ≤ pi ≤ N-1）、qiは強さが加算されるモンスターの位置（0 ≤ qi ≤ N-1）。 |
スコア = ceil(∑(log₂K - log₂(Ai + 1)))。さらに、最終状態で高々1体のモンスターだけが非ゼロの強さである場合、(M - 使用した魔法の回数）のボーナス点が加算される。問題は50個のテストケースからなり、最終スコアはすべてのケースのスコアの合計。 |
|
|
|
2021/08/08 10:00 |
180時間 |
概要: 自動車組立ラインの生産スケジュール最適化問題。単一のコンベアベルトに複数の作業ステーションがあり、異なる車種ごとに処理時間が異なる。コンベアベルトの進行速度は一定で、各車には前後の車と一定の距離が必要。各ステーションでの作業には互いに干渉しないための制約がある。制限時間内に指定された需要を満たすように、車種の製造順序を最適化することが目標。効率を最大化し、生産時間を最小化する製造シーケンスを決定する問題。 目標: コンベアベルト式の組立ラインで製造する車種の最適な順序を決定し、時間制限内に生産される車の台数を最大化する。各種は異なるステーションでの処理時間を持ち、コンベアベルトの制約を考慮する必要がある。 |
入力: M S T L（車種数、ステーション数、作業間隔、時間制限）に続き、M×S個の作業時間(ti,j)、S個のステーション位置(xj)、M個の車種需要(ni)。 出力: K（生産する車の台数）に続き、製造する車種を表すシーケンスp1, p2, ..., pKを出力。 |
すべての需要を満たす場合: 106 × (2 - completiontime/L); それ以外: 106/M × sum(sqrt(carsmade/demand))を四捨五入。 |
|
|
|
2021/08/07 16:00 |
4時間 |
概要: 「Patrolling」は、N×Nのグリッドで自動運転の無人パトカーを効率的に巡回させる問題です。グリッドの各マスは道路（5-9の数字）または障害物（#）で表されます。パトカーはスタート位置(si,sj)から始めて、道路マスのみを上下左右に移動することができます。パトカーには全方位カメラが付いており、パトカーがいる位置から上下左右の直線上にある道路マスを「視界に入る」と定義します（ただし障害物があると視界は遮られます）。目標は全ての道路マスが少なくとも一度は視界に入るようなパトカーの巡回ルートを作り、そのルートの総移動時間を最小化することです。各道路マスの数字はそのマスに入るための移動時間を表します。 目標: 全ての道路マスが少なくとも一度は「視界に入る」ようなパトカーの巡回ルートを作り、総移動時間を最小化する。 |
入力: 1行目：N si sj（グリッドサイズとスタート位置）。続くN行：グリッドを表す文字列（'#'は障害物、'5'-'9'は移動時間を表す道路マス）。N は49以上69以下の奇数。 出力: パトカーの移動方向を表す文字列。上下左右の移動はそれぞれ'U'、'D'、'L'、'R'で表す。 |
全道路マスの数をr、視界に入った道路マスの数をv、総移動時間をtとしたとき、v < r（全ての道路マスが視界に入っていない）の場合はscore = round(10,000 × v/r)、v = r（全ての道路マスが視界に入った）の場合はscore = round(10,000 + 10,000,000 × N/t)となる。スコアが高いほど良い。 |
|
|
|
2021/08/07 16:00 |
4時間 |
概要: NxNマスの地図上で、障害物と数字（5-9）で表される道路が与えられる。各マスの数字は移動時間を表す。特定の位置から上下左右に移動し、視界に入る道路を最大化しつつ、元の位置に戻る最短経路を求める問題。 目標: スタート地点から出発し、全ての道路マスが少なくとも一度は視界に入るような巡回ルートのうち、総移動時間が最小のものを求める。 |
入力: N(49-69の奇数)とスタート地点(si,sj)、各マスの情報（'#'は障害物、'5'～'9'は道路の移動時間）が与えられる。 出力: 上下左右の移動をU,D,L,Rで表した巡回ルートを一行で出力する。 |
視界に入った道路マスの割合（v/r）に応じた基本点と、全ての道路マスが視界に入った場合は追加点（104+107×N/t）が与えられる。 |
|
|
|
2021/06/26 13:00 |
6時間 |
概要: 宇宙人の遺伝情報はトーラス状の物質に記録されており、A〜Hの8種類の文字からなるN×Nの行列として表現される。縦方向または横方向に連続する部分列が読み取られているので、これらの情報を元に行列を推定する問題。 目標: 与えられたM個の文字列をできるだけ多く部分列として含むようなN×Nの行列を求める。部分列は横方向または縦方向に一致するもので、行列は端と端がつながっている。 |
入力: Nは20で固定、Mは400〜800、各文字列siはA〜Hからなる長さ2〜12の文字列。 出力: A〜Hと.(空白)からなる長さNの文字列をN行出力する。 |
部分列として含まれる文字列数がM未満の場合は108×(c/M)、M個すべて含む場合は108×(2N2/(2N2-d))。dは空白の数。 |
|
|
|
2021/05/22 12:00 |
200時間 |
概要: 辺の長さが未知の30×30頂点の無向グリッドグラフがあり、1000個のクエリを処理する必要がある。各クエリでは始点と終点が与えられ、そのパスを求めて出力する。実際のパスの長さが計算され、辺の長さを推測しながら徐々に性能を改善する。 目標: 与えられた始点から終点へのパスを1000回求め、できるだけ最短に近いパスを出力すること。各クエリで出力されたパスの長さと最短路長の比率が高いほど高得点となる。 |
入力: 1000個のクエリで各クエリごとに始点と終点の座標が与えられる：sik sjk tik tjk 出力: 始点から終点へのパスをU(上)、D(下)、L(左)、R(右)の文字列で表現したもの。出力後はflushが必要。 |
各クエリの最短路長/出力パス長の比率を重み付け和として計算：\mathrm{round}(2312311\times \sum_{k=1}^{1000}0.998^{1000-k} \frac{ak}{bk}) |
||
|
2021/04/25 19:00 |
4時間 |
概要: 50×50マスの床に1×1、1×2、2×1のいずれかの大きさの長方形タイルが隙間なく敷き詰められている。各マスには整数値が書かれており、高橋くんは(si, sj)のマスからスタートして移動する。移動は隣接するマスへ行うことができるが、同じタイルを二度踏んではならない（初期位置のタイルは既に踏んだとみなす）。訪れたマスに書かれた数値の合計が得点となる。 目標: 同じタイルを二度踏まないという条件の下で、訪れたマスに書かれた数値の合計が最大となるような移動経路を見つける。 |
入力: 初期位置(si, sj)、各マスのタイルID ti,j、各マスの整数値 pi,jが与えられる。 出力: U（上へ移動）、D（下へ移動）、L（左へ移動）、R（右へ移動）を用いて移動経路を文字列で表す。 |
訪れたマス（初期位置のマスを含む）に書かれた数値の合計が経路の得点となる。条件を満たさない出力はWAとなる。 |
||
|
2021/03/06 12:00 |
200時間 |
概要: AtCoder社は10000×10000の正方形スペースにスポンサー企業n社の広告を設置する。各企業の広告は軸に平行な長方形で、頂点座標は整数値、正の面積を持つ。異なる広告は重なってはならないが、辺を接してもよい。空きスペースがあっても良い。企業iは点(xi+0.5, yi+0.5)を含む面積riの広告スペースを希望しており、実際の面積siとの比率に基づいて満足度が決まる。 目標: 各企業の満足度の総和が最大になるように広告スペースを配置する。企業iの満足度は、指定点(xi+0.5, yi+0.5)を含む場合のみ正の値となり、希望面積riと実際の面積siの比率に基づいて計算される。 |
入力: 企業数n(50≤n≤200)と各企業の希望点(xi,yi)および希望面積ri。すべての希望面積の合計は10000×10000。 出力: 各企業の広告スペースを表す長方形の対角となる2頂点の座標(ai,bi),(ci,di)。 |
109 × ∑i=0n-1 pi / n を最も近い整数に丸めた値。piは企業iの満足度で、面積の比率から計算される。 |
||
|
2020/12/12 10:30 |
8時間 |
概要: 50×50のマス目からなる鉱山での鉱石採掘問題。各マスは採掘すると特定の利益が得られる。採掘は隣接するマスのうち少なくとも1つが採掘済みである必要がある（鉱山の外部は採掘済みとみなされる）。採掘コストは採掘予定マスに隣接する採掘済みマス数kに応じて、コスト係数C/kとなる。どのマスをどの順番で採掘するかを決定し、利益-コストの値を最大化する問題。 目標: 50×50マスの鉱山において、各マスの採掘利益とコスト係数Cが与えられる。採掘はマスに隣接する採掘済みマスが1つ以上必要で、採掘コストはC/k（kは隣接する採掘済みマス数）。採掘するマスとその順序を決定し、総利益p-総コストcを最大化する。 |
入力: 採掘コスト係数C、50×50マスそれぞれの採掘利益pi,j（外周マスはすべて0） 出力: 採掘するマスの総数M、採掘する順番にマスの座標(ik, jk)をM行出力 |
利益の総和がp、コストの総和がcのとき、max(0, p-c)点が得られる。100個のテストケースの合計が最終スコア。不正な出力をした場合、提出全体がWA判定。 |
|
|
|
2020/11/07 14:00 |
8時間 |
概要: 「カードの回収」では、20×20のグリッド上に0から99までの番号が付いた100枚のカードがランダムに配置されている。プレイヤーは左上隅(0,0)から開始するロボットを操作し、全てのカードを回収する。ロボットは上下左右に移動でき、現在地のカードを回収したり、回収済みのカードを置いたりできる。最終的に手持ちのカードが下から順に0,1,...,99となるように回収・操作を行う必要がある。 目標: ロボットをコマンド（U:上、D:下、L:左、R:右への移動、I:カードの回収、O:カードの設置）で操作し、全てのカードを回収して、最終的に手持ちのカードが下から順に0,1,...,99と昇順に並ぶようにする。移動コマンド（U,D,L,R）の回数をできるだけ少なくすることが目標。 |
入力: 100行の入力で、各行はカード番号iの座標(xi, yi)を表す2つの整数が与えられる。 出力: ロボットの操作コマンド列を1行で出力する。 |
スコア = 4000 - k（kは移動コマンドU,D,L,Rの回数）。カードの回収・設置コマンド（I,O）はスコアに影響しない。移動コマンドが4000回を超える場合やコマンド列の長さが10000を超える場合、不正な操作や最終状態が条件を満たさない場合はスコア0となる。 |
|
|
|
2020/09/27 21:00 |
2時間30分 |
概要: N×Nのパネルがあり、各パネルは色1からKのK色で塗られている。パネルをタッチして好きな色に変えられるが、タッチしたパネルから上下左右に隣接する同じ色のパネルだけを辿って到達できる全てのパネルが同時に色が変わる。目標は全てのパネルを同じ色に揃えること。最も多いパネルの色を持つパネル1枚につき100点を得るが、タッチ1回ごとに1点失う。10000回以上タッチすると0点となる。 目標: N×N(N=100)のパネルで、最も多い色のパネル数を最大化しながらタッチ回数を最小限にする。各パネルは色1〜9の9色でランダムに塗られている。パネルをタッチすると、そのパネルから上下左右に隣接する同じ色のパネルが全て指定した色に変わる。最終得点は(最も多い色のパネル数×100)-(タッチ回数)で計算される。 |
入力: id N K、続いてN行の文字列Si。Si,jは上からi番目、左からj番目のパネルの色（1〜K）を表す。 出力: 最初の行にタッチ回数Q、続くQ行にはYi Xi Ciを出力する。Yi、Xiはタッチするパネルの座標、Ciは変える色を表す。 |
50個のテストケースに対する得点の和が最終スコア。各テストケースでは、最も多い色のパネル数×100点から、タッチ回数を引いた点数が得られる。ただし、タッチ回数が10000回を超えると0点となる。 |
|
|
|
2020/06/28 21:00 |
2時間 |
概要: AtCoderがコンテストを26種類に増やし、D=365日間の開催スケジュールを決定する問題。各タイプのコンテスト開催による満足度の増加s_{d,i}と、連続で開催されないことによる満足度の減少があり、タイプごとに開催コストciが異なる。毎日どのタイプのコンテストを開催するかを決めて、最終的な満足度を最大化する。 目標: 最終的な満足度が最大となるように365日分のコンテスト（26種類）のスケジュールを決定すること。連続開催による不満減少と、コンテスト満足度の合計値からコスト総和を引いた値が最終満足度。 |
入力: D=365、各タイプのコストci、各日各タイプの満足度増加量sd,i。 出力: 各日に開催するコンテストのタイプt1からtDを一日一行で出力。 |
最終満足度をSとすると、max(106 + S, 0)が得点。50テストケースの合計得点が最終スコア。 |
||
|
2020/03/07 14:00 |
4時間 |
概要: 「ハイパー覆面すごろく (Hyper Masked Sugoroku)」は、サイコロをカスタマイズしながらボードゲームを進める問題。N+1マス（0からN）のゲームボードがあり、各マスiには隠された価値Viがある。Mラウンドでサイコロを振り、出た目の数だけ前進する。ゴールを超えた場合は余った分だけ戻る。ゴールに正確に到達した場合はスタートに戻る。各ラウンドの前に、サイコロの1つの面を1～6の任意の値に変更できる。最初のサイコロは標準的な値[1,2,3,4,5,6]を持つ。 目標: サイコロの面を戦略的に変更しながらゲームを進め、訪れたマスの価値の合計（総スコア）を最大化する。 |
入力: 最初の行：N M（実際のテストではN=500、M=5000）。その後、Mラウンドの対話形式で：プログラムがサイコロの6つの面を表す6つの整数を出力し、d v x（サイコロの出目、現在のマスの価値、現在の位置）を受け取る。 出力: 各ラウンドで、サイコロの6つの面を表す6つの整数（1～6の範囲）。 |
各テストケースのスコアは、訪れたマスの価値の合計。50のテストケースがあり、最終スコアはすべてのテストケースのスコアの合計。ゴールマス（N）の価値は5000点。 |
|
|
|
2020/02/15 19:00 |
4時間 |
概要: 「ゲーマーXとモノス大会」では、プレイヤーはゲームモノスで高得点を狙います。20×20グリッドの盤面に色と数字の書かれたモノミノ（1マスサイズのピース）を置いていき、同色の数字の合計点数を競います。1回の操作で、盤面の空きマスにモノミノを1つ置きます。次のモノミノの色と数字は予測できず、合計300個のモノミノを置く必要があります。置いたモノミノは動かせません。同色のモノミノが隣接していれば連結とみなされ、各連結成分の点数は「その連結成分に含まれるモノミノの数字の和」の2乗となります。 目標: 20×20の盤面に300個のモノミノを順番に配置し、同色の連結成分の点数（「数字の和」の2乗）の合計を最大化する。 |
入力: 最初の行にN（グリッドサイズ）, M（モノミノの数）が与えられる。次のM行には各モノミノの色と数字が与えられる。N=20, M=300で固定。 出力: M行の出力。各行にモノミノを置く位置（行と列）を「r c」の形式で出力する。 |
各色の連結成分について「その連結成分に含まれるモノミノの数字の和」の2乗を計算し、それらの合計がスコアとなる。 |
|
|
|
2019/12/07 14:30 |
4時間 |
概要: 「千の木2」は、2次元座標平面上にN=1000個の頂点があり、S=1000個の無向木が与えられる問題。頂点間に辺を追加して無向グラフGを作成し、与えられた木それぞれをGの頂点の部分集合にマッピングする。各頂点iは座標(xi, yi)と「力」ciを持ち、2頂点i, j間の距離がci + cj以下の場合のみ辺を追加できる。目標は、各木に対応する部分グラフを元の木に「類似」させること。各木Tiに対して、Tiの全ての辺がGにある場合に得点が与えられ、余分な辺が少ないほど高得点となる。 目標: 2次元平面上のN個の頂点間に辺を追加して無向グラフGを作成し、S個の与えられた木をGの部分集合に割り当てる。各頂点の「力」とユークリッド距離に基づく制約内で辺を追加し、各木に対応する部分グラフが元の木に近い（余分な辺が少ない）ほど高得点となる。 |
入力: N S、各頂点の座標(xi, yi)と力ci、およびS個の木の構造（各頂点の親を表す）が与えられる。N=S=1000固定。 出力: M本の辺(Ai, Bi)とS個の割り当て（各木の各頂点がGのどの頂点に対応するか）を出力。 |
各木Tiごとに：Tiの辺がすべてGにある場合、余分な辺数eiに応じて得点が決まる。ei=0なら100点、ei=1なら10点、ei=2なら1点、ei≥3なら0点。全S個の木の得点の合計がスコア。 |
|
|
|
2019/12/07 10:30 |
4時間 |
概要: 二次元平面上にN個の頂点があり、各頂点にはパワー値が設定されている。S個の木構造（各木はK個の頂点を持つ）が与えられる。頂点間の距離がパワーの合計以下の時に辺を追加でき、これによりN頂点のグラフGを作成する。S個の木それぞれに対して、Gから対応するK頂点を選び、元の木と「似た」部分グラフを作る。似ているほど高得点となる。 目標: 二次元平面上にN=1000個の頂点があるグラフGに辺を追加し、与えられたS=1000個の木（各木はK=20頂点）に似た部分グラフをGから取り出す。各木Tiに対して、Gの頂点Vi,1...Vi,Kを選び、辺の有無が元の木と一致するほど高得点を得る。辺の不一致が少ないほど良い。 |
入力: N S K、各頂点の座標(xi,yi)とパワーci、S個の木それぞれについて各頂点の親ノード情報p_{i,j}（N=1000、S=1000、K=20に固定） 出力: 作成するグラフGの辺の数M（0≤M≤100000）と各辺の端点、S個の木それぞれに対応するGの頂点番号V_{i,1}～V_{i,K}を出力 |
各木について：元の木に辺があるがGにない場合は0点、それ以外の場合、Gに辺があるが元の木にない辺の数eiに応じて、ei=0なら100点、ei=1なら10点、ei=2なら1点、ei≥3なら0点となる。 |
|
|
|
2019/11/02 14:00 |
8時間 |
概要: 「ロボットの誘導」では、N×N (N=40) のグリッド上にM=100体のロボットと、B=300個の壁がランダムに配置されている。ロボットは初期方向に動き、グリッドの端はつながっている（トーラス状）。プレイヤーはグリッド上に方向ガイドを配置し、ゴールに到達するロボットの数を最大化する。ロボットは方向ガイドに従って方向転換し、ゴールに到達するか壁に当たると停止する。 目標: N×Nグリッド上にロボットと壁が配置されている状態で、方向ガイドを適切に配置してより多くのロボットをゴールに誘導する。ゴールに到達するロボット数を最大化し、使用するガイド数を最小化し、ロボットが通過するユニークなセル数を最大化することがポイント。 |
入力: N M B（グリッドサイズ、ロボット数、壁数）、ゴール座標、各ロボットの座標と初期方向、各壁の座標が与えられる。N=40, M=100, B=300で固定。 出力: K（方向ガイド数）と、各ガイドの座標および方向を出力する。 |
スコア = 1000 × A - 10 × B + C （A: ゴールに到達したロボット数、B: 配置した方向ガイド数、C: ロボットが通過したユニークなセル数）。50のテストケースの合計スコアが最終スコアとなる。 |
|
|
|
2019/08/31 21:00 |
2時間 |
概要: N×Nのマス目に数値を書き込み、縦または横に連続した数の区間和が好きな数B1、B2、B3になるものをできるだけ多く作る問題。ただし、各マスには書き込める数の最小値li,jと最大値ri,jが決められている。和がB1、B2、B3となる縦または横の区間の数をA1、A2、A3としたとき、A1×B1+A2×B2+A3×B3が得点となる。 目標: 30×30のマス目に制約を満たす数値を書き込み、縦または横に連続する区間の和がB1(10～19)、B2(20～29)、B3(30～39)のいずれかになる区間をできるだけ多く作成し、得点A1×B1+A2×B2+A3×B3を最大化する。 |
入力: 最初の行にN B1 B2 B3、続いてN行にわたり各マスの最小値li,j、さらにN行にわたり各マスの最大値ri,jが与えられる。 出力: N行N列のマス目に書き込む数値Ai,jをN×N個の整数として出力する。全ての整数はli,j≦Ai,j≦ri,jを満たす必要がある。 |
和がB1、B2、B3となる縦または横の区間の数をA1、A2、A3としたとき、A1×B1+A2×B2+A3×B3が得点となる。不正な出力の場合はほぼ全てのテストケースが0点となる。 |
|
|
|
2019/03/23 13:00 |
8時間 |
概要: 立方体の箱に異なる半径の球を詰め込む問題。各球は重ならず、箱からはみ出さないように配置する必要がある。各球には基本点が設定されており、特定の球のペアが一定の距離内に配置されるとボーナス点が加算される。1000×1000×1000の立方体コンテナに球を戦略的に配置して総得点を最大化する。球は半径Rの整数値を持ち、コンテナ内に配置するかどうかを選択できる。各球の配置とペア間の距離を考慮して、最適な配置戦略を見つける必要がある。 目標: 1000×1000×1000の立方体コンテナに球を戦略的に配置し、各球の基本点と特定の球ペアのボーナス点を考慮して総得点を最大化する。球は重なったり、コンテナからはみ出したりしてはならない。各球は配置するかしないかを選択できる。 |
入力: L N M に続き、N行の半径と点数の値、さらにM行の球ペアのボーナス点条件。L=1000固定。 出力: N行、各球のX Y Z座標。コンテナに配置しない球は(-1, -1, -1)で表す。 |
配置された各球の基本点と、一定距離内に配置された特定の球ペアに対するボーナス点の合計。 |
|
|
|
2019/03/02 14:00 |
4時間 |
概要: 「めくってそろえる」は、神経衰弱のようなインタラクティブ問題です。N個の山札（各山札には1以上⌊N/2⌋以下の整数が書かれたカードが積まれている）が横一列に並んでいます。プレイヤーは山札の上を移動し、カードをめくって同じ値のカードを見つけるとペアで取り除いてスコアを獲得します。ゲーム開始時、プレイヤーは山札0の上にいて、初期スコアは0です。プレイヤーは移動可能な総距離Tを超えない範囲で操作を繰り返すことができます。操作では、現在の山札から別の山札に移動し、その山札の一番上のカードを表向きにします。もし表向きのカード同士が同じ値ならば、それらをペアで取り除いてカードの値分のスコアを獲得します。目標は得点を最大化することです。 目標: 移動可能な総距離T以内で、同じ値のカードペアをなるべく多く見つけて、獲得スコアを最大化する。 |
入力: 1行目：N T（山札の数、移動可能な総距離）。N = 50。その後、インタラクティブ形式で、めくったカードの情報や操作結果が返されます。 出力: 各操作で移動先の山札番号qを出力します。インタラクティブなので、山札の状態を考慮して次の行動を決定する必要があります。 |
同じ値のカードをペアで取り除くと、そのカードに書かれた整数分のスコアを獲得します。最終スコアが高いほど良い評価となります。 |
|
|
|
2019/02/11 19:00 |
4時間 |
概要: N=200個の都市を巡回する旅行計画を立てる問題。各都市の座標(xi, yi)が与えられており、都市間の移動距離はユークリッド距離で定義される。毎日1つの都市を訪れ、N日目には最初の都市に戻る必要がある。旅行計画として、各都市の訪問順序を決定する。 目標: 1日の移動距離の分散が最小になるような都市の訪問順序を決定すること。分散は各日の移動距離dと移動距離の平均averageを用いて、variance = (1/N)×Σ(dj - average)2で定義される。 |
入力: 都市数N=200と各都市の座標(xi, yi)が与えられる。座標は0≤xi, yi≤500の範囲の整数。 出力: 都市の訪問順序を表す0〜N-1の整数列（都市番号）を出力する。 |
各テストケースの得点は、106÷(1+variance)の小数点以下を切り上げた値。50テストケースの合計点が最終スコア。 |
|
|
|
2018/12/01 10:30 |
8時間 |
概要: 「モンスターテイマー」は、モンスター「タカハシくん」を育成するシミュレーションゲーム。プレイヤーは1000ターンの間、10種類のスキルの訓練、野生モンスターとの戦闘、クエスト達成を通じてお金を稼ぐことが目標。各ターンでは、スキル訓練（特定のスキルを1上げる）、クエスト受注（特定のスキルレベルが必要、成功すると報酬獲得）、アルバイト（確実に少額のお金を稼ぐ）のいずれかの行動を選択する。クエストには有効期限があり、スキルレベルが要求を満たさないと失敗する。最終的なお金の量を最大化するための戦略的な意思決定が求められる。 目標: 1000ターンの間に、スキル訓練、クエスト受注、アルバイトの3つの行動から選択し、タカハシくんのスキルを育成しながらお金を最大化する。10種類のスキルと複数のクエストの要求・報酬バランスを考慮し、最適な行動選択が重要。 |
入力: T N M（ターン数、スキル数、クエスト数）に続き、M行のクエスト情報（Ai Bi Ci Si,1 Si,2 ... Si,N）が与えられる。 出力: 1000行の行動を出力。各行は「1 X」（スキルX訓練）、「2 Y」（クエストY受注）、「3」（アルバイト）のいずれか。 |
最終的なお金の量がスコアとなる。30テストケースのスコアの幾何平均が最終順位を決定する。 |
|
|
|
2018/11/10 14:00 |
8時間 |
概要: 「ばらばらロボット」は、29×29マスのボードをデザインして、500種類の異なるコマンドシーケンスに従うロボットが異なる位置で停止するようにする問題。ロボットは前進(S)、左折(L)、右折(R)のコマンドを実行するが、その効果は特殊タイルによって変更される。壁(#)があると移動できず、数字タイル(D, T)はその数分コマンドを繰り返し、方向変更タイル(L, R)は強制的に方向転換させる。目標は、異なるコマンドシーケンスを持つロボットが、できるだけ多くの異なる位置で停止するようなボード配置を設計すること。 目標: 29×29マスのボードに特殊タイル（壁、数字、方向変更）を配置し、500種類の異なるコマンドシーケンスを実行するロボットが、できるだけ多くの異なる位置で停止するようにする。同じマスに少数のロボットが停止するほど高得点となる。 |
入力: 最初の行にN M L（500 29, 300）が与えられ、続くN行に長さLのコマンドシーケンスが与えられる。 出力: M行M文字、ボードの各マスを表す特殊文字（通常マス".", 壁"#", 数字"D"(2), "T"(3), 方向変更"L", "R"）を出力。 |
1ロボットが停止するマスは10点、2ロボットが停止するマスは3点、3ロボットが停止するマスは1点、それ以上は0点。総合得点はこれらの合計。 |
|
|
|
2018/03/10 14:00 |
4時間 |
概要: 「ぐるぐる庭園」では、プレイヤーはK日の間に庭師として働きます。プレイヤーは毎日、庭のセル（マス）を1つ選んで作業を行うことができます（何もしないこともできます）。庭には妖精がおり、プレイヤーが作業を行った後、妖精は8方向のいずれかにランダムに移動します。妖精が通過した場所には花が咲きます。セルには満足度値があり、そのセルで花が咲くと、プレイヤーはその満足度に応じたポイントを獲得します。同じセルに2回以上花が咲いても追加ポイントはありません。プレイヤーの目標は、K日間でできるだけ多くのポイントを獲得することです。 目標: K日間、毎日1つのセルで作業を行うか何もしないかを決定し、妖精の移動経路上に咲く花による満足度ポイントを最大化する。 |
入力: 1行目：H W K（庭の高さ、幅、日数）。続くH行：各行にW個の整数sij（各セルの満足度）。最後の行：sy sx（妖精の初期位置）。 出力: K行：各行にプレイヤーが作業を行うセルの座標「y x」を出力。セルで作業しない場合は「-1 -1」を出力。 |
妖精が通過したセルに花が咲き、そのセルの満足度分のポイントを獲得する。同じセルに複数回花が咲いても追加ポイントはない。最終スコアは獲得したポイントの合計。 |
|
|
|
2018/03/03 10:30 |
8時間 |
概要: 「ツカモの栽培」は、50×50のグリッド上で植物「ツカモ」を栽培するシミュレーションゲーム。プレイヤーの目標は、1000ターンの間に可能な限り多くのツカモを収穫すること。グリッドは更地、畑（ツカモが生えている）、岩、ワープゲート、道路のマスで構成されている。プレイヤーは各ターンで、道路の作成、ツカモの植え付け、収穫、更地化、労働力アップ、ワープゲート作成、アルバイトのいずれかの行動を取ることができる。ツカモは成長して繁殖するが、同じマスに100本揃うと岩になる。 目標: 50×50のグリッド上で1000ターンの間に行動を選択し、植物「ツカモ」をできるだけ多く育てて収穫する。お金と労働力を管理しながら、道路やワープゲートを戦略的に配置し、ツカモの成長と収穫のタイミングを最適化する。 |
入力: 50×50のグリッドの初期状態（'.'=更地、'#'=岩、'W'=ワープゲート）。マス(x,y)は左上が(1,1)、右下が(50,50)。 出力: 1000行の行動を出力。各行は「コマンド 座標指定」の形式。コマンドは道路作成/植え付け/収穫/更地化/労働力アップ/ワープゲート作成/アルバイトから選択。 |
1000ターン終了時までの収穫したツカモの総数がスコアとなる。50テストケースの合計点が最終スコアとなる。 |
|
|
|
2018/02/17 14:00 |
8時間 |
概要: N行N列のマス目Aが与えられる。これは初期マス目（全マスが0）に対して1000回の「山型足し算」を行って生成されたもの。山型足し算(X,Y,H)は、位置(X,Y)を中心に高さHの山を作る操作で、各マスには max(0, H - |x-X| - |y-Y|) を加算する。与えられたマス目と同じマス目を山型足し算の組み合わせで再現する。 目標: 与えられたマス目Aにできるだけ近いマス目Bを生成する山型足し算の手順を求める。マス目Aと完全に一致した場合は山型足し算の回数を最小化する。 |
入力: N行N列のマス目A（N=100、各マスの値は0～100,000） 出力: 山型足し算の回数Qと、Q回分の山型足し算のパラメータ（X, Y, H）を出力する。 |
基本点として 1010 / (Σ|Ai,j - Bi,j| + 1) 点が得られる。マス目が完全一致した場合、ボーナス点として（1000-Q）点が追加される。 |
|
|
|
2018/02/11 19:00 |
4時間 |
概要: 「ゲーム実況者Xの挑戦」では、プレイヤーはH行W列のマップ上でキャラクターを動かし、できるだけ多くのコインを集めることを目指します。マップには壁、コイン、罠、空きマスがあり、外周は壁で囲まれています。プレイヤーは上下左右の方向にキャラクターを動かすことができますが、壁のあるマスには移動できません。また、マップ上には罠があり、罠のあるマスに入るとゲームが終了します。プレイヤーの目標は、罠に引っかからずに制限ターン以内でできるだけ多くのコインを集めることです。 目標: H×Wのマップ上でキャラクターを操作し、罠に引っかからないように制限ターン以内にできるだけ多くのコインを集める。 |
入力: 1行目：N K H W T（テストケース数、各テストケースの数、マップの高さ、幅、制限ターン数）。続くH行×N個のブロック：各ブロックはH行W列のマップを表し、'#'は壁、'.'は空きマス、'o'はコイン、'x'は罠を表す。 出力: K行：各行にはプレイヤーの移動方向を表す文字列を出力する。移動方向は'U'（上）、'D'（下）、'L'（左）、'R'（右）で表される。 |
プレイヤーが集めたコインの数がスコアとなる。罠に引っかかるとゲームが終了し、それまでに集めたコインの数がスコアとなる。 |
||
|
2017/12/15 12:00 |
744時間 |
概要: 「Satellite data compression」は、GOES-16気象衛星からのデータを圧縮・解凍するプログラムを作成する問題です。データは16チャンネル（異なる波長の光に対応）で、4つの観測（5分間隔）から得られた64個のファイルで構成されています。これらは、アメリカ大陸の観測データ（CONUSデータ）です。目標は、データを可能な限り効率的に圧縮し、元のデータに完全に復元できる（ロスレス）アルゴリズムを開発することです。圧縮と解凍の両方を行える単一のプログラムが求められます。圧縮アルゴリズムはロイヤリティフリーである必要があり、圧縮と解凍の合計実行時間は600秒以内に収まる必要があります。 目標: GOES-16気象衛星からの64個のデータファイルをロスレス圧縮し、できるだけ高い圧縮率を達成する。同じプログラムで圧縮と解凍の両方が行えることが必要。 |
入力: 圧縮フェーズでは、「encode」、出力ファイル名、圧縮するディレクトリ、ファイル数（N=64）、ファイル名とサイズが入力として与えられる。解凍フェーズでは、「decode」、圧縮ファイル名、出力ディレクトリが与えられる。 出力: 圧縮時：指定された場所に1つの圧縮ファイルを作成する。解凍時：すべてのファイルを指定されたディレクトリに抽出する。ファイルは元のデータと完全に一致する必要がある。 |
スコア = 圧縮率 × 1,000,000。圧縮率 = 1 - (圧縮後のサイズ / bz2圧縮後のサイズ)。bz2圧縮の参照サイズは507,803,245バイト。bz2より高い圧縮率を達成すると、その率に応じて賞金額が増加する。 |
||
|
2017/03/20 14:00 |
4時間 |
概要: 「石油王Xの憂鬱」では、8つの油タンクを管理して顧客にサービスを提供します。各顧客は特定の量の油（D）を欲しており、限られた時間（T）だけ待ちます。目標は、各顧客にD量の油を正確に販売してD²の価格を得ることで収益を最大化することです。毎分、以下のいずれかのアクションを実行する必要があります：タンクに油を満タンにする、あるタンクから別のタンクに油を移動する、タンクを新しい空のタンクに交換する、待機（現在の顧客を見送る）、または特定のタンクを使って油を販売する（それらの油の合計がDと等しい場合）。 目標: 8つの油タンクを戦略的に管理し、顧客が欲する正確な量の油を販売することで、収益（販売量の2乗の合計）を最大化する。 |
入力: 各アクション（1000回）に対して： D T C1 C2 C3 C4 C5 C6 C7 C8 A1 A2 A3 A4 A5 A6 A7 A8 ここでDは希望する油の量、Tは残りの待機時間、Ciはタンクの容量、Aiはタンクiの現在の油量です。 出力: 各入力後に以下のフォーマットのいずれか： ・「fill i」：タンクiに油を満タンにする ・「move i j」：タンクiからタンクjに油を移動する ・「change i」：タンクiを新しい空のタンクに交換する ・「pass」：現在の顧客を見送る ・「sell n x1 x2 ... xn」：合計がD量になるn個のタンクから油を販売する |
油を販売するたびに、D²ポイントを獲得します。スコアは、すべてのテストケースでの獲得収益の合計です。合計50のテストケースがあります。 |
|
|
|
2017/03/04 20:00 |
3時間 |
概要: 「Multiple Pieces」では、50×50のグリッドが与えられ、各マスには0から9までの数字が書かれています。プレイヤーの目標は、このグリッド上にできるだけ多くの「ピース」を作ることです。各ピースは正確に8つの連結したマスから構成され、その得点はそれらのマスに書かれた8つの数字の積となります。一度ピースに使用したマスは、他のピースに再利用できません。連結とは、隣接するマス（上下左右）を通じて到達可能なことを意味します。 目標: 50×50のグリッド上で、8マスから成る連結したピースをできるだけ多く作り、各ピースのスコア（8つの数字の積）の合計を最大化する。 |
入力: 1行目：H W K（H=50, W=50, K=8）。続くH行：各行にW個の数字（0-9）が並ぶ。 出力: 1行目：C（作成したピースの数）。続くC×K行：各ピースの各マスの座標（y x）。各ピースの8マスは連続して記載する必要がある。 |
各ピースのスコアは、そのピースを構成する8つのマスの数字の積。総スコアは全ピースのスコアの合計。最終得点は、総スコアを10,000で割って切り上げた値。10のテストケースがあり、最終スコアは全テストケースの得点の合計。 |
|
|
|
2017/02/19 13:00 |
8時間 |
概要: 50×50の正方形ブロックが与えられる。ブロックは「o」「x」「.」の3種類があり、「.」ブロックは消滅して上にあるブロックが落下する。プレイヤーは消滅前に「.」ブロックを「+」（消滅しない通常ブロック）か「-」（消滅せず落下もしないブロック）に変換できる。消滅後の上下左右に連結する「o」ブロックの最大数と「x」ブロックの最大数の和を最大化することが目標。 目標: 50×50のブロック配置において、「.」ブロックを「+」または「-」ブロックに変換して、「.」ブロック消滅後の連結する「o」ブロックの最大グループサイズと「x」ブロックの最大グループサイズの和を最大化する。「+」は消滅せず、「-」は消滅も落下もしない特殊ブロック。 |
入力: N=50行のブロック配置。各行はN=50文字の文字列Siで、各文字Si,jは「o」「x」「.」のいずれか。 出力: 変更後のブロック配置を出力。「.」ブロックを「+」か「-」に変換した結果を出力する。その他のブロックはそのまま。 |
10個のテストケースに対し、各ケースでの得点（消滅後の連結する「o」ブロックの最大数と「x」ブロックの最大数の和）の合計が最終スコアとなる。 |
|
|
|
2016/11/03 20:00 |
3時間 |
概要: 1以上109以下の整数を100個出力する問題。各整数の約数の集合に対する和集合のサイズが得点となる。例えば、12と16を出力した場合、12の約数は{1,2,3,4,6,12}、16の約数は{1,2,4,8,16}であり、和集合は{1,2,3,4,6,8,12,16}となり、サイズは8が得点となる。できるだけ多くの異なる約数を持つ整数を選んで出力し、高いスコアを目指す。 目標: 1以上109以下の整数を100個出力する。出力した整数の約数の集合の和集合のサイズを最大化することが目標。異なる約数をできるだけ多く含む整数を選んで、和集合のサイズを大きくする。 |
入力: 入力は与えられない。 出力: 整数を100個、改行区切りで100行で出力する。各整数は1以上109以下。 |
出力した100個の整数の約数の集合の和集合のサイズが得点となる。サイズが大きいほど高得点。 |
|
|
|
2016/03/20 13:00 |
8時間 |
概要: 30×30のマス目に1-100の整数が書かれており、マスを選んで数を減らしていく「山崩しゲーム」。選んだマスの数を1減らし、上下左右に同じ数のマスがあれば連続して選択できる。選択したマスの数が全て同時に1減る。マスの数が0になるとそのマスは消える。すべてのマスを0にするのが目的。 目標: すべてのマスを0にするために必要な手数を最小化すること。各手は1つのマスを選ぶことから始まり、隣接する同じ数のマスを連続して減らすことができる。 |
入力: 30×30のマス目に書かれた整数（1≦Ai,j≦100）が与えられる。整数は1-100から均等な確率でランダムに選ばれる。 出力: 高橋君が数を減らすマスの順番を、行、列の順番でスペース区切りで出力する。手の区切りは不要。 |
各テストケースについて、出力が正しければ「100000 - 手数」の点数が得られる。全テストケースの合計点が最終スコア。 |
|
