問題概要 2次元平面上に点がN( 解法 とりあえず座標圧縮しておく。その後x座標の大きい方から右上にいくつ点があるのかとx[1]

問題概要 重み付き有向完全グラフが与えられる。ノード0からスタートしてもっともコストが小さい辺を選んで未訪問のノードへ行く。1本辺を選んでコストを書き換え、全てのノードを訪ねるのに必要なコストを最大化する問題。 解法 どの辺をどの長さに書き換え…

結果。 1完。これで4連続で2完を逃しており辛い。 300は全探索考えた上で計算量危ないから場合分け多い方向に走ってしまったけど、ちょっと工夫して探索空間減らせば場合分けを減らせてよかった。とにかく場合分けはバグの元なので場合分けしなくていいよう…

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

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

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

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

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

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

問題概要 (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でどうやって計算量落とすか、という話になったのだけどパターン当てはめることが出きるよう…

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

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

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

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

問題概要 長さL( 考えたことなど (easyが酷い点数で残り時間も少なく、焦った状態で問題を開いた。いつもはDivision Summary見てから問題開くのに今回は余裕がなくて忘れていた) (問題を下から眺める。確率か。しかも複数求めるやつだしどうせDPだろう)。 問…

問題概要 [0,X)*[0,Y)(X,YB->C->Aというルートで巡回する。ある地点からある地点まで移動するにはマンハッタン距離に比例した時間がかかる。時間が[minT, maxT]に収まるような3点の選び方は何通りあるか求める問題。 考えたことなど (まず問題を下から眺める…

結果。 またしてもレーティング上がって2400を突破した。1年前の青だった自分と比べても特に解ける問題の範囲はそんなに変わってないのにとても不思議。easyに安定感持たせてmediumから苦手意識を取り除くだけでこんなに変わるのか…。 最近は明らかに好調な…

問題概要 ある数字列X(Xの長さは50以下)がある。いくつかの適当Xを一文字だけ置換した数字列が与えられるので、Xとして考えられるものがいくつあるか求める問題。 解法 候補はたかだか10*50しかないので全生成してチェックすれば良い。

問題概要 兵士がN( 解法 実はこのままではこの問題は解けず、「合流はない」という条件を付け加えなければならない。 最短経路に使われる辺だけを(有向化して)残すと辺の重みが正なのでDAGになる(距離の近い順がそのままトポロジカル順序になっている)。求め…

問題概要 N(≦16)個の箱があり、各箱の中には石が十分たくさん入っている。この箱の中からいくつか選び、lower[i]以上upper[i](1 解法 愚直に塗りつぶしたりsegtree使ったりしても解けるらしいけど、時間空間ともに危険域なので別の方針で頑張る。 部分集合を…

結果。 Div 1 550にミスがあってunratedだった回。unratedなだけで、勝利数とか正解数とかには反映されてるっぽい。 赤10人うちターゲット3人というエグい部屋だった。全体順位63位で部屋内順位10位。2完できたのはよかったけど550はもう少し早く解けてもよ…

やっと念願かなってTopCoder Algorithm部門で赤コーダーになれた。以前にも書いたようにこの部門が花形だという意識が自分の中にあったのでとても嬉しい。僕はICPC組やJOI組と違ってTopCoderから競技プログラミング始めた人間なので、レーティングの変遷を見…

問題概要 f(X)=A+X+B+X+C (各変数は文字列)がある。f^k(X) (k 解法 Xの中にPがk回現れるとすると、f(X)の中でPは2*k+(AとBとCに一部が含まれるようなPの個数)となる。( .. )の部分は文字列のprefixとsuffixを持っておけばよい。毎回prefixとsuffixを計算し直…

問題概要 蟻がN( 解法 すれ違いを避けるため、最初に座標を全部2倍(どうでもいいことだけど、この座標を2倍するテクニックって結構頻出で、自分は勝手に座標拡大といっている)して毎秒1単位の速度で動かしてシミュレーションする。衝突が起こるとき、かなら…

結果。 2完+撃墜200で5位！前回も撃墜で+300とかしていたので運がよい。開始前は全く自信なくて「きっと半日で赤コーダー陥落するんだろうなー、記念赤って感じだよなー」とか思っていたのに、何と次も赤維持できそうなくらいのバッファができた。撃墜とかは…

結果。 1完(90点！)+撃墜300点で念願の赤コーダーに。medium開いてすらいない意識の低さが自分らしい。 最初は二部マッチングで真面目にやるのかなー、とか考えつついやいやTCOとはいえeasyでそれはないと考え直した。最初は最大サイズ-1が答えかと思ってサ…

問題概要 サイズN( 解法 既に得られた結果の内、互いにまったく区別できないような番号をまとめて、その最大サイズのみに応じて答えは決まる。分割してパラレルに処理することができるので最大サイズのlog程度が答えとなる。矛盾のチェックは集合Sとσ(S)のサ…

問題概要 長さN(スワップすることを繰り返してa[i] 解法 まだよく理解していないのだけど、動かすのは片方の列だけだと考えて大丈夫らしい。 それを踏まえると、(前の列の何番目までは対応付けた、既に動かした後列の集合）を状態としてdpで計算できる。