267.1

つまらないけど、一度はやっておかないといけない問題セット。つまらなさは異常。

250

N本のベクトルを利用してa1V1+a2V2+a3V3+...+anVn=Pとなるようにする。各aiが非負として、各aiの総和のうち最小のものを答えよ、という問題。

0除算が発生しないようにうまいこと分母をいじりつつ、2文字の連立一次方程式を解くだけ。下手にやると0除算(実際には0に近い値での割り算)が発生して変な値が返ってくる。doubleでやらないといけないようにsinとかcosを使う形でN本のベクトルが与えられる。doubleでちゃんと正しく演算できますか、という問題。もちろんできません、と答えておいた。

500

15パズルみたいな状況で、目的のものと空白の位置が与えられて、目的のものを一番左上に移動するまでに何ステップ必要か答えよ、という問題。(他の場所の形は問わない。)

最初に上に動かすか左に動かすかを試して、以降はグリーディ。壁際で一個動かすのにはコスト5かかり、それ以外の場所で一個動かすのにはコスト3かかる。(後者の場合はジグザグに動くことを強要されるので、いつかは壁際に行くことになる。)最初に動かすコストは目的のものと空白の位置とのマンハッタン距離か何かだけれど、目的のものを跨ぐことはできないので、若干修正が必要。グリーディな問題でちゃんとコーナーケース拾えますか、という問題。余りにも面倒なので最後の方はパラメータいじってテスト通るまで何回か適当にやってた。

この問題については別解があるはずだし、そっちの方が安全なのでそれを使って解いた方がいいと思う。単純に全探索するとメモリがいくらあっても足りないが、最初以外は目的のものから2マス以上離れる必要はないので、メモしつつ全探索すればいいと思う。

1000

複数の作業を順番に行っていくとき、作業を開始できるようになる時間が与えられ、最後の作業が終了した時間が与えられる。(英語の意味が理解できていないので、直訳のようなものを書くと意味不明になるので簡単に書くと)一番時間のかからなかった作業にかかった時間の最大値として可能な値を答えよ、という問題。

単純にバイナリサーチするだけ。すべての作業に同じ時間がかかったとしても一般性は失われないはず。

取り敢えず問題文の意味を理解しないでコーディングして、あってるかどうか試すのは非効率だからやめた方がいいと思うのだけれど、その辺がどうにもならない...。