問題概要 重みなし区間スケジューリング問題を解く。ただし2個までは重複を許す。 解法 重み有り重複なしだとDPで重み有り重複有りだと最小費用流、重みなし重複なしだとGreedy、ここまでは知っていたけど重みなし重複ありは意外と知らなかった。制約見たらG…

問題概要 ノード数N( 解法 木を適当に根を選んで根付き木にする。その後適当に1点選んで、それ以外の点を角度でソートして各部分木のサイズごとに再帰的に割り振る。

問題概要 H*W(H,W 解法 8近傍にマップを拡大しておき、そのマップで探索する。同じ中で新しいマップにいくことができたらそのような遷移を繰り返して無限に遠くに行くことができる。1500^2*9でちょっと恐いがcharなので十分メモリは足りる。探索はDFSだとス…

問題概要 長さL( 解法 辞書式順序に対して、a+max(b,c)=max(a+b,a+c)が成り立つという事実を使う。後ろから見れば貪欲が効く。

結果。 1/5完。長さLの文字列をとるのに配列の長さを+1していなかったという信じられないミスをしてしまった。こういうミスが起こるのは集中力が絶望的に足りていないからだし、そもそも最近はあまり真摯に問題に向き合っていない気がするので、気合いを入れ…

問題概要 長さN(区間[a,b]にある1の個数はcである、というものである。条件を満たすような列のうち、[1,N]にある1の個数の最小値と最大値を求める問題。全ての制約を満たす列が少なくともひとつ存在することが保証されている。 解法 累積和+差分制約というよ…

問題概要 ノード数N( 解法 JAGの冬コンテストでも同じような問題が出ていた。貪欲にやってよい。分離云々のところはちょっと工夫したunion-findでKruskal風に行ける。

結果。 テスターやってました。開催までにジャッジ解と入力生成器を2撃墜できたので役目は果たせたと思います。 OUPCは初期はアジア地区予選想定ではなかったので簡単な問題しか入れていませんでした。アジア地区予選想定ということになってから難化させる必…

問題概要 整数K( 解法 Kの約数の個数をdとおく。d*Nは大きいのでTLEする。ところで、Kの約数がX[i]で割りきれるかどうかはgcd(K,X[i])で割りきれるかどうかと同じなので、各X[i]はgcd(K,X[i])で置き換えてよい。gcd(K,X[i])はKの約数なのでgcd(K,X[i])の個数…

結果。 4/4完で8位。これだけみれば悪くないけど参加者が正味何人いたのやら。全く同じ問題が出題されていたらしいけど、それを除けば悪い問題ではなかった。 ただ、システムは不満だらけでTLEの設定やら言語補正やらが分かりにくく、部分点制度を採用してる…

問題概要 2次元迷路がある。スタート->中間地点->ゴールの最短路を求める問題。 解法 BFS。

問題概要 長さ50以下の文字列が50個以下ある。適当に並び替えて、先頭から2個以上選んで連結して作れる文字列のうち辞書順最小のものを求める問題。 解法 小さいので全探索。とはいえもちろん3つ以上つなげる意味は無いので2個だけ選ぶようにする。

問題概要 ふたつの日付の間隔を求める問題。 解法 一日ずつincするのが間に合うので愚直にやる。

結果。 こういう形で開催されるコンテストが増えてきているのはとても良いことだと思います。問題は典型的なものが多かったです。

問題概要 4近傍に関する連結成分の個数を求める問題。 解法 flood fill。union-findでもいいけど普通は流す。

問題概要 L*H(L,H 考えたこととか 2000だしO(N^2)かなあ、setとかの重いlogはくっつけないようにしないと。 dpで考えてみるとdp[k段目][x座標][これまでに使った個数]でこれだけでO(N^3)なので無理げ。 dpでなく、線を決めて考えると…？ 傾きの候補はO(N^2)…

問題概要 アルファベットの先頭n( 考えたこととか 辞書順最小の何かを構成する問題なのでいつものパターンで行けるか？ 先頭からみていって、yes/noを返す判定関数を作れさえすれば良い。nが小さいので計算量は無視してよかろう。 えっと、今考えてる文字よ…

結果。 1完でとても悔しい。というのも500で固定長配列使わずにvector使ったせいでMLE(RE)したから。しかしこの失敗の本質は解答仕上げるまで時間書けすぎたせいで見直しする時間がなかったことにあるので、やはり速度が本当に必要な段階に入っているのだろ…

acceptされたコード 長さN( 解法 両端の要素が同じでその範囲ではその数がちょうどK回現れるような区間を列挙する。その区間を右端でソートして小さい順に重複しないように数え上げていけば解ける。BITなどを使っても解けるっぽい？

問題概要 H*W(H,W 解法 1の個数が2以下だと無理。それ以外の時、どれか1ヶ所変えて非連結にできるかどうかを調べる。これは全探索でよい。1ヶ所変えて無理だったら答は必ず2になる。

結果。 2/5完。Bが一番簡単だった。AでHack祭りだったけど自分も2回Hackされた。残りの時間ではずっとCを考えていて、場合分け多めにならざるを得なかったので慎重にやっていて提出したらWA。サンプル1すら通っていなかったので不思議に思っていたら問題を2…

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

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

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

結果。 尊敬する競技コーダーであるところのtomerunさんとuwiさんのチームに混ぜてもらって参戦。残念ながらあまりチームに貢献することはできなかったけど、とても楽しい経験をさせてもらった。やっぱりチーム戦は楽しいのでこれからも増えてほしいところ。…

問題概要 C++のstd::pairでintのpairを入れ子にして作る。そのを省略した文字列が与えられるので復元する問題。矛盾があれば指摘する。 解法 BNFが ::= pair, > | なのでそれにしたがって書く。ただし最後が余ることがあるので注意。

問題概要 W*Hのマットがあり、その中にN個の円(半径はそれぞれ決まっている)を詰める。中心がマットの中に入っていればよい。円同士は重なってはならない。そのような円の配置方法をひとつ出力せよ。マットの面積は円の面積の総和の5倍以上であり、答えが必…