プログラマ失格ですねこれは。それにしても点数の付け方がおかしい。(一般的にこう点数配分するのが正しいという状況で、相対的に普段よりも簡単とされるものに全く手が出ないのが何よりも問題。) 250 AからBまでの素数をNで割った余りとして一番多いものを…

幾何は何度やっても早くプログラムできるような気がしません。汎用ライブラリを作る能力でもあればいいのかなぁ？ 250 ある円の半径の2乗が与えられるので、円弧上にある格子点の数を求めよ、という問題。 ピタゴラスの定理を使って全探索するだけ。 500 1分…

スコアの決定アルゴリズムがよく分からない...。 250 整数配列が与えられるので、任意の隣接する二つの要素をマージしていくという操作を行い、先頭から見たときと末尾から見たときで同じ配列になるように変形する。このマージ作業の必要最小回数を答えよ、…

英語力は最大のプログラミング能力のようです。問題やたらと長いし...。 250 ローン残高と、月々の支払額と、残り期限が与えられるので、利率を求めよ、という問題。 利率をバイナリサーチ。利率が実際よりも少ないと支払いを行うと途中で値が負になるし、多…

250 ランダムに上下左右に移動するロボットが、同じマスを通らずにN歩移動できる確率を求めよ、という問題。 上下左右のうち、まだ到達していない場所について探索を続けるDFSを回せば良い。全部のパスを計算してから同じマスを通っていないか確認するのはダ…

300 直前の5個の値を使って、次の値を予測するという方式のうち、最近N個のデータに適用した際の差分が最小のものの差分を答えよ、という問題。 可能な予測方式すべてについて計算するだけ。 450 各瞬間のある商品の売値と買値が提示される。それぞれの瞬間…

今までで一番簡単な問題セット、のような気がする。 250 27個の数字を使って、3x3x3の立方体を作成する。高々1回だけ任意の二つの数字をスワップして良いとき、三つの連続する数字(斜めは含まない)の合計の最大値と最小値の差分の最小値を求めよ、という問題…

250 三つの文字列集合が与えられるので、それぞれについて、他のどの集合にも入っていない文字列には3点、他のどれかに含まれるものには2点、他の両方に含まれるものは1点として、スコアを計算せよ、という問題。 実装あるのみ。 600 N以下の整数について、…

250 文字列Aが文字列Bから任意の文字を削ってできるとき、削られた文字を答えよ、という問題。 結果はユニークになるように制限されているらしいので、Aの文字を順番に試せば良い。 500 両隣がなるべく空いている状態で場所を選択するルーチンの人が順次やっ…

情けないミスで、簡単な問題を落とした感じ...。まぁ仕方ない...。INFはできるだけでっかく取りましょう。 250 各桁の積がNになる整数のうち最小のものの桁数を答えよ、という問題。 9から順に割っていって桁を追加していけばいいみたい。なんとでもできるけ…

250 文字の出現頻度から、暗号を解読せよ、という問題。同じ頻度の場合はアルファベット順。 やや面倒な実装系。 500 2次元盤面上をアルファベット順に縦横斜のいずれかに移動する。Aから始まってN文字移動できるパスは何通りあるか答えよ、という問題。 各…

問題をちゃんと読みましょう。 250 整数Nの各桁を並び替えてできる整数の総和を、重複するものを2度数えないようにして求めよ、という問題。 まさにC++のnext_permutationを使いましょうという問題。普通に実装してもすぐ終わるようにNは100000以下になって…

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 同一直線状にある線分をできるだけマージしてから、任意の三本を選んで交点が三つできるものの組を数えれば良さそう。