年末なのでPKUやって終わることに。 1250 人のINとOUTの列が与えられる。N個のスペースがあって、INかOUTの時点ですいていれば利用できる。利用できなかった人数は何人か答えよ、という問題。 書いてある通り実装するだけ。(多分英語の方が難しい問題。) 125…

微妙なセット...。スタイル作るのが恐ろしく面倒だということが分かったので、フォントを無視するようにIEの設定をいじってみた。(他の人にやさしくないなぁ。) 250 3辺の長さが整数の三角形のうち、すべての辺がA以上B以下であるものの数を答えよ、という問…

結構いいセットのような気がする。600>>>1000なのはさておき。関係ないけどフォントがおかしいのでスタイル作るか...。 300 N個の点がある状況で、できるだけ多くの点が距離D以内にあるような直線を引くとき、その点数を答えよ、という問題。直線は任意の位…

250の早解きセット。 250 x軸に垂直に置いてある複数のものがある。貫通するレーザーをランダムに照射するとき、当たる数の期待値を答えよ、という問題。 衝突するレーザーの照射角度の最小値と最大値をそれぞれのものについて求めて、レーザーの照射可能範…

ちょっと時間が空いたので...。昔にランダムサンプルでやったセット。何も進歩していないのね...。それにしてもつまらないセット。 250 2x2のタイルを敷き詰めることを考える。2x2の領域が複数個あり、部分的にに1x1のタイルが置かれている。このときタイル…

考え方を変えないと話にならないフェーズには突入しているんだろうなぁ、と思う。取り敢えず守りに入る段階ではない。 250 使っていい数字が制限されている状態で、ある数の次の数を求めよ、という問題。使ってはいけない数を含むものや、0で始まるものは不…

インフレしてた分をちょっと返済。情けない結果ではあるが。安心して年越せないやこれ。 250 ある数Xと2進数で足し算を行った時に、キャリーが出ない数のうちK番目のものを答えよ、という問題。 適当にinf取ったらinfが小さ過ぎた。どうしようもない。下から…

250 '['と']'からなる文字列が入力として与えられるので、それらが対応を取れるように、先頭に'['を追加し、末尾に']'を追加せよ、という問題。 取り敢えず先頭から見ていって、']'が多いようなら先頭に'['を入れ、最後に余った'['の数だけ']'を入れればおし…

200 入力文字列のアルファベットについて、大文字と小文字が交互に並ぶように変換せよ、という問題。 大文字か小文字かの状態を覚えておいて、アルファベットならば適切な方に変換していくだけ。 575 N( 先頭から順番に数字を決めていく。既に使った数字と、…

これの1000もテンプレ的な問題のような気がする。SRMでは同じ解き方が連続する傾向にある気がする。 250 凸包が入力として与えられるので、角を一つずつ落としていくとき、最後に残る三角形の面積の最大値を答えよ、という問題。 回りくどく書いてあるけれど…

面倒なセット。自分が思った通りに実装するのは問題ないのだけれど、それが現実的な速度で動かなかったり、そもそも問題の要件を満たしていなかったり。 250 二つの配列が与えられた時、片方の配列からもう一方の配列に要素を移動することで、両方の配列の平…

250 ある品物がK個セットのとき価格Nとする。最低A個入手するのにかかる最小コストを求めよ、という問題。 ある個数入手するのに必要な最小価格についてDPする。最低A個なので、単価の安い大きなセットを購入することも考慮に入れて、少し余分にDPしつつ、A…

問題自体は簡単なセットのはず。250が一番難解だった。 250 高々100x100の二次元文字列が与えられる。その内部に部分的に矩形を全通り取り出して、それに含まれる文字を種類ごとにカウントする。最終的に各文字は何回カウントされるか、という問題。 何も考…

難易度的にはかなりやさしめ。1000は典型的な問題だろうなぁ。 250 整数配列に対して、先頭から二つずつ要素を取り、その和の配列とその差の配列を作る。和の配列について、先頭から二つずつ要素を取り、その和の配列とその和の配列を作る。以下和の配列につ…

500>>>1000のセット。というか1000は知っていれば一瞬。このセットの500はアルゴリズム的に目新しいことは特にないかも知れないけれど、プログラマ的にはいかに綺麗に(結果的に正確に)解けるかが重要な問題だと思う。やっておいて損はない。(プログラマ的に…

実装系セット。 250 丸い物を積むことを考える。下に何もなければ落ちる。そうでないなら、右下に何もなければそちらに落ちる。さらにそうでなければ左下に何もなければ落ちる。このとき、積むx座標が順番に与えられるので、最終的にどういう形状に積まれる…

500>>>1000というか1000のどこが難しいのか分からないままに通ってしまったセット。全然吟味していないけど。どうでもいいけど、一通りやり終えると250の内容を忘れてしまうのはいかがかと...。 250 N( N!通り整数を作ってみて、それぞれ約数の数をカウント…

250 整数配列の各要素を0にすることを考える。一度の操作で一つの要素から高々Nだけ減算することができる。一回の操作のコストを、0でない要素に対応する値の合計とするとき、最小コストを答えよ、という問題。 要素数が10なので10!試すだけ。 500 チェスの…

集中してやらないとダメだなぁ、という感じ。取り敢えず投げてみる、というやり方はやめにした方が良さそう。 300 個人の上位のスコアが公開されていて、各チーム4人のとき、チーム間での順位の可能な最大値と最小値を答えよ、という問題。公開されていない…

簡単なDPが書けなかった...。 250 ?は任意一文字を意味し、*は0文字以上の任意の文字列を意味する。このとき、ある文字列と等価な最短文字列のうち、辞書順で先頭のものを答えよ、という問題。 ?*は*?と等価なので置き換え、**は*と等価なので置き換える、と…

やっとこさ行列乗算で解くべき(？)問題で正解にたどりつきました。 250 ある文字列のpermutationのうち、同じ文字が隣接しないものの数を答えよ、という問題。 C++のnext_permutationなら何も考えずにうまくいきます、だそうで。(ソートしないといけないので…

250 辞書の中の語を二つ組み合わせてできる語を考える。既に辞書にある場合や、組み合わせが複数通りあるものの数を答えよ、という問題。 辞書と新規にできた語を覚えておいて、出てきた回数が複数回のものをカウントすれば良い。同じのが出てきたらカウント…

つまらないけど、一度はやっておかないといけない問題セット。つまらなさは異常。 250 N本のベクトルを利用してa1V1+a2V2+a3V3+...+anVn=Pとなるようにする。各aiが非負として、各aiの総和のうち最小のものを答えよ、という問題。 0除算が発生しないようにう…

長文読解テスト。不可もらいました。 300 複数の目的地があり、通過したN秒後に通過したことが分かる。同様に進行方向を変更するのもN秒後までできないし、停止もN秒後までできない。このときいずれかの目的地に到達するまでの最小時間を答えよ。(問題文に書…

問題が長かった。ついでに言うと面白みのない実装系セット。 250 NxNの対戦結果が与えられるので、対戦相手が行った自分以外の対戦成績が良い順にソートせよ、という問題。 ソートするだけ。 500 あるレシピが与えられ、作りかけの状態が与えられる。もしあ…

昔は逆だったのに、600は600ってほど難しくはないし900は900ってほど簡単でもない気がする。 250 一日の長さと一年の長さが与えられるので、一年をN日ないしN+1日にしたときにできるループの最小長を求めよ、という問題。 一日の長さと一年の長さのgcdを求め…

プログラミングスキルじゃなくて知能を測定している時点で詰んでいるんだと思う。半分くらいは英語の仕様書読みみたいなものだけれども。 250 N進数である数をDで割り切れるかどうかの判定は、最下位の桁のx倍+次の桁のy倍+...がDで割り切れるかどうかで決定…

手を抜いた分だけ情けないミスをしましたよ、という感じ。情けないっていう次元ではなさそう。 250 カードをPermutationを用いて1回以上N回以下のいずれかの回数だけシャッフルする。初期配置を好きなようにいじって良いとき、自分の欲しいカードが配られる…

非常に面倒なセット。基本は書いてある通りに実装するだけだけど、長文。 250 最初は正しい箱に正しい中身が入っている状態のものに対して、最後に使ったものは箱から出しっぱなしで、次のを使う時に今あけた箱に出しっぱなしだったものをしまうという処理を…

面倒なセット。 250 文字列ペアについて、the、of、andのいずれかの単語が含まれるか、単語数が3つよりも多いもの、が1つだけのものでないものを答えよ、という問題。 実装するだけ。 500 5個サイコロを振り、必要なものを残して他の物を振る(2回まで)、とい…