問題リンク Online Quiz System 概要 オンラインクイズゲームシステムのシミュレートを行い、サーバとクライアント間のデータ通信量を答えよ。 プレイヤー数はM、問題数はNである。 クライアント側のプログラムは全て同じである。 全問題文は事前にダウンロ…

問題リンク ! 概要 整数NとN進数で表現された文字列Mが与えられる。N進数でM!を計算したとき、末尾に続く0の数を10進数で出力せよ。なお、10を超える整数はA〜Zで表現されるものとする。 8 M 解法 この問題の応用編になります。 まずNを素因数分解し、必要な…

問題リンク The Closest Circle 概要 N個の円が重なることなく散らばっている。円同士が最も近づいている場所の距離を求めよ。円同士の距離は、 中心間の距離−円1の半径−円2の半径 とする。なお、N個の円の中の半径の最小値をRとすると、全ての円の半径rはR …

問題リンク Hit and Blow 概要 Hit and Blowをする。今、N回の試行とその結果が分かっている。試行結果から、答えが1つに定まるならその答えを出力せよ。 そうでなければ新たに数xを試行する。試行し、その結果から解が一意に決まるならばそのxを答えよ。xが…

問題リンク Speed 概要 トランプの「スピード」をプレイするロボットA, Bがいる。このロボットたちの動作をシミュレートしてどちらが勝つかを判定せよ。 「スピード」は手札が4枚、場が2か所、デッキを使い、2人が向かい合って遊ぶ。場に出ている一番上のカ…

問題リンク Gather on the Clock 概要 N個の数字が円形にならんでいる。好きな数字Aを1つ選び、時計回りに1つ回った次の数字Bとの差の絶対値|A-B|が得点に加算される。この後、Bは円から無くなる。この操作を円に残った数字がただ1つになるまで続けたとき、…

問題リンク Area Separation 解法 直線を1本引くたびに面がいくつ増えたかを数えていきます。 直線を1本引いたら増える面の数は 境界線上でない場所で登場する交点の数 + 1 です。交点の数というのはユニークな交点の事を指し、複数の直線と同じ場所で重なっ…

問題リンク Divisor is the Conqueror 概要 1〜13の数字が書かれたカードをN枚持っている。 最初は手札のうち任意の1枚を場に出す。2枚目以降は、場に出ているカードの総和Sを割り切る数字が書かれたカードしか出せない。このルールの下でN枚のカード全てを…

問題リンク Private Teacher 概要 N人の学生と期間W(週間)が与えられる。学生にはtiの勉強量が必要であり、勉強できる曜日のリストが決まっている。 1日につき、学生1人だけに勉強を1教えることができる。 期間内に全ての学生に対して必要としている勉強を教…

問題リンク Petoris 概要 h*wのブロックと、H*Wのボードが与えられる。ブロックには1個以上のタイルが、ボードには0個以上のタイルがはまっている。ボードにブロックをはめ込み、全てがタイルで埋まった行の数が得点となる。得られる得点の最大値を答えよ。…

問題リンク Repeated Subsequences 概要 アルファベット大文字のみからなる文字列Sが与えられる。Sのlongest repeated subsequenceを求めよ。 Sのlongest repeated subsequenceとは、Sを2つの部分文字列FとRに分け、それらのLCSの内で、最も文字数が長いもの…

問題リンク Mysterious Dungeons 概要 W*Hのマップがある。人('@')と出口('>')が1つずつある。人は隣接する4マスへ移動できる。 アルファベット大文字は岩を表す。岩は消えている状態と消えていない状態の2つの状態を持つ。消えている状態ならば人はこのマス…

問題リンク Turn Left 概要 M個の交差点とN本の双方向道路がある。交差点にはそれぞれ名前Sがついており、座標(x, y)にある。 交差点srcとdestが与えられる。道路を走る際、右に曲がることはできない、Uターンもできない。この条件のもとで、srcからdestへ最…

問題リンク Black Force 概要 H*Wのグリッドで表される凹凸の土地が与えられる。(i, j)の高さはH(i,j)である。 ここに容量C以上の水を蓄えるダムを建てたい。グリッドの中からダムにするための土地を連続領域として選ぶ。連続領域とは、領域内の任意の2マス…

問題リンク Flame of Nucleus 概要 N個のドームと、M本の双方向の道がある。ドームにはそれぞれPi人の人と、Ki人収容可能なシェルターがある。M本の道はドームiとドームjを結んで通行にD日の時間がかかる。 L日後に核が落とされる。L日目より早くシェルター…

問題リンク Goofy Converter 概要 N, MとN個のLiが与えられる。全ての i (0 Li = Σ(i が成り立つような長さN+M-1の{0,1}ビット列Kが存在するか。存在するならばそれのうちいずれか1つを、無ければGoofyと答えよ。 1 1 0 解法 Kはつまり、インデックスiから始…

問題リンク Compress Files 概要 N個のファイルがあり、それぞれ、圧縮前のサイズBと圧縮後のサイズAが決まっている。作業領域の初期サイズはMである。 圧縮が済んでいないファイルの集合を選び、1つの圧縮ファイルにまとめることができる。この圧縮ファイル…

問題リンク Dance Dance Revolution 概要 DDRの譜面が与えられる。これが「自然な」譜面かどうかを判定せよ。「自然な」とは ・左足と右足が交互に出る ・同じ矢印が連続しない ・体は常に前を向く ・足が交差しない を満たすことをいう。 譜面の長さ 解法 …

問題リンク First Experience 概要 コンピュータのシミュレータの動きをシミュレートし、演算結果を表示せよ。 シミュレータはR1, R2, R3の3つのレジスタがある。 R1: 最も新しい演算結果が入っている R2: 最も新しい入力値が入っている R3: 入力された演算…

問題リンク Greedy, Greedy. 概要 N種類(c1, ... ,cN)の価値を持つ硬貨がある。この硬貨の群に対して以下の2点を調べよ。 1. 任意の金額をこれらのコインで表せる 2. 任意の金額を表すのに必要な最小枚数が常に貪欲的に求まる 1 0 解法 適当な金額の範囲[1, …

問題リンク International Party 概要 N個の言語が飛び交うパーティーがあり、M個のグループがある。i番目のグループはki個の言語だけ使うことができる。パーティー全体で使用できる言語を最も小さくし、なおかつ任意の2グループ間でおしゃべりができるよう…

問題リンク Tetrahedra 概要 N本の棒のうち、6本を選んで四面体を作ったとき、作ることのできる四面体の体積の最大値を答えよ。誤差は10^-6未満にせよ。 6 長さ 解法 全探索です。 棒を6本選んで(nC6)、四面体のどの辺に使うか(6!)の組み合わせになるので、…

問題リンク Restaurant 概要 レストランのコックの動きをシミュレーションせよ。 コックは1人しかいない。レストランにはN個のメニューがある。メニュー i を調理するのにtiの時間がかかる。 注文は先着したものが優先的に処理される。コックは作らなければ…

問題リンク Moduic Squares 概要 3*3のセルと1つのmoduic cellがある。これら10マスに1〜10の数字を1回ずつ当てはめる。 3*3の中の全ての列について(垂直、水平、対角)のそれぞれの総和がmoduic cellの値を法にして等しい時、パズルが完成する。 入力に盤面…

問題リンク Lying about Your Age 概要 新しい街に引っ越してきて、あなたは自分の年齢を他人に知られたくない。自分の真の年齢をM進数表現(2 入力に3つの整数A, B, Cが与えられる。真の年齢がAのときにBと主張したとする。このとき、真の年齢がCとなったと…

問題リンク Headstrong Student 概要 整数x, yが与えられる。x/yを計算した結果で、循環に入るまでの長さと循環の長さをそれぞれ答えよ。有限小数となるならば循環の長さは0とせよ。 1 解法 循環に陥るかどうかはx/yの計算途中ででてくる値を覚えておけば分…

問題リンク Everlasting...? 概要 2つの整数A, Bが与えられる。これらの整数のKey numberをKa, Kbとしたとき、Kb 2 解法 AとBを素因数分解してkey numberを計算するだけです。 ソース

問題リンク Reading a Chord 概要 M個のトーンからなる音がなるようなコードを全て列挙せよ。ただし、各トーンのオクターブの高さは考慮しなくてよい。 コードは図1にある通りである。 コードに任意のテンションをつけることができる。例えば、(-9)というテ…

問題リンク Sort the Panels 概要 N個の'W'と'B'からなるパネルの順列S, Tが与えられる。次のルールに従ってSをTへ変化させるのにかかるコストを最小化せよ。 機械が1台ある。機械は任意のパネルへ移動してマークをつける。続けてもう1か所別のパネルへ移動…

問題リンク Osaki 解法 イベント処理で解きました。 時刻の昇順でソートし、時刻が出発のものだったら電車の車両が増えるのでインクリメント、到着のものだったらデクリメントします。このシミュレート中の車両の最大値が答えです。また、出発の時刻と到着の…