問題 有向グラフが与えられる。開始点と終了点が与えられるので、最短距離またはその+1までのパスは何通りあるか答えよ、という問題。 解答例 まずダイクストラで、開始点からの最短距離を全部の点について求める。再度ダイクストラで、最短距離またはその+1…

明日に備えて肩慣らし。タグをPOJにしておくべきだったかも？ 問題 石がいくつかある。それぞれに重さと価値があって、二つのバケツに振り分ける。最初は一つ目のバケツに石を入れていき、D+1以上の重さになったらもう一つのバケツに入れていく。二つ目のバ…

比較的新しいところをやろうとして、解いた問題番号のmax付近から。2005年って新しくはないな...。 問題 行列に対して、上下反転・左右反転・90度刻みの回転・対角線で反転(2種類)といった操作列が与えられるので、最終的な結果を答えよ、という問題。 解法例…

A点からB点への移動コストが与えられるので、0番目の地点にN人の人がいて、それぞれ、1,2,...,N番目の地点に行って帰ってくるとき、最小のコストを求めよ、という問題。 行くだけのコストならダイクストラをやるだけ。帰ってくるコストについては、開始点が…

連結なグラフが与えられるので、各ノードを除去したときにいくつの連結成分に分かれるか答えよ、という問題。 全部試すだけの問題だった。ノード数が1000なので最悪ケースのときにTLEすると思うが、そんなケースは来ていない。問題はノード番号の付け方で、…

ある特定の1点から出ている辺に使える本数の制約があるときのMSTを計算せよ、という問題。 辺の選択を全パターン試す。ツリーにならないケースがあるのでちゃんと書く必要がある。

無向グラフが与えられるので、MSTのコストを求めたい。またMSTがユニークかどうか知りたい。という感じの問題。 MSTのコストはプリムでもクラスカルでもいいので適当に求めることができる。その後、使用した辺を一通り除去してみてもMSTのコストが変わらなけ…

二次元空間上に規則的に数字を並べるので、与えられた座標に相当する数字を答えよ、という問題。 規則が二つしかないので、それに応じた数字を答えるだけ。

滞在できる点の座標と、スタートとゴールが与えられる。二点間の距離が指定された長さ以下の時に移動できるとして、最小移動数を答えよ、という問題。 到達できるかどうかの判定をしつつ、BFSするだけ。結構重ためな感じも、Javaの3倍ルールの前では...。

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

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

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

円卓に偶数人の人が並んでいて、それぞれが飲み物の入ったグラスを持っている。手が他の組と交差しないように二人一組で乾杯を行うとき、同じ飲み物を持った組は最大でいくつ作れるか、という問題。 典型的なDPなので、何も考えずにやれば人数NについてN^3く…

100桁程度の整数が二つ与えられる。それらの整数の各桁にあらわれる数字の集合が等しい場合、それらをfriendとする。また、片方の整数の隣接する2つの桁の数字について、片方を+1し残りを-1した結果できる整数(先頭の0は除く)が、他方の整数とfriendであれば…

煽りにとっても弱いです。 2,3,5以外の素数を約数に持たない数のうち、最初の1500個を求めよ、という問題。 1から始めて、2,3,5倍したものをPriorityQueueのようなものに追加していくだけ。何も考えずにやるとint溢れするのでlongでやればいい。 別解募集中…

すべての硬貨の価値は任意の自分より小さい額の硬貨の価値で割り切れるとする。このとき、硬貨の価値と枚数が与えられるので、お釣りはないものとして、指定された額を何回まで支払えるか答えよ、という問題。 大きい額の硬貨から使うことを考える。お釣りが…

区間(0,1)にある分母が32767以下の既約分数が与えられるので、同じく分母が32767以下の既約分数で、一番近いものを答えよ、という問題。複数ある場合は一番小さいものを答える。 既約分数なので、分母が違う既約分数と一致することはない。また、おなじ分母…