問題概要 W*H(W,H 考えたこととか 最後のステップでは単調増加列っぽいのを必ず消すんだからそこを目標にすれば良さそうだな。 全列挙は流石に無理。DPも覚えるべき状態数多すぎ、xorする系のやつだからフロー系もないだろう。 というか、これ答存在するのか…

問題概要 一人以上が参加した投票が合った。各候補者の四捨五入された得票率が与えられるので、そのような得票率が実際に現れるには最小で何人の投票参加者がいればよいか求める問題。無理なら指摘する。 考えたこととか 0がコーナーケースになりそうな予感…

結果。 久しぶりにeasyを落としてしまった。そしてmediumは多くの人に解かれていたので当然速度差で負けた。速度どうやればでるのか未だに分からないので困る。

問題概要 問題文は状況を理解しにくいものになっているので、解答を見て問題を想像してください。

結果。 1/4完。最初サンプルの意味が分からずに1時間くらい消費した時点で心が折れた。2問目は証明なしで貪欲というかシミュレーションっぽいのを書いて、手元でちゃんと出力条件満たしてるのに何で通らないの？また読み間違えたのか？と混乱状態になったけ…

問題概要 N( 解法 許容誤差が小さいのでモンテカルロでよい。許容誤差の2乗*定数回程度回せば失敗確率は十分小さくなるらしい。

問題概要 W*H(W,Hボトルネックを最大化する問題。 解法 答について二分探索する。こうすると、各マスにある時刻で入れるかどうかが簡単に判定できる。なお、答は十分小さい値をとりうるので、low=0.0なら到達不能、とすると間違える。

問題概要 文字を逆さにしたときの辞書式順序でソートする問題。

問題概要 数列の平均値を出力する問題。

結果。 D言語でやるかー、と思ってAやっていたら何故か合わずにあせった。A~EでなくA,B,C,D,Fになっていて、はーそーなんですかと思いつつ修正してAC。 Bは反転するだけだと思って実装するとコンパイルエラー。std.algorithmのreverseは返り値がvoidなのでre…

問題概要 N( 解法 押し付け合うフェーズでは、どちらも重いものから貪欲に押し付けるのが最適になる。とすれば、k番目に軽いものがどちらの負担になるかは分かるので、後はAが自分の負担が最小になるように最初に選ぶだけになる。これはとても簡単なDPで計算…

問題概要 1~Nを並び替えた順列pがある。pのうちいくつかは分かっているがほかは分からない。pの中から何かを選んで加点する。加点してP点を確実に越えるようにしたい。最小なんかい選ぶ必要があるか求める問題。 解法 分からないものの平均値と分かっている…

結果。 遅い1完で酷い目にあった。

問題概要 10個のボールがあり、番号がついている。順序を保ったままボールをふたつの集合に分けるとき、どちらも番号が昇順になるようにできるか判定する問題。 解法 10個しかないので全探索。ボールの数が増えてもDPで解ける。

OUPCのFour Arithmetic Operationsの解説にも書いていたけど、忘れないようにまとめておく。 A*B を mod M (M>2^31)の世界で計算したくなったとする。当然、A,Bともに大きな値となり、そのままA*B%Mを計算したらA*Bの部分でオーバーフローが起こりうる。 じ…

問題概要 文字列Tを前半と後半(ただし後半は非空)に適当に分け、前半に含まれる4の数と後半に含まれる7の数が一致するときTはバランスがとれているという。長さL( 解法 文字列Tがバランスがとれている条件を考える。4[i,j]を部分文字列T[i,j]([i,j)の半開区…

問題概要 長さ50以下の文字列がK+N個(K,N 解法 小さいので愚直にやって間に合う。

結果。 3/5完。lucky numberな回。もう少し早く解けるようになると嬉しい。

問題概要 (0,0)から(N,L)(N(i,j+1)へは1.0/vで移動でき、(i,j)->(i+1,j+k)へはsqrt(w[i]^2 + k^2)/u[i]で移動できる。 解法 とりあえずO(L^2*N)の自明なDPが見える。本番中はこれを落とせないか考えていたけど落とせなかった。終了後Petr先生の解答見て勉強…

問題概要 [L,R](1 解法 以前1~Nまでのxorがどうなるか調べたことがあって、それを思い出すだけで良かった。 1~Nまでの累積xorはmod 4で周期性が現れる。2*n ^ (2*n+1) = 1になって、その1を打ち消すのにさらに2つかかるという理屈。

結果。 残念ながら1完。とはいえ撃墜とvolaの高さのせいかレートは上がった。 easyは過去に調べたことがある題材だったので自分にしてはさくっと解けた。mediumはDPでどうやって計算量落とすか、という話になったのだけどパターン当てはめることが出きるよう…

問題概要 バスに子供がM人、大人がN人乗っている。子供は料金を支払うことができない。大人は自分のぶんだけか、子供の分を支払うことができる。ただし、子供の分を払うときは1人分料金が免除される。支払われる料金の最大値と最小値を求める問題。支払うこ…

結果。 ジャッジシステムの不具合によりunratedになった。D解くのにかなり時間とられてしまった。

問題概要 与えられた文字列を最小何回のスワップで回文にできるか求める問題。無理なら指摘する。 解法 まず、できるかどうかは奇数回出現する文字を数えれば良い。もし奇数回出現する文字が真ん中にないのなら、まずスワップして真ん中に持っていく。 後は…

精神的、体力的な負担が大きくなりすぎてしまったし、何より楽しいと感じることがなくなったのでこれからはMarathon Matchに参加しないことにしました。 最初はhasi君が、「Marathon始めたらalgoのレート上がった」と言っていたので興味を持ったのですが、実…

解法 問題文よく分からなかったのでサンプルを眺めていたら最大値を求めるDPっぽかったのでその通り書いたら通った。

問題概要 2次元平面上にN( 解法 まず凸包を作る。整数座標なので凸包は100個ちょいしか残らない。N^3だとTLEするのでキャリパーっぽくN^2でやる。底辺の2点の組み合わせを全探索する。もっと速く解けるらしい。

問題概要 10*10の盤面があり、各マスは黒か白である。任意の大きさの正方形で全ての黒いマスを被覆する。このとき、はみ出したり白のマスに重なってはいけない。最小枚数を求める問題。 解法 基本方針はBBだけど、下界は相当緩くてよい。正方形を考えるとき…

問題概要 重さw[i]、価値v[i]の商品がC( 解法 どの商品が中央値にくるかを全探索する。その商品以下の価値からN/2個、それ以上からN/2個選ぶときは重さの小さいものを貪欲に選べばよいので、これはheapを使えば前処理で効率的に計算しておくことができる。

問題概要 長さL( 解法 一瞬Div 1 500の類題より難しいように見えたけど気のせい。各文字列について、何番目に来るかの期待値=前にくる文字列の個数の期待値。お馴染みの線形性を用いると、各文字列が前に来る確率を足しあげればよいことがわかる。文字列A、B…