問題概要 仕事がN( 解法 時間のかかるものから処理した方が良いのは明らか。また、処理してから分裂させるより分裂させてから処理した方がよいこともわかる。 なので、時間の大きい順にソートしてから、（いくつまで処理するか、未処理な狐が何匹いるか）を…

問題概要 長さN(k-1になるものをつくるかのいずれかである。kの最大値を求める問題。 解法 答えについて全探索する。こういうのは上手い方法があるのかも知れないけど、間に合うなら愚直にやってよいと思う。もちろん愚直に書くのがバグ生みにくいときの話だ…

問題概要 正整数列Xが与えられる。i番目とi+k+1番目をペアでとることができる。重複してとることはできない。とることのできる最大スコアを求める問題。 解法 MOD k+1で考えてよい。配列をMOD k+1で分類したとき、長さが偶数なら全部とることができて、奇数…

問題概要 RGBの値が、直前の値と離れすぎず近づきすぎずになるようにランダムに塗っていく。最初と最後が整合しない確率を求める問題(適当)。 解法 愚直にやると、状態数が40*50^3で参照先が50^3となりTLEする。累積和を用いてO(1)で参照できるように加速す…

問題概要 ある数列A(|A|=N0でなくてはならない。無数にある場合は指摘せよ。有限である場合、答えはsinged 32bit integerの範囲に収まる。 解法 こういうのは何も考えずに初項を適当に変数で置いてそれ以降を表す。こうすると上限と下限が得られるので範囲を…

結果。 1完だけど皆落ちまくって何とかレートは微増した。550は誤読したけど、十分難しかったのでちゃんと読めていてもダメだったっぽい。250は実にわかりやすい撃墜ポイントがあって、それには気づけたし大量に落ちるとも思っていたけど撃墜ケース作れなく…

問題概要 白い玉がN個、黒い玉がM個ある。この中からランダムに二つの玉を選んで白く塗る。全ての玉が白になるまでかかるに必要な回数の期待値を求める問題。 解法 よくある一次方程式型のDPを解くだけ。

問題概要 長さL( 解法 半分全列挙は間に合わない。二部グラフの片側の最大次数2という制約が強く、ひとつ適当に決めると後はいっぺんに決まる。各連結成分毎に独立に考え、それぞれ最小値をとってやるとよい。簡潔に実装する部分がメイン。

問題概要 0 解法 積がn!になるようなのを考える。n!=Πp_i^e_i (e_i>0)と書けるとき、既約なのでp_iは全部分子にいくか分母にいくかである。なのでn以下にある素数の数を2の肩に乗せればよい。このとき分子と分母は当然異なるので分子

問題概要 ジュースの入ったボトルが2本ある。各人が交互にジュースを残り半分ずつ飲んだ。もっとも多く(単独)ジュースを飲んだ人が勝ちになる。誰が何回飲んだかという情報が与えられるので、勝った可能性のある人を全て求める問題。 解法 nが小さいので全探…

結果。 Easyは誤読で手間取ったものの気にせず書いた。愚直な解法書いてる途中で綺麗な解法に気づいたけど大分書いてしまっていたので気にせず愚直に解いた。Mediumは割と速く解法が見えたけど、ちょっと実装ミスで長引いた。Hardは実装面倒だなー、くらい。…

問題概要 前進、後進、回転の操作列を適切に並び替えて原点からの距離を最大化する問題。 解法 前進、後進は全部まとめた方が良い。後は回転をその間にどう挟むか。つくれる角度は超簡単なDPで計算しておく。

問題概要 あなたは原点にいて4近傍のどれかに移動できる。いくつか点があって全ての点を1度以上尋ねて最後はどれかの点で終わるようなパスを考える。そのパスの経路長が指定された偶奇にできるかどうか判定する問題。 解法 最後の点をどれにするかでパリティ…

結果。 2完。easyは、見た瞬間「何これ超簡単じゃん」と思って、「%2を探すゲーになるなあ」とか思いながらサクッと書いた。mediumは久しぶりの幾何で、解法はちょっと考えたら正しそうなのが思い浮かんで証明せずに突っ込んだ。提出した後easyを見直したら…

問題概要 長さN( 各項に決まった値がxorされる。 値にある置換が施される。 のどちらかの操作が行われる。K( 解法 xorとかはビット毎にばらしてやれば良い。後は確率のDPをやればよい。「確率で」やると考えた方が分かりやすく、本当は同じことをしているは…

問題概要 A*p + B*q (p, q ≧ 0)の集合をX*p + Y*qが含むようにしたい。そのようなA,B,X( 解法 XがA,Bの約数なら無数に存在する。それ以外の時、X*p+Y*qによってA、Bが少なくとも作れなければならない。また、A、BがつくれたらA*p + B*qは自然に作ることがで…

結果。 275が割と早めに解けたおかげで500に時間をかけられた。500はDPを確率ベースで考えたらわかりやすかったのに期待値ベースで考えて混乱してしまった。残り時間が少なくなって適当にコードをいじっていたらサンプル全部通ったのでダメモトで提出してい…

問題概要 重複のない要素N(クイックソートでソートしたい。ピボットを越えて値をスワップする際にコストが1加算される。また、ピボットの左側と右側ではそれぞれ相対順序が保存される。ソートするのに必要なコストの期待値を求める問題。 解法 状態を(今考え…

問題概要 レジスタが一つしかない。レジスタには今ある値sが入っている。sに対してs:=s*s, s+s, s-s, s/sの操作だけでsをtに変えたい。sをtに変えるコマンド列で最短かつ辞書順最小のものを求める問題。0 解法 幅優先探索する。到達可能なノードは2のべきだ…

問題概要 長さN( 解法 貪欲に小さい二つを選んで合併していく。これでうまく行く理由は、小さいものほど後に残す影響を小さくできるから。

結果。 easyだけ解いた。mediumは普通に難しかったし、どれだけ時間をかけたとしても解ける気がしない。

問題概要 N( 解法 1単位量あたりの仕事をこなすのに必要な料金について、平均最小化の問題に帰着させる。蟻本にも載っている問題。

問題概要 2つの正整数x,yのgcdとlcm(ともに10^12以下)が与えられる。このときx+yのとりうる最小値を求めよ。そのようなx,yが存在しないときはその旨指摘。 解法 x=gcd*p, y=gcd*qとすると視界が開ける。解が存在しないのはlcmがgcdの倍数でないとき、あとはl…

結果。 2連続2完で嬉しい。3連続2完はまだないから次も2完したい。 250はgcdとlcmを見た瞬間x*y=lcm*gcdを連想して(よく出てくる)解法に気づけた。10^12という制約もルートで解けといわんばかりだし。実装もシンプルだったけど、1箇所int64をintと書き間違え…

問題概要 整数n( 解法 nを素因数分解してp_i^e_iが出てきたとき、これと同じ素数のべきで構成された数だけを使う。なので、まずそれぞれの要素を素因数分解してその約数でnを割り、割りきれなかったら即座に0を返す。割り切れないときはどのp_i^e_iが満たさ…

問題概要 長さN( 右の空のマスにずらす。 1つ右、2つ右にチェッカーがあって3つ右が空のとき右に3つずらす。 のいずれかをする。最右にチェッカーが来たら即消す。交互に動かして、動かせなくなった方の負け。勝つのはどちらか求める問題。 解法 なんか賢い…

結果。 久しぶりに2完。500遅すぎてひどいなーとか思っていたらみんなバタバタ落ちて順位はそこそこだった。でも前回落とした分を回収できていないのが辛い。 今回はチェックシートを用意して挑んだけど悪くなかった。何というか安心感が得られる。

問題概要 ノード数N( 解法 ビットDP。計算量が怪しくても大きいケースだけ埋め込めば通る。 個数制限なしナップザックみたいにやるとO(N*M*K^2*2^K)で解ける、と思ったけどまだ落ちてO(N*M*K*2^K)でいける。

問題概要 数字と.が書かれた長さ3のピースがN( 解法 左端と右端をどれにするか全探索する。全部数字なパーツも左端、右端の候補に入れた。そっちのほうが場合分け減らせてよい。 ピースが連結しない場合とかもあるので注意。

結果。 300だけしか解けずに残念な感じだった。450は計算量が結構怪しい解法を思いついて、しばらく他の解法ないかなーと考えたのち怪しい方法を実装した。ところがK=8のケースで一部TLEした。結局修正できずに終了してしまったけど、後から考えると埋め込み…