ひどい負け方をした...。問題自体は簡単なセットです。 250 対象な隣接行列が与えられるので、0の地点から開始して、一筆書きできるかどうか判定せよ、という問題。 要は連結かどうか判定する問題です。BFSなりDFSなりお好きな方をどうぞ...。BFSするときはq…

要求された金額を超えないように、手持ちのお金を支払うとき、支払える最大金額を答えよ、という問題。 要求金額は100K程度で、通貨の種類が10程度、通貨の枚数は1000程度。普通にDPをやると多分TLEするので工夫が必要。K種類の通貨で実現できる金額がすべて…

N地点についてそれぞれの間の距離が与えられるので、すべてが連結されるようにできるだけ小さいコストでつなぐときの最小距離を求めよ、という問題。 典型的なMSTなのでプリムなりクラスカルなり...。

追記の追記 やっぱりO(N)でできます。ただし、N+1じゃなくてN+7になります。なぜ6個増えたかというと、常に0を出力する1入力の回路が6ゲートかかるからです。実装上の都合により、常に2を出力する回路を7ゲートで作成する方が、N個必要という部分が分かりや…

色々な問題の集合のコンテストなので、とても一人では参加できる能力もないし、他の人が大半やっているのですが、取り敢えず一部の問題だけ比較的に良いものができたのでメモしておきます。 部分問題 0#という名前の2入力2出力のゲートを使って、特定の出力…

タイトルの付け方の規則を忘れた...。 250 二つの文字列が与えられるので、各文字について、前後の文字に書き換える処理をできるだけ少ない回数することで、同じ文字列に変形せよ、という問題。 基本的には小さい文字に合わせるわけだけれど、aとzがつながっ…

難易度が大分低下した感じのセット。 250 直進、向きを変える(左右)、という命令の列が与えられる。このシーケンスを延々と繰り返すとき、無限に遠くまで行くかどうかを答えよ、という問題。 取り敢えず一つのシーケンスが終わったときに、同じ向きのままで…

D 10進数表記で合計がNになるように、B進数の整数の和に分割することを考える。このとき、各桁に同じ数が出現しないような整数の和に分割する方法は何通りあるか答えよ、という問題。 この手の問題は基本的に上から決めるか下から決めるか、のどっちか。キャ…

A 線形合同法で生成した乱数列が部分的に与えられるので、次に出てくる数を答えよ、という問題。乱数は法Pで生成され、Pの桁数Dが与えられる。 決めないといけない変数が二つあるので、要素数が3つないと決定できないことがある。3つの乱数X->Y->Zという列が…

C 直線状にお店を配置することを考える。現在の座標とその位置に置ける店舗数が与えられるので、同じ場所にある二つの店舗について一つを左に、もう一つを右に移動させる、という処理を繰り返すことで、どの座標にも高々一つしかないようにしたい。このとき…

B N種類の大きさの板を使って、長さLになるように積み上げたい。どの板も好きなだけ使って良いが、全部で使う枚数を最小にしたいので、その最小枚数を答えよ、という問題。 Lが十分大きいので、最終的には一番大きいのをできるだけ多く使うことになる。これ…

AからBに流せる水の量、という形でグラフが与えられるので、始点から終点まで流せる最大流を求めよ、という問題。 まさに最大流を実装しましょうという問題。せっかくなのでDFSでやったらダメでBFSにしたら通った。

0からN-1の数を均等に生成する乱数生成器を二つ使ってXORしたときの結果の期待値を答えよ、という問題。 各ビットについて独立に計算するだけ。1になる確率と0になる確率からXORして1になる確率が計算できる。

整数配列が与えられて、すべての要素を1ずつ減らすことができ、一つの要素だけK減らすことができる。このとき、すべての要素を0以下にするのにかかる最小ステップ数を答えよ、という問題。 ステップ数を決めれば、それで0以下にならない要素をKずつ減らす回…

N個の回転運動をする物体があり、それぞれが一周する時間が与えられる。すべての物体が回転中心を含む同一直線状に並んでから、次にそうなるまでの周期を求めよ、という問題。 どの二個をとってみても半周の倍数だけ差がつけば良いので、逆数の差分がいずれ…

整数BとNが与えられるので、A^NがBに一番近くなるような整数Aを求めよ、という問題。 Bがかなり小さいので探索しても終わる。大きい場合は概数に対してpowとか使うのが妥当？複数の解があり得る状況なので、気を付ける必要がありそうだけれど、そういうケー…

整数配列が与えられるので、合計値がK以上になる最短部分配列の長さを答えよ、という問題。 大きい配列の部分和をやるときの常套手段というか、もっと大きい問題の部分問題として良く出てくる問題。ライブラリ化するほどのものでもないので、いざというとき…

格子点上の点がいくつか与えられ、幅Dで格子をその上に書くとき、通過する最小の点数を答えよ、という問題。 法Dで考えれば良くて、x軸方向の分布、y軸方向の分布、x軸とy軸の両方を決めた時の分布、というものをそれぞれの点の座標から計算しておく。後は一…

.を最後に一つだけ含む文字列について、全ローテーションを作成し、ソートした結果の最後の一文字ずつがRLEで圧縮された形で与えられる。元の文字列を復元せよ、という問題。 与えられた入力において、何番目の文字か分かると、その次の文字がどれか分かる。…

5x5の整数配列が与えられるので、任意の初期位置から5回の上下左右の移動でできる6桁の整数は何通りあるか答えよ、という問題。 4倍ずつに増えていくけれど、大した量にならないので、実装あるのみ。

N個の整数列の中で、一番大きい素数を約数に持つものを答えよ、という問題。 実装するだけ。ちょっとエラトステネスの篩を書いてみたくなりました、というだけ。

1からTまでの数字について、それぞれを使える回数の上限値が与えられるので、A個以上B個以下の数字の集合を作る方法は何通りあるか答えよ、という問題。 単純にDPやるだけ。全部のテーブルを持っていると、メモリが足りなくなるので、直近だけ覚えておくよう…

重さと耐久力のペアからなる物体の配列が与えられるので、最大危険度が一番小さくなるように縦に積みたい。危険度は、上に乗っている重さの合計から耐久力を引いたものである。 まず、N個のものの一番下に入れるときよりも、それ以外の場所に入れる方がその…

底辺が同一直線上にある矩形が複数あり、それを重ね合わせた図形の上辺の形状が与えられる。このとき、与えられた図形は最小いくつの矩形からなるか答えよ、という問題。 上辺が今までよりも上にある場合には、そこに新規の矩形があると分かる。下にある場合…

一次元上のN点をすべて訪問することを考える。移動を開始してから各点に到達するまでの時間の合計値の最小値を答えよ、という問題。 取り敢えず、ある点と別の一点が指定されれば、その間に通過していない点はないはずなので、現在位置と、一番遠い通過済み…

900のときは600をやる方針。 250 整数から、4のべき乗を取り除く作業を交互にやって、最後に全部取った方が勝ちというゲームの勝者を判定せよ、という問題。 典型的なNimなので、どうやって相手をはめるか、というお話。4のべき乗は法5を見ると+1,-1しか取ら…

実装ゲー。ただし、いかにして実装を楽にするかゲーでもある。 A ひし形に並んだ整数配列が与えられるので、対称性を持つように要素を追加するとき、追加する最小数を求めよ、という問題。 実装ゲー。メモリケチって正方形にして云々、とかやっちゃダメ。 B …