頭悪いって次元を超越してた...。 250 整数配列が与えられる。現在の値が与えられて、整数配列の要素を順番に足すか引くかしていく。引いたときに負になったら0にする。2200以上の値に二回続けてならないようにしながら、2200以上である状態とそうでない状態…

250 たくさん箱があって、それぞれの箱の中には二種類のものが入っている。全部の箱からK個ずつ取り出したときに、二種類のものがどういう分布になるか、可能なパターンの総数を答えよ、という問題。 全部のKについてループ。各箱から一方の種類を取り出すと…

250 整数配列が与えられるので、ORして目的の値にできなくなるようにいくつか除去したい。除去する最小の個数を答えよ、という問題。 取り敢えずORすると目的の値の関係ないビットが立つヤツは無視して、目的の値の各ビットについて、いくつの要素が立ってい…

全探索すら書けない。 250 A^Bを以下の操作で作るときの最小回数を答えよ、という問題。素数をかけるまたは自分の約数のどれかをかける。 取り敢えず素数を一通りかけた状態を考えてやって、後は必要な回数だけべき乗していくようなイメージ。必要数を上回る…

グリーディセット？ 250 ナップザック問題。袋が300までで、荷物が100以上300以下という状況。何袋か、という問題。 100以外のヤツラは高々2個までしか入らないというのをうまく使う。100のヤツラを3個詰めることができるけれど、実はそれは余ったときの選択…

釣り掘り。 250 文字列Aに対して、任意の位置の文字を先頭に移動させる、という操作を繰り返して文字列Bを作りたい。少なくとも何回の操作が必要か答えよ、という問題。 取り敢えず先頭にどんどん文字が入っていくということは、確定させるには後ろから、と…

なんか算数っぽいセットだった。 250 ある要素を+1する操作または、全部の要素を二倍にする操作を行って、目的の配列を作るときの操作回数の最小値を答えよ、という問題。 取り敢えず、目的の配列の奇数要素は+1でしか作れないので、それ戻して、全部偶数に…

最近全然ダメ。最初からかもだけど。 250 区間に2色の色のどっちかを付けるという操作をやった結果、何通りの色付けが可能か答えよ、という問題。 自分が塗った部分が最後まで残っているかどうかを考えるだけ。 500 文字列中にある文字が連続する箇所がK個以…

世間的には簡単なセットだったようで、難易度的には割りと微妙な雰囲気。 250 整数配列があって、その比率を維持した状態の部分配列が二つ与えられる。元の整数配列の要素数の最小値を答えよ、という問題。 要は最大の共通部分列を求めてやって、両方の和か…

時間足りないのは純粋に頭悪いから。 250 六角形グリッドの適当な点に色を塗っていく。隣接する点には同じ色にならないように指定されたマスを塗るとき、最低何色必要か答えよ、という問題。 3色あれば十分なので、それより少なくできるか調べる。2色でDFSす…

難易度詐欺。点数と英語によるトリック。 300 与えられた順番にボールを並べていく。ボールは一列になるように置き、置いたときに、右側にあるボール群の色の数と、左側のそれの合計値が得点になる。このとき可能な最高得点を答えよ、という問題。 左側と右…

平常心を失った状態で行動してはいけない...。そろそろレートちまちま稼ぐ生活にしようかなぁ...。上を見るのは諦めて。 275 木の根からの距離ごとにいくつ点があるか与えられるので、可能な木のうち、二つのノード間の距離が最大になるようなものの最大値を…

250 右にしか移動できないRと左にしか移動できないLの初期配置が与えられる。お互い乗り越えることはできないとして、目的の盤面を達成できるか答えよ、という問題。 頭から順番に見てって、Rが少なかったりLが多かったりしたらダメ。LとRの出てくる順番が違…

ゆとり仕様かと思ったらライブラリゲー。 250 文字列中のある文字を全部特定の別の文字に置き換えるという操作を繰り返して、回文にしたい。置き換えが発生する延べ文字数の最小値を答えよ、という問題。 結局二回置き換えする理由はどこにもないので、置き…

難易度バランスおかしい。 250 N個のものからできるだけたくさんのものを選びたい。選ぶコストはそれぞれのコストと、それぞれの間の移動コストで決まる。指定された範囲のコストで最大いくつ選べるか答えよ、という問題。 両端を全ペア選んで中身をコスト小…

忙しくて悲惨...。 250 Nステップあって、i番目のステップではiメートル進むか何もしないかを選択する。このとき、立ち止まってはいけない位置が一箇所だけ与えられるので、一番遠くまで行くときどこまで行けるか答えよ、という問題。 取り敢えず進めるだけ…

やれることはやったのでまぁ仕方ないという気分。(いつまでもそのままじゃダメだけども。) 250 折れ線グラフが与えられるので、x軸に平行な直線と交わる回数の最大値を答えよ、という問題。 当然、折れ線の一部がx軸に平行だったら無限に交わる。それ以外の…

異常に頭悪いことが分かった。(分かってた。) 250 完全二分木が与えられる。同じ頂点を複数回通らないように、二頂点間を結ぶパスで全体をカバーしたい。最小でいくつのパスが必要か答えよ、という問題。 今の根が終端なパスがあるかないかで分岐して、木の…

すっかり忘れ去ってた...。 250 N人の人がいて、各二人の財産の差額がD以内であるかどうかの関係が与えられる。このとき、財産の差額の最大値を答えよ、という問題。 要はある人から別の人への最短距離の最大値を求めよという問題。全部やるだけ。 600 見て…

かなり簡単な問題だったのに、解けなかったのでどうしようもない。 250 見てない。 500 木の枝を目的の状態になるようにフリップしたい。始点と終点を決めて、そのパス上の枝をフリップする操作を最低何回やる必要があるか答えよ、という問題。 一つの枝を二…

解けるようにならないといけない問題に見えた。 250 各人の能力と、タスクの難易度と量が与えられるので、できるだけ一番タスク量の多い人のタスクを最小化するように分割するときの、その値を答えよ、という問題。 バイナリサーチしてください、と書いてあ…

メモ忘れ...。 250 連続するNマスにどのようにモノが配置されているかが与えられる。連続するKマスにいくつモノが配置されているかの情報が与えられるが、どの位置のものかは分からない。同じ区間についての情報が複数ないことと、全体として正しい情報が与…

まじめにやらないとダメ...。 250 区間グラフが与えられるので、二点を選んでできるだけ多くの区間をカバーせよという問題。 区間の両端を全パターン試すだけ。 600 N人の友人関係が区間グラフの交わりで与えられる。全員が全員に情報をブロードキャストした…

解けないとダメだったと思う。思うだけ。 250 N個の文字列を作成することを考える。今までに現れた任意の文字列に2ステップでアクセスでき、文字列の末尾に文字を足すには1ステップ必要で、文字列をコミットするにも1ステップ必要。最短作業ステップ数を答え…

TCOの悪意に満ちた問題。 250 友達関係が与えられる。友達の友達と友達になることができるとき、ある人と友達になるのにかかるステップ数はいくらか答えよ、という問題。(これに関してはほとんど問題文を端折っていない。) 距離-1じゃなくて、相手側も最適に…

実装と数学。 250 ある文字列が周期K以下の周期的な文字列になるように書き換えたい。最小の書き換え文字数を答えよ、という問題。 周期全部について調べる。周期が決まれば、最初の数文字を拾って、周期ごとに文字数カウントをして、全文字数から最大出現文…

TLEした。 250 二次元盤面上に二種類のものが置いてある。ものが置いてある状況が与えられる。マンハッタン距離でD以下の位置にあるものは同じものであるとして、二種類のものの配置として可能なものは何通りあるか答えよ、という問題。 UnionFindしましょう…

まだまだいけそう。 250 二次元盤面上を目的地に向かって移動することを考える。上下左右の移動コストと斜め四方向の移動コストが与えられるので、最小コストを答えよ、という問題。 取り敢えず目的地の座標のXとYの合計値が奇数なら、少なくとも一度は上下…

おもしろくなかった。 250 N人をK個の部屋に得点順に分ける。K人ずつ拾って、ランダムにアサイン。自分がいる部屋の得点の平均点の期待値を答えよ、という問題。 実装やりましょうって問題。自分がいる部屋の人数が固定か否かで分岐。固定なら、自分以外のラ…

完敗...。 250 3種類の木をそれぞれの種類ごとに直線状に等間隔に木を植えたい。座標が整数になるように並べるとき、種類に関係なく一番近くにある木の距離の可能な最大値を答えよ、という問題。 ある二種類の木の距離が一箇所決まると、その二種類の木の最…