競プロ-ICPC
問題. Waterworld 下図のように表面が分割された球が与えられる。水平方向には高さが等しくなるように 分割されており、垂直方向には 等分されている。 ステップ目のときの領域 の表面積に占める水の量の割合をパーセント表記したものを とする。 球全体の表…
問題. Turning Red 個のライトと 個のボタンがある。ライトは赤、緑、青の三色のいずれかで点灯する。ライトの色を変えることができるボタンを1回押すと、赤は緑に、緑は青に、青は赤に色を変える。 各ボタンに対して、そのボタンを押すと同時に色が変わるラ…
問題. Riddle of the Sphinx 3種類の生物がいる。それぞれの種類の足の数を答えよ。問題を解くためにスフィンクスに「」という形式の質問を 5 回行う。これは 3 種類の生物がそれぞれ 匹いるときの足の本数の合計を訊ねる質問である。この質問に対してスフィ…
問題. Compression 0 と 1 からなる非空な文字列 が与えられる。 の連続する 2 つの同じ連続部分列に対して 1 つの連続部分列を取り除く操作を再帰的に繰り返していく。最終的に得られる文字列の中で長さ最小のものを答えよ。制約:
問題. Carl’s Vacation 2 つのピラミッドがある。そのピラミッドの頂上間の最短距離を求めよ。ピラミッドの形状は で表される。ピラミッドの形状は真上から見ると正方形で、正方形のある一辺をピラミッドを左にしながら点 から点 へ向かう線分で表す。ピラミ…
問題. Icpca 文字 種類の相異なる英大文字からなる文字列 と、式 が与えられる。 式 は次の文法規則からなる。 ・E F | '(' E '' E ')' ・F | | | ただし、不等式の評価は ならば 、 ならば とする。 上の全順序のうち式 と の値が等しくなるものの数を求め…
問題. 接触追跡 あるアプリを利用している人が 人いる。その中で 番目の利用者は感染者である。時刻順に濃厚接触の記録が 件与えられる。 番目の記録 は 番目と 番目の利用者が濃厚接触したことを表している。感染者と直接的または間接的に感染した疑いのあ…
問題. 荷物 正整数 が与えられる。正整数 で を満たすもの中で の最小値を答えよ。 制約:
問題. 天秤 個の薬品と 個の分銅の重さが与えられる. 番目の薬品の重さは で, 番目の分銅の重さは である.すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ.ただし,釣り合わないときは任意の重さの分銅を 1 つだけ追加するこ…
問題. Routing a Marathon Race 無向グラフ ,2頂点 ,頂点重み が与えられる. から へのコスト最小の道を見つけそのコストを答えよ.ただし,道のコストとはその道に含まれる頂点の重み和と,道に少なくとも1頂点が隣接する道以外の頂点の重み和を足したも…
問題. Sixth Sense 2つの整数列 が与えられる. 番目の要素が よりも大きくなるような要素が最も多くなるように を並び替えよ.そのような並び方が複数ある場合は辞書式順序で最も大きいものを求めよ.制約: ,
問題. Four-Coloring 無向グラフ の平面描画が与えられる.頂点 の座標を としたとき,各辺 に対して , または が成立つ.このとき, の4彩色を求めよ. 制約: , (整数座標)
問題. Shortest Common Non-Subsequence '0' と '1' からなる2つの文字列 が与えられる. と のどちらの部分文字列でもない '0' と '1' からなる文字列で最小の長さのものを求めよ.ただし,答えが複数ある場合は辞書順で最小のものを求めよ.制約:
問題. What Goes Up Must Come Down 非負整数列 が与えられる. の隣り合う2要素を交換するという操作を繰り返して を山型にしたい.ただし,数列 が山型であるとは,ある要素 が存在して, となることである.数列 を山型にするための交換回数の最小値を求…
問題. Arithmetic Progressions 非負整数からなる集合 が与えられる. の部分集合で等差数列となるものの中で要素数最大のものを見つけ,その要素数を答えよ.制約: ,
問題. 全チームによるプレーオフ チームで引き分けのない総当たり戦を行う. 試合の結果が確定しているときに,残りのすべての試合を行い,すべてのチームの勝利数が等しくなる試合結果(プレーオフ)の組合せ数を求めよ.制約: ,
問題. Parallel Lines 2次元平面上に 個の点がある.どの点もちょうど1つの対に含まれるように,すべての点から 個の対を作ることを考える.ここで,各対を対に含まれる2点を通る直線として考えると,いくつかの平行な直線に分割される.その分割の各部分の…
問題. Secret of Chocolate Poles 厚さが1cmの白と黒の薄いチョコレートと,厚さが cmの黒の厚いチョコレートの3種類がある.高さ cm 以内で黒色と白色が交互に配置されるチョコレートの積み重ね方が何通りあるか求めよ.ただし,一番下と一番上の色は黒とす…
問題. プレゼント交換会 頂点 辺の無向グラフ が与えられる.入次数の最大値と最小値の差が小さくなるような各辺の向き付けを求めよ.最適解が複数ある場合は入次数の最小値が大きいものを選ぶとする.制約: ,
問題. 文字解読 2値画像が2つ与えられる.2つの画像が同じ文字を表しているか判定せよ.画像の白のピクセルは4近傍,黒のピクセルは8近傍で連結しており画像範囲外のピクセルは白とする.画像は各連結成分の包含関係で1つの文字を表す.2つの画像の連結成分…
問題. 3Dプリント 3次元空間に 個の同じ大きさで同じ向きの立方体の配置候補が与えられるので,その中からちょうど 個選び立方体を連結で表面積が最小となるように配置せよ.配置候補の各立方体は3個以上とは重ならず,3個以上の立方体が共有点を持つことは…
問題. Cleaning Robot サイズが横幅 ・縦幅 の部屋がある.部屋のタイル上に1つの掃除ロボットといくつかの障害物が置かれており,各タイルは綺麗か汚れている.掃除ロボットは上下左右の障害物の無いタイルへ移動することができる.すべてのタイルを綺麗に…
問題. カードゲーム 1より大きい整数が1つ書かれた 枚の青いカードと 枚の赤いカードが場にある.青いカードと赤いカードのペアが1より大きい共通の約数があるとき場からペアを取り除くことができる.最大何組のカードを場から取り除けるかを求めよ.制約: …
問題. 離散的速度 単純無向グラフ とスタートとゴールの頂点 が与えられる.また,辺 には制限速度 と距離 が与えられている. から まで最小の時間で移動したい.ただし,各頂点では速度を1, 0, -1 だけ増加することができ,各移動する辺では制限速度を守り…
問題. ダルマ落とし 正整数 が与えられる.隣り合う2要素で値の差の絶対値が1以下ならばその2要素を取り除くことができる.最大でいくつの要素を取り除くことができるかを求めよ.制約: ,
問題. 竹の花 種をまいてから 年周期で花を咲かす竹のことを 年竹と呼ぶ.今, 個のすべての区画のそれぞれに 年以上の周期の竹の種を1つまくことを考える.この時, 年以降できるだけ長い期間どこかの区画で花が咲くような種の植え方を考え,そのような植え…
問題. 当選者を探せ! 最も多くの票を獲得した候補者が次期委員長に選出される.選挙の開票を一票ずつ行っていくときに,当選者が確定するところと当選者を求めよ.もし,当選者が確定しない場合は"TIE"と表示せよ.制約:
問題. 被験者の選定 n人の学生の得点が与えられる.得点の差の絶対値が最小となる2人を選び,その値を答えよ. 制約: ,