Hatena::Grouptopcoder

Hiro180の日記

2017-06-18

AOJ-ICPC埋め (2nd) 15:02

面白かったのをピックアップします。

鎖中経路 (550pts)

中心&交点を列挙してdijkstraする。辺を貼れる条件の言いかえが結構難しい。

ぼくのかんがえたさいきょうのおふとん (550pts)

dp[mask] = (maskに含まれる布団のぬくもりの和をSとするとき、maskに含まれる布団のあり得る順番すべてに対して需要がS以下の日に対する不快度の和の最小値)とすると通る。

Dictionary (550pts)

色々な意味で難しい。dp[L][R][K] = (L~Rの辞書をK文字目以降で辞書順に並べ替える方法の数)とする。

選挙活動 (600pts)

考えるべき点は(人-多角形の頂点)の直線同士の交点のみ。あとはライブラリを貼ってなんとかする。

ICPC Teams (600pts)

これはかなり難しい、あと良問。余事象を考えて包除原理すると制約がsameだけになるのでできる。

Polygon Guards (700pts)

凹多角形と点の包含関係は偏角の和で判定できるらしい。あとは解の上界を見積もって枝狩り探索。

Towns along a Highway (800pts)

探索木の大きさをO(2^N)にしようと考えると解ける。左右から1つずつ決めていくだけ。

回転と書換 (800pts)

区間DPである区間を文字chに変換できるかを求めたあと、2つの区間を持つDPで徐々につなげていって最大値を求める。

2017-06-14

AOJ-ICPC埋め (1st) 13:00

競プロ再開します。(今回はマジです。) 最近やった問題のまとめ的なことをします。

Rabbit Party (500pts)

クリークを全て調べて終わりです。(575)

引っ越し (550pts)

http://joisc2011.contest.atcoder.jp/tasks/joisc2011_bookshelf をします。

つながれた風船 (550pts)

高さで二分探索することを考えると、結局N個の円があった時すべての円が含む点が存在するか否かを判定すれば良くなる。

2円の交点と各円の中心を考えれば十分。

夕食 (550pts)

良問。そのままDiv1Medに使えそう。解法は食堂に使うべき順番(Ci+i*pの大きい順)が決まるので、食堂を0個、1個、2個...使う場合の幸福度を順に計算してmaxをとればOK.

Reverse Sort (600pts)

解の上限は9なので、8以下にできるかを考える。区間を選び反転する操作は可逆なことに気づけば半分全列挙のノリですり合わせるだけ。(カンニングしました。)

ほぼ周期文字列 (600pts)

sa+lcpを貼って、Tだけずらした文字列同士に対してグチャグチャやると通る。ハッシュを使った解法の方が綺麗に書けます。

最強の呪文 (700pts)

良問。解法は後ろから見て(dp[v] = (vからゴールに至る辞書順最小の文字列)とする)ベルマンフォードをする。存在しない場合を弾くのが難しくて結局良く分からないまま通してしまった(反省)。


800pts以上はなかなか手がつかなさそうですが国内予選まで頑張りたい。

2016-12-31

2016年を振り返る 20:37

競プロと少し疎遠になったのもあり目標を立ててその結果発表をするだけのブログになりつつありますが、今年も振り返ります。

(目標: http://topcoder.g.hatena.ne.jp/Hiro180/20160103/1451813037 )

JMO: 1/20 春合宿止まりでした。

JOI: 1/10 レベルが高い。

運動会: 0/20 大事なのは優勝することじゃないです。(じゃなんでこんな目標にしたんですかね....)

(ちなみにそれぞれ2回戦 / 5位 / 4位 でした)

iPad模試: 0/5 不可能。

東大模試: 4/9 秋OPで339取った。3位とかどうして取れると思ったのか。あとA判阻止した本レは許さん (白目)

実テと定期考査: 4/4 実テで2回1位だった。定期考査も年間9.8だったし良いのでは。

卒業条件: 4/4 遅刻28とかしたけどセーフ。

音ゲー: 4/4 結構スッパリ辞めました。(模範的受験生なので最近ハエレ鳥乗せてしまったのは内緒) (ゲーセンは殆ど行かなかった)

生活リズム: 1/4 卒業は出来たので情けの1点。() 来年の課題です。

パソコン甲子園: 3/4 健闘できたので3位だったけど高評価。Isは良いコンビだったと思います。

数学甲子園: 4/4 結果は4位ですが満足だし楽しかったから満点。良いチームだった。

数学甲子園の審査員には京大の特色入試レベルの問題も評価して貰えなかったしIMOの3番級の問題でも作れば良いんじゃないんですか。知らんけど。

適当なイベント: 4/4 化グラ金。参加するとすら思ってなかったけど楽しかった。

コミュ力: 2/4 微増。

人生を楽しむ: 3/4 まあ概ね楽しんだ。

総計: 35/100 (落第)


まとめ: 目標を得点制にするのやめます (震え声)

追記: そういえば目標に無かったので忘却してましたが、申し訳程度の競プロ要素としてSRM 694のwriterをしました。後でそれについて記事を書きます。(たぶん)

2016-06-12最近解いた問題

たまには競技プログラミングのブログも書こうと思います。

面白かったのとか教育的なのとかをまとめる。

Yandex 2016 round2 D 23:48

<問題概要>

Ax+By = Cを満たす非負整数x,y全てに対して C(x+y,x)の総和を求めよ (A,B<=100 C<=10^18)

<解法>

要するに「総和がCになるようにA,Bを並べ替える方法は何通りあるか」を求めればよい。行列累乗するだけ。

csacademy beta round 7 Array Coloring 23:48

<問題概要>

N個の無色のセルをM回異なる色で区間を塗った結果が与えられる。考えられる色の順番すべてに対して、「色を塗られた回数」の最大値が最大になるとき、その回数を求めよ (N,M<=100000)

<解法>

色ごとに(左端、右端)を求め、ある色と色に対し、「片方の(左端、右端)を含む最小の(左端、右端)がもう片方の(左端、右端)」であるとき、対応する頂点間に有向辺を結ぶことを考えると、森になる。ダミーの根を作り木にして、木DPをする。

「間に根の色を挟まないような子の集合に対し、1つはdpの値を、その他は1を加えた値」の最大値が今考えてる部分木に対するDP値。

SRM691 Div1 Med 23:48

<問題概要>

仕事がN個あり、経験値と係数が決められている。得られる収入は(これまでの経験値の総和)*(その仕事の係数)である。

ただし、Nは偶数で、N/2個仕事をした時点で研修に参加し経験値がX増えるものとする。

収入を最大化せよ。 (N<=50,経験値,X<=100000,係数<=10)

<解法>

X=0の場合を考える。

(経験値、係数) = (ex1,co1),(ex2,co2)の2つの仕事を考える。これまでの経験値をexpとすると、収入は

・前者->後者: (exp+ex1)*co1 + (exp+ex1+ex2)*co2

・後者->前者: (exp+ex2)*co2 + (exp+ex1+ex2)*co1

となるので、(前後はどちらも同じ。)

実質ex1*co2とex2*co1の比較であり、それはつまりex1/co1 と ex2/co2の比較である。

以上より、(exp/coef)が大きい方からやるのが良いと分かった。 (こういう問題、150問に1問くらいのペースで見るイメージがある)

X>0の時にはこれではうまくいかない。しかし、Xの前後ではそれぞれこの順番で並べるのが良いので、

順に振り分けていくDPを考える。

ここで、収入の計算方法を

(exp1+exp2+.....+expE) * coEを毎回加えるのではなく、(coE+co(E+1)....+coN) * expEを毎回加えるという発想をすると、

研修の前にやった仕事に対する係数の総和を決め打ちすると(tmpCoとする)

前に振り分けたときは(sum(co)-sum(振り分け済みの前のco)) * exp

後ろに振り分けたときは(sum(co)-tmpCo-sum(振り分け済みの後ろのco)) * exp

を毎回加えればOK。

計算量は50 * 25 * 250のDPを25*10回くらいするのでまぁ通る。 良問。

SRM692 Div1 Med 23:48

<問題概要>

長さSの文字列が与えられる。(length(S)<=100)

以下の条件を満たす文字列は何通りあるか.

・non-intersectなSの個数の最大値はK個 (K<=10^9)

・長さはK*length(S)以上K*length(S)+N以下 (N<=1000)

・文字はすべて英小文字

<解法>

貪欲に取っていったときの出現箇所を考える。

1つ目の出現箇所までに無駄な部分がi文字になるような場合の数は、愚直なDPで計算できる。

一つ前の出現箇所から無駄な部分がi文字になるような場合の数も、愚直なDPで計算できる。

ここで、dp[i][j] = 2^i個文字列が出現するときに無駄な部分がj文字になるような場合の数

とすると、O(N*N*log K)くらいで計算できる。

最後の出現箇所から無駄な部分がi文字あるような場合の数も、愚直なDPで計算できる。

以上で求めた値を掛け合わせて足せば答が出る。

SRM692 Div1 Hard 23:48

<問題概要>

根付き木が与えられる (頂点数<=300000)

全ての部分木に対し、(ある頂点からすべての頂点へのパスの重みの総和)の最小値のXORを求めよ。

<解法>

重心が最小化する頂点なのはまあそれはそうっていう感じで

部分木に対し、重心が求まればパスの重みは求まるので、重心を求めることを考える。(地味に256MB制限が厳しいのでsegtreeに逃げることはできません)

ところで、ある部分木(根をVとする)に対し

すべての部分木サイズがもとの部分木サイズの半分以下ならVが重心になり、そうでないときは

部分木サイズが最大の子(V2とする)の重心の祖先のどれかが重心になることが示せる。

(前者は自明、後者はV2の祖先以外が重心になるとすると、その頂点の部分木サイズは明らかに小さすぎるから矛盾)

よって、(自分から子へのパス重みの総和、重心)を返しつつDFSをすればOK.コスト計算はDoublingでできる。

(重心を求めるフェーズがやばくならないのは、「系列」が変わらない限りO(N)で済むことと、「系列」が変わるときには部分木サイズが倍以上になるからまとめてO(N log N)的な感じだと思います)

2016-01-03

2016年の目標 18:23

今年も去年の形式と同じにします。


<JMO>(累積和)

合宿に行く: 1点 IMOに行く: 9点 IMOで銀メダル以上を取る: 10点


<JOI>(累積和)

合宿に行く: 1点 IOIに行く: 4点 IOIで銀メダル以上を取る: 5点


<運動会>

馬鉢優勝:5点 6棒優勝:5点 総合優勝:10点


<模試系>

iPad模試で3連覇: 5点

(この行は全て東大模試) 4月以降全部理三A判: 1点 1回以上334点以上とる: 4点 1回以上総合3位以内に入る: 4点

実テか定期考査で1回以上1位を取る: 4点


<その他諸々> (部分点有り)

卒業条件を満たす: 4点

音ゲーをやり過ぎない: 4点

生活リズムを整える(=授業中寝ない、寝過ごさない): 4点

パソコン甲子園で金を得る: 4点

数学甲子園で人権を得る: 4点

何か適当なイベントに参加していい結果を出す: 4点

コミュ力をつける : 4点

人生を楽しむ: 4点


以上100点満点。赤点になる未来しか見えない感じの目標だけど頑張りたい。