遅延が定番になりつつ...。 250 整数配列が与えられるので、任意の整数を好きなように二つに分ける、という操作を高々K回行ってよいとき、10をいくつ作れるか答えよ、という問題。 取り敢えず、20を見たら優先的に処理したい。それ以外はどうやっても同じ。…

A 文字列が4つずつ与えられるので、接尾辞が一致するパターンがどのようになっているか答えよ、という問題。 やるだけ。 B 整数が与えられるので、適当に各桁の数字をスワップしたものを二個作り、加算した結果の末尾の0が一番多くなるものを答えよ、という…

前に入室トラブルがあったので、その補足の回。完敗。レートは気にしないがdivisionは気になるので、ネガティブスコアはやめましょう、と思った次第。 250 1からNまでの数字が順番に並んでいる。平方数番目にある数を除去する操作を繰り返していって、最後に…

問題 N以下の数のうち、0と1以外の数字を含まないものの数を答えよ、という問題。 解答例 やるだけ。1から初めて、10倍した数と10倍して1加えた数の両方を再帰的にチェックしていく。int溢れに注意するだけ。 これそのものは意味のない問題だけれど、AとBだ…

やるだけ幾何。幾何といえばdoubleの精度を気にする問題。 問題 目的地と現在乗ったばかりのバスの停留所の座標と、バスの速度と自分の移動速度が与えられる。次以降の停留所で降りるとして、目的地に最短で到達することの出来るバス停(同じ時間のものが複数…

問題 Ax+By+C=0なる形式で与えられる直線が、格子点を通るかどうか答えよ、という問題。通るなら一つ点を答える。 解答例 拡張ユークリッドの互除法をやるだけ。Ax+Byの0ではない最小値と、そのときのxとyが求まるので、Cがそれで割り切れるかどうか判定する…

簡単な問題しか解けない病気...。 問題 (または)からなる文字列が与えられるので、バランスの取れている最長区間の長さと、その長さに該当する個数を答えよ、という問題。 解答例 バランスの取れている条件は、隣にバランスの取れているものがくっつくか、(…

問題 整数列が与えられるので、最大値と最小値の差分がK以下になるように取ることができる最長の連続領域の長さを求め、それに該当する区間をすべて列挙せよ、という問題。 解答例 とにかく最初から順番にできるだけ長い領域を確保する。こうすると次に入れ…

問題 N進数の掛け算の表を作れ、という問題。細かいレイアウトはしなくて良い。 解答例 普通に標準ライブラリに整数をN進数表記に変換する、というものがある言語の方が最近は多いと思うので、それを使えば問題なし。自分で書いても大して困らないとは思うけ…

そもそもどこに勝敗ラインを引くかで人生は決まると思うのですが...。 275 ノード数がNの木のうち、各ノードの次数に応じたスコアリングを行うとき、スコアの最大値を答えよ、という問題。 ノード数とランクの合計値を状態にしてDPすれば良い。ただしすべて…

普通に大敗。最初から勝ち目のない戦いという感じではあるけれども。 A 整数配列が与えられるので、任意の要素の値を別の値に変更してソートするという操作を一度だけ行ったとき、各位置にくる値の最小値を答えよ、という問題。 とにかく一番大きい値を出来…

ちょっと変則な時間だった。 250 見てない。 500 見てない。 1000 長さ50程度の0か1からなる文字列が50個ほど与えられるので、それらから一個ランダムに選ぶ操作をK回行ってできる文字列に、長さ500程度の文字列が何回出現するか期待値を答えよ、という問題…

英語読解力と実装力のテストにはちょうど良いみたいです。 A 文字列が与えられるので、各文字間の差分をビット列で逆順にしたものを出力せよ、という問題。(意訳かつちょっと違うけど。) 英語を読んでやるだけです。 B 矩形の形状に色が塗られている盤面があ…

想定解なんて知ってるわけないじゃん...。 問題 大きさ1のものと2のものしかないナップザック問題。 解答例 大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大き…

典型的な誤差について考える幾何の問題。 問題 正N角形の頂点のうちの三つが指定されるので、可能な正N角形のうち、一番小さいものの面積を答えよ、という問題。 解答例 外心を計算して、各頂点との間でなす角の角度を求めてやる。それが正N角形のNを指定し…

過去問ちょこちょこ。4桁の人が解いている問題はやる必要ないとは思う。 問題 N*MのホールをカバーするようにA*Aの布を敷きたい。布は切ってはいけない。何枚必要か答えよ、という問題。 解答例 縦に何枚、横に何枚、というのを計算して乗算するだけ。乗算の…

完敗。手も足も出ず。 300 板の上にコインが乗っている。全部のコインを上下左右にまとめて移動させることができるので、できるだけ少ない操作回数で、コインの残り枚数を指定された枚数にしたい。最小回数を答えよ、という問題。 どの矩形領域を残すかとい…

分かるけど、できない。できなきゃ意味ない...。 250 距離Xだけ荷物を運ぶが、一度の運搬で移動して良い距離は素数でない距離でなくてはならない。何回の運搬に分けて行えば良いか答えよ、という問題。 Xが素数なら1だけ動かして、素数でなくなるまで試す。 …

問題 有向グラフが与えられる。開始点と終了点が与えられるので、最短距離またはその+1までのパスは何通りあるか答えよ、という問題。 解答例 まずダイクストラで、開始点からの最短距離を全部の点について求める。再度ダイクストラで、最短距離またはその+1…

明日に備えて肩慣らし。タグをPOJにしておくべきだったかも？ 問題 石がいくつかある。それぞれに重さと価値があって、二つのバケツに振り分ける。最初は一つ目のバケツに石を入れていき、D+1以上の重さになったらもう一つのバケツに入れていく。二つ目のバ…

参加資格剥奪です、といわれても仕方ないくらいひどいスコア。 A 8x8の盤面上を、下向きに移動する物体が配置されているので、上下左右斜め移動を駆使して全部回避できるかどうか判定せよ、という問題。 やるだけ。 B 文字列が与えられるので、その任意の部…

比較的新しいところをやろうとして、解いた問題番号のmax付近から。2005年って新しくはないな...。 問題 行列に対して、上下反転・左右反転・90度刻みの回転・対角線で反転(2種類)といった操作列が与えられるので、最終的な結果を答えよ、という問題。 解法例…

解けないと判断したときに踏ん切りがつかないのをどうにかしましょうね、というお話。 250 a+b*xとc*d^yという式で表現されるN以下の数はいくつあるか答えよ、という問題。 前者は圧倒的に数が多いので、取り敢えず除算でいくつあるかカウントする。後者は指…

最初二問が普通なのに、最後が...。 250 N人の人がいて、全員白または黒の帽子をかぶっている。自分以外の人を見て白い帽子をかぶっている人数を答えるので、白い帽子をかぶっている人の人数を答えよ、という問題。 結果をソートすると、白い帽子をかぶって…

二回目なのに、余りの頭の悪さに絶望した...。 250 NxMの盤面に数字が書かれている。どの行・どの列からも二つ以上数字を選ばないように選んだとき、総和が等しくなるか否かを答えよ、という問題。 DPすれば良い。選択しない行があるとめんどくさいので、行…

4と7からだけなる数字のセット。以下これをLucky数として...。 A Lucky数でceilingを計算することにして、AからBまでの数のceilingの合計値を答えよ、という問題。 Lucky数を求めておいて、飛び飛びにその区間をまとめて足すだけ。 B 文字列中の47という部分…

比較的やるだけセット。結果的にどうやっても通ってしまう感じ。 250 ある数字を作りたいが、使って良い数字が指定されており、後はinc/dec操作しかできない。数字指定とinc/dec操作の必要な最小回数を答えよ、という問題。 作りたい数字が比較的小さいので…

冷静にかつ高速に実装する能力が足りない。明らかに経験値不足。情けない...。 250 見てない。 450 見てない。 1050 二次元空間上に点がいくつか与えられる。二点を指定してできる矩形の中に入る点を除去する操作を任意の順番で行ったとき、残る点数として可…

微妙なセット...。強実装。 250 A個セットでB円というものがいくつかあるので、少なくともK個入手するのに必要な最小コストを答えよ、という問題。 最後の帳尻合わせが面倒なので、DPすれば良い。Kが大きければ、一個当たりの単価が一番安いセットをある程度…

double誤差を意図している感じの悪さを除けば、比較的良いセット。 250 0点から10点までの1点刻みの点数で答えるアンケートを行ったときの、各質問における点数の平均値が小数点以下4桁目以降を切り捨てる書式で与えられるので、何人にアンケートを行ったか…