250 入力文字列を空白で単語に切る。単語中の母音のうち、両側に子音が存在するものを削除した結果を答えよ、という問題。 子音は隣接している必要はないが、単語内で右側と左側に存在する必要がある。実装するだけ。 500 ドミノを並べることを考える。最初…

300 N個の物体のうちK個を一か所に集めるとき、マンハッタン距離で必要な最小移動距離を求めよ、という問題。 どれかのx座標とどれかのy座標にまとめるのを全部試すだけ。300なのは点差をつけるための措置？ 500 NxNのボードで、x方向ないしy方向に1マス必ず…

全然ダメな日。明日は頑張ろう...。 250 文字列中のアルファベットの出現頻度から、一番類似度の高い文字列を選べ、という問題。 いわゆる精度問題。頻度計算を各文字についてやる時に、割り算を最後に回しましょう、ということ。あるいは簡易分数クラスでも…

350 長さNのテーブルに団体客が連続した領域になるように着席する。団体の大きさと確率が与えられ、それに応じて客が訪れる。客は着席可能な任意の場所に等確率で着席する。このとき、最初に座れない団体が発生したときの、テーブル占有数の期待値を求めよ、…

ある整数Nが与えられるので、A+B=Nを満たすAとBについて、BがAから任意の一文字取り除いたものを、Aが小さい順に答えよ、という問題。 どの桁を飛ばすかで、その桁より右は2倍だし左は11倍。候補が二回カウントされていたり、文字列で順番出していたり、答え…

DP大好きなセット？ 250 入力文字列の先頭の文字を中央に置き、2文字目をその文字の上下左右に配置し、3文字目を2文字目の上下左右のうち何も置かれていない場所に置く。以下同様に繰り返していった結果できる配置の中央から、一番外側までの文字を上下左右…

1000 どうも最大値として使う区間と、それに対応する最小値から、N-1個の分割が可能かどうかの判定がまずかったっぽい。 いくつ分割が可能か、という情報ではなく、上限と下限を持つようにしていたのが問題。(後述) 問題は、全部の値について可能かどうか判…

300 椅子取りゲームで負けるプレイヤーを答えよ、という問題。 一番近い椅子が一番遠いプレイヤーが必ず負ける、という注釈が書いてあるので、それに従って実装するのみ。検証できていないけれど...。一番近い椅子に順次割り当てを行っていって、最後に残っ…

凄くつまらないセットのような...。 250 PIのN桁目を四捨五入して答えよ、という問題。 Nは高々25程度なので、適当にやるだけ。二桁以上の繰り上がりは1回しか起こらないので、そこだけ例外処理してしまってもいいのかも。(そもそも25要素の配列を適当にコピ…

300 トランプのサブセットが与えられ、その中からN枚取り出すとき、一番多いスートの枚数の期待値を答えよ、という問題。 各パターンの確率をDPで求めて、N枚になる確率と、その時一番多いスートの枚数から期待値を計算すれば良い。 500 ダイヤル式のカギを…

自分が最初に参加したSRMが322で、これが100回目のSRMのようです。4連続でレートが上がった後は必ず落ちていたけれど、今回も上昇。いい加減高所恐怖症...。 250 サッカーの試合を5分刻みで見て、それぞれのチームが各5分に点を取る確率が与えられる。(5分間…

SRM前の練習。こういうことやると、これの日付変更アルゴリズム(次の日リンクが出ない)と競合するんだけど...。 300 N人の人が輪になって並ぶ時、隣接する二人の身長差の最大値の、最小値を求めよ、という問題。 取り敢えずN人をソートする。一番小さい人の…

これのログアウトのタイミングがかなり謎。 250 素数Pが与えられた時に、A^K=1(modP)なる最小の正整数KがP-1であるAをすべて求めよ、という問題。 Pが高々1000なので、全部試せばおしまい。(問題文を簡潔に書こうとしたら用語を知らないことに気付いたので、…

面倒くさいセット。かなり実装するだけの感が強い。 250 N行M列に並べられたカードを左上から縦方向に回収し、横方向に並べていくという操作を繰り返す。あるカードが1回目の操作の時にはK[1]列にあり、...i回目の操作の時にはK[i]列にある時、操作終了後に…

250 ユーザと閲覧可能な要素が与えられる。あるデータが複数の要素からなるとき、そのデータの各要素に対して閲覧可能なユーザのみ、そのデータを見ることができるとする。閲覧可能なユーザリストを答えよ、という問題。 愚直に実装するだけ。 500 0から9と…

自分の分不相応にレートが上がっているような気がしますが...。そもそも1000点問題が全然解けていないのにレートが上がっている時点で、近いうちにさっくり落ちるとは思いつつ。 250 一次元上で並んでいるN個の点の座標と質量が与えられるので、重力的に釣り…

高速化のためのトリックのつもりが、低速化につながるケースもあるので、メモ付き探索では注意が必要？ 250 N回の乗継で目的地を目指すとき、最速で目的地に着くときの時間を答えよ、という問題。各乗継に、可能な開始時刻と終了時刻が与えられる。 各乗継で…

普通に考えたら、もっと効率の良い方法があったので、メモ。 1000 同一直線状にある線分をできるだけマージしてから、任意の三本を選んで交点が三つできるものの組を数えれば良さそう。

250 グラフ3つの連結成分が与えられるので、連結成分を一つに統合するための最小コストを答えよ、という問題。 各連結成分間での最小コスト(3つ)を計算して、一番大きいの以外を使えば良い。 500 N本の同じ長さの棒を使って、7セグ表示で表現できない最小の…

101回目のレート変動で赤くなりました。黄色の連続は100回で終了。まぁ、次回には黄色くなるわけですが。 250 カードの山がいくつかある。各山から一枚ずつ取って、新しい山を作るとき、状態のループ長を答えよ、という問題。 シミュレーション問題。50回と…

特殊な知識は必要としないスタンダードなセット。BFSは使うけど。 200 使用した回数で出力する文字が決まっている機械が複数ある。連続使用回数と機械の番号が与えられるので、出力される文字列全体を答えよ、という問題。 単純にシミュレーションするだけ。…