2011-12-01から1ヶ月間の記事一覧
遅延が定番になりつつ...。 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 矩形の形状に色が塗られている盤面があ…