今年最後のSRMなんだけど、結局いまいちな結果に終わってしまった。 250 一直線上に木が立っているので、木の一番上の点が同一直線状に乗るように木を削るとき、少なくとも何本削らないとダメか答えよ、という問題。 直線として考えられるのは元の木のうちの…

2章付近 クロスフリーとかラミナーとか後の方で使うっぽい話がされているけど、良く分からないので保留。木構造で表現できるのがクロスフリーで、DAGっぽくなるとクロスしちゃってるってことなんだろう、多分。(くらいのいい加減な認識。) 強連結成分の取得…

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

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

取り敢えずこの本には読書タグをつけておいたらしい。別のタグにしときゃいいけど、多分そんなに本なんて読まないしメモしない。 アウトラインというよりは、大事そうなところだけ拾い読みしてるっぽい雰囲気を出しつつメモ。(一応全部読んではいるけど、理…

250 1からNまでの数字を高々1度だけ使って、サイコロを作る。向かい合う面の値の和が等しく、かつK以上にする方法は何通りあるか、という問題。 和を決めると、数字のペアが何通りあるか分かるので、3つ取り出す。後はそれをサイコロにするので2倍するだけ。…

250 Mの倍数すべてについて、それより以上で最小なNの倍数との差分の期待値を答えよ、という問題。 GCDを見てやれば、Nで割ったときの余りとして出現するものが分かり、それがループするので平均するだけ。 550 見てないけど実装系だったらしい。 1000 無限…

300が難し過ぎて1000を開く時間がなかったセット...。なんとも...。 300 任意の整数配列が与えられたときに、任意の二個の要素を取り出し、その結果から決まる特定の要素を一つ挿入するという処理を繰り返したとき、操作の順序によらずそれぞれの配列につい…

難易度設定が謎なセットが続いているような気もします。 250 N人の既に知っている人と、M人の知らない人がいる状況で、ランダムに2人選んで情報を伝えるという作業をする。このとき、全員に情報が伝わるのにかかるステップ数の期待値を答えよ、という問題。 …

久し振り過ぎたので、ほとんど検証しないでサクサク投げたら、サクサク落ちた日。 250 長さNの配列から、i番目とi+K番目を取り除く、という操作をできるだけ多くやって、取り除いた要素の値の合計を最大にしたい、という問題。 法Kごとにグループ分けして、…

幾何はライブラリが必要なので困る。 300 整数Xが与えられたときに、X*X、X+X、X-X、X/X、のいずれかにXを置き換えることができる。このとき、できるだけ少ない置換回数で、目的の整数Yにする方法を答えよ、という問題。複数ある場合は辞書順で最初のものを…

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

なんかテストランが間違ってたセット。 250 等差数列に対して、偶数を2で割り続けた結果の数列が与えられるので、元の数列を復元せよ、という問題。 先頭二つを全パターン試して、問題がないかチェックするだけ。 500 見てない。 1000 凸包が二つ与えられる…

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

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

550 スタックに4種類のものを詰め込む。上のL個が同じ種類のものだった場合には、L個まとめて取り出すことができるとする。このとき、N個のものを詰め込むときに、最終的に全部取り出せるようなパターンは何通りあるか答えよ、という問題。 取り敢えず、全部…

250 整数xの各桁の数字を足したときの和をs(x)とするとき、s(x)*s(x)=s(x*x)なるxはいくつあるか求めよ、という問題。 キャリーが出るとおかしくなるらしいので、各桁の数字が3以下のものについて全探索するだけらしい。x*xの上限が10^18程度なので、xの各桁…

相変わらず900が解けない日々。1000よりも常に難しい気もしている。 250 1より小さい実数の、小数点以下6桁までの精度で値が与えられる。このとき切り捨てを行うとして、字面上一番似ている分数を答えよ、という問題。 分母は高々1000なので、全部試すだけ。…

今回からDiv.1だそうで。(実際にはDiv.2の大会に参加できないという制約があるだけだけど。) A 整数A,B,Nが与えられるので、A*X^N=Bなる整数Xが存在すれば、それを答えよ、という問題。 Xの絶対値はBの絶対値以下であることと、Xをかけていく過程で絶対値が…

あんまりいい問題セットだとは思えなかった。 250 整数配列から、一つおきに取る、残りから二つおきに取る、残りから三つおきに取る、を繰り返したときに最後に取ることになる値を答えよ、という問題。 愚直にシミュレーションするだけというひどい問題...。…

もっとまじめにやりましょう、って感じだった。 A 既に使った値を覚えておいて、使っていない最小の値を教えてくれるマシンがある。使った値のリストが与えられるとき、そのマシンに問い合わせた結果を答えよ、という問題。 やるだけ。 B N人の人が総当たり…

かなり嫌いな落とし穴に毎回はまってる...。 250 ある問題の答えについて、Lie人に嘘を教えた状況で、N人のうちYes人がYesと聞いたと教えてくれた。実はLiar人が嘘をついたという状況で、もとの問題の答えはどっちだったか答えよ、という問題。曖昧か、矛盾…

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

変則セットはいいけど、Hardを難しくするなら出題する意味ないと思います。 250 キーワードリストが与えられるので、閾値以上の数だけ禁止ワードを含んでいたら、すべてを禁止ワードにする、というのを、キーワードリストの集合に対して適用する。最終的に禁…

英語がひどいセット。 250 一列に並んでいる全員に紅茶かコーヒーを配る必要があり、誰に何を配るかが指定されている。同時に運べる数は一方の種類のみで7個までで、移動時間は距離によって決まり、渡す時間は固定、飲み物は開始点に置かれており回収する時…

結果は変わらないとは思うけれど、もっといいコンディションでやりたかったセット。 250 ある整数Xについて4X+3また8X+7に変換する処理をするとき、法Mの世界で0になるのは何ステップ目か、という問題。 かなり状態が合流するので、何も考えずにBFSで通った…

グラフセット。別名ライブラリゲー。 250 海と陸が六角形を一つの単位として配置されている状況で、海岸線の長さを答えよ、という問題。 要は陸と海が接している数を答えよという問題なので、6方向調べる。 500 整数配列が与えられるので、平方数の和が平方…

手が遅いです...。気付くのも遅かったけど。 250 ペットを飼いたいが、個体ごとの飼育コストが、現在のペット数でリニアに変化する。このとき与えられた予算で最大何匹飼えるか、という問題。 K匹飼うときのコストをソートして小さい方からK個拾う、というの…

解けたけど、解けていないセット...。 250 直方体が二つ与えられるが、一部くっついている場所がある可能性がある。このとき全体の体積を求めよ、という問題。 何も考えずに全部の座標をチェックして、二回目なら無視するという処理をするだけ。 500 N地点あ…

昔のセットを解く作業...。点数とクオリティが今とはマッチしていない感じ。 300 同じ大きさのバイナリ行列が二つ与えられる。3x3の領域について値を反転させる作業を行って、二つの行列を一致させるとき、必要な最小反転数を答えよ、という問題。 要は左上…