CF #500

大失敗。


記念すべき500回目らしい
出ちゃうか
6問

C読む
うーん
とりあえずAに行く

A:
Aにしてはむずくない?
AGCのyosupo回でみた
mxとmnが同じ側なら幅N最小で違う側なら半分ずつだな

B:
できる限り操作をすると長方形いくつかになる
これを得れば答えもすぐわかりそう
(x,y) と (x,y') に辺を生やせば
冷静に考えると x-y で辺を生やせばいいな
答えは連結成分-1

C:
取るべき値は少ないので現在の値を持ってDP?
ちょっと面倒そう
選ぶやつを固定すると、適切な位置でコストを発生させれば (何個選んだか, 直前選んだか, 2狛江選んだか) でやれるな
TLE
は?
内側でK * 3 の vectorを毎回宣言してたのを外側にしたらTLEが取れた
5000 * 2500 * 3 でこんなに遅いのか・・・

順位絶望だったが順位表見てもD以降全然解かれてなくてたまげる
とりあえずD読む
D:
はえ
とりあえず手でいろいろ試す
連結成分の数は高々2しか減らないことによる下限があるな
(abab,baba) みたいなのならこれを達成できる
2kなら一回使えば↑の王道ルートに乗せれそう?
2k+1 も一回使えばいけそう こっちはこれで最適
逆から考えると場合分けがわかりやすいな

何通りか場合分けして書く
WA
えー
場合分けが足りてないことに気づく
書く
WA
えー
手元で試すとまだ場合分けが足りてないことに気づく
終了

結局a abab みたいなケースは2回ですら無理だったのでまだおかしかったんですね

異常な場合分けによらない解法:
2減らせるなら2減らす, みたいな貪欲を実装すればよかったっぽい?
yosupoのコードはかなり短かった

反省:
実装方針(こいついつも同じ反省してんな(いや今回は行けると思ってしまったのがなあ... 実際もうちょい時間あれば行けたとは思う))


E,F: まだ読んでない

TCO2018 r4

開始前:
かなり体調管理に成功した
3-7-8 ...

easy:
これほんとにround4か?
何回かテストして提出

med:
とても解ける問題に見えない
よく読むとunzipしても高々hoge回と書いてある...
これほんとにround4か?
そっ閉じ

hard:
これほんとにround4か?
とりあえず手で試してみる
常にcyclicな区間になってるな
じゃあ和は行列累乗でできるので区間を求めるのが本質
今N個ものがあってT回やったときにx番目がどこに行くかという関数を作る?
よく考えると逆向きでちょっと変
じゃあT回やったときにN個ものがあるうちのx番目にいくのはどの区間かという関数を作る?
逆向きに展開していくときにいくつをマージしてできたかみたいな情報がいるから変

結局前からシミュレーションで、個数,はじめの物体の区間のはじめの値, 各物体のサイズ , 最後の物体のサイズ をもって頑張ればいけるな
間に合わず

chal:
何もできず
redが3人easy落としててたまげた

反省:
できることはわかるけど実装がわけわからん系は解けてないのと同じなのでちゃんと落ち着いて方針を考える
まあ今回はこれを意識したら一生方針が決まらなかったんですけど
だめやんけ

hard:
謎(Kankuro)
苦行(tourist)
マシなシミュレーション(Um_nik)
謎を思いつくのはかなり難しそう かなり賢い
トーナメント表みたいなものだと思うと、2回戦進出したやつの重みを1/Bにするというのはそこまで不自然ではない気がする 今度からトーナメント表っぽいのはこれを考えよう(ただ再びそれがN個並ぶっていうのが非自明なんだよなあ)

CF #499

開始前:
辛いカレーをお腹いっぱい食べてしまった
6問か

C:
まずCから開く
読めない
読めた

(8)

D:
読めた
マージテクで終わりだな
UnionFindのほうが楽かな
0になるやつの親と1になるやつの親と普通にやるとどっちになるか持てばいいな
ここで実装で何故か混乱する
今頭が働いてないのでやめたほうがいいなとなってAに行く
(35)

A:
読めない
読めた

たしかクソしょうもないバグで時間とかした、こんなのバグるか?
(46)

B:
読めない
読めた

WA on 1 (は?)
よく見るとT回しか回してない
書き直して再提出
WA on 1 (は?)
よく問題文を読むと、-1を出力してはいけなかった(下の方に書いてある intじゃないとhogehogeみたいなのを見て勘違いしていた)
AC
(65)

D:
頭が働いてなさすぎてうつ病
普通にマージテクのほうが楽なので書く
普通にかけた
(83)

E:
順位表見たらメチャクチャな場所にいたので嫌な気持ちになる
F解かれてないしEだな
データ構造じゃん
まずoのやつを含む最小の直方体を考える
それにクエリが入ったらo
xにできるかは?
そいつをoだとおもって追加したときに内部にxがいるか?
3次元点存在クエリになった
z軸をtime sweepすると、2次元で点add,長方形countになる
あらかじめ点がわかってるやつなので、マージソートのやつでいいな
ライブラリにあるので貼る
(113)

順位表見たらhack横行しまくっててこわい
見直して終了

反省:
Dまでで信じられないパフォーマンス出したのはカレー食べ過ぎたせいなのでコンテスト直前に食いすぎない(事前に食べておく)
言い訳がましくて嫌だけど明らかにパフォーマンス落ちるから気をつけないと

F:
どうせいい感じに多項式持ってFFTだろうって感じだけど、まずcutされた頂点数を固定すると割り振り方がクッソ自明になることに気がつく必要がある
これは fv(x) = fa(x)*fb(x)*fc(x)*x + 1 って感じになるんですが
とりあえずline graph ですらこれが解けないとどうしようもないのでそれを考えます
(((1*x+1)*x+1)*x+1 .. みたいな感じになってこれは自明
line graph にちょっと増やしたようなグラフだと各xの部分がなんか一般の多項式になる
(((1*a+1)*b+1)*c+1 ..
abcd + bcd + cd + d + 1
これはcd (ab+b+1) + (d+1) とかなので半分(多項式の次数の和で分けないとだめかも)ずつに分ければできる
で、一般の木の場合にどうするかというとだいたい一緒で、とりあえずHLDします
で、heavy path の部分は (((1*a+1)*b+1)*c+1 .. みたいなformで持っていく
その時light から入ってくるfu(x) は上のようにexplicitに評価する
計算量は、各heavy path の一番上でexplicit に計算するので、
vでexplicitに計算するとき、s = sz[v] とすると O(s log^2 s) でできるので
lightを降りた段数でまとめて数えると全体で O(n log^3 n)
重すぎィ!

これってこの形以外で出るのか?(出ないなら今後出たらこっからコピーしてこよう)
HLDでマージをなんとかするのは普通だけどそもそもline graph で D&C っていうのがちょっと面白かった

AGC026

開始前:
久々の? sugim回
楽しみ

A:
普通だな!
(2)

B:
見た瞬間落ち着きをなくすことを確信したので飛ばす

C:
設定おもしろい
普通にDPはできない
左半分を決めると・・・
右半分も決めて半分全列挙、できた文字列のペアをハッシュにぶち込めばOK
もしかしなくてもハッシュいらなかったね
(15)

D,E,F を眺める Dが数え上げなのでこれからやる

D:
ちょうど2個か
0,2,4だとこの前見た感じで行がflipで全て一緒になる(縦と横のxorとる)みたいな感じ
ちょうど2個だと、縦横の配列のどちらかには二連続で同じものが出てこない という条件
これで長方形だと解けた
ぐにょぐにょしてると?
階段状なら左から見れば順次増やしていける気がする
減らすのが厳しい
冷静に考えると上からだと増えるだけだな
これ実装辛くないか?(区間を列挙してマージとかする必要あるし今2個が連続してるかみたいなのもキーにいる)
まあ行けるな! (30)
とけました (93)
は?

焦って順位表を見るとE,Fともに早い段階で解かれてる
F自分が出てきたので考えようと思ったけど読んだら混乱しそうな雰囲気を感じたのでEに行く

E:
はえーおもしろい こいつ良問しか作れないのか
両方とる/とらない なので、1-Nのsubsetを取る問題
辞書順最大なので貪欲
はじめにb何個置ける?
bの区間→aの区間が完全にdisjointならおける
こういうのをとるときはindexのsubsetは連続したものしか取らなくて良い
これ全部試せるね
そうするとbbbaaaみたいなので区切れて完全に別の問題(後ろで再帰的に解く)に出来る?
よく考えると違って、bbbaaba みたいな感じでまだbが紛れ込むことがある
でもこれは絶対とったほうがいいな
もっと一般になんかb???a ってのをとったら間にあるbは絶対とっていい
始点を固定してこれを繰り返すと・・・?
うまく完全に2箇所に切れた→再帰できる
同様にa???bをとると、あいだのaは絶対とっちゃダメ
これも同様に2箇所に切れる やったぜ。(128)

流石にFは無理そう
B:
落ち着く
解けました(137)

Fの出演料を嘆願する(1pt でももらえるとすごいうれしいので)

おわり

反省: Dで見通しが甘いまま強実装を始めたこと AGCなんだからもうちょい実装軽く出来るはず(どうやるんだろう)

TCO2018 3A

開始前: touristいるやん!
easy:
自然な設定だな→
まあまず最後がAだったら流石にB負けるな→
まあd=1があるな(冷静)→
最後がBの場合は、d ≦ 10 ならBは絶対勝てるな、それ以外ならA勝ち?→
よく考えるとd=11,N=2はB勝ちだな→
d > 11 なら流石に最後から2桁目で無理なのを選べるな→
残りは d=11,N偶数. これはBが直前のAの数字を繰り返せば勝てる

med:
めんどそう→
どうせ0があると分けれそう→
分けれた→
区間では、符号と大きさを考えて大きさの方はにぶたんとかすればいいかな→
値がでかすぎるので、logを取って累積和、実際の値はmodintで計算かなあ・・・→
log2(x) ≦ 30 とかにしないとmodでオーバーフローするけどギリギリすぎて怖いしやりたくない→
冷静に考えると累積積じゃなくてsegtreeに乗せればいいな→
書く→
符号周りの方を信じられないほどバグらせる

hard:
かなりmed遅れたので速く解きたい→
なんとなくgcjっぽい感じの設定、どうせ賢い解法があるんだろう→
2-regular subgraph を取ってきてなにかする? わからん →
全域木をとって全部0にすると、その葉3つで三角形が作られてしまうと終わる→
わからん→
全域木を取ったあとのcomplementを考えよう→
たかだか次数2なので、pathとcycleしかない→
pathしかなかったとするとそれを全部1にすればおわり→
サイクルがあったら1本除いて・・・→
・・・・・・→
vertex disjoint な path集合を除いて残りが森になるようにしよう→
各タイミングでできるだけ極大なpathをとれば、サイクルが余ることはないな→
実装、提出、順位表を見に行く(残り8分?)→
冷静に考えると始点を固定しているので、まずいことに気づく(残り3分)→
書き換える、ギリギリまで悩んだあと、再提出

chal:
d=11をガン無視してるコードを一つ落とす、その後はhardの再提出前のコードが落ちるケースを作り、これで落ちそうなやつに投げる
→ 2 unsuccessful (どぼじで)
冷静になってコード読むと、dfsでbreakしていない→
じゃあ極大pathじゃなくてただのdfs木やんけ→
よく考えると僕のコードでもbreakしてないやん!(は?) 再提出の必要なかったね(結果論)→
悲しみに明け暮れながらmedの写経してたら取られた、おしまい

頭が悪いのでfull feedbackじゃないと無理。

ICPC 国内予選 2018

今年は チーム Gifted Infants としてICPCに参加します。
チームメンバーは yosupo, maroon, sigma です。他の二人が強すぎて役割が持てないことを除けばいい感じ

チーム名は確かyosupoが決めました。キッズがイキってる感を表現しています。

前日: 次の日が締切なので必死に論文を書く。雨の話を聞いて嫌な気持ちになる。

当日:
雨が降ってなかったので嬉しかった。
駒場会場で多くの久々の人に会えたので楽しかった。

コンテスト:
とりあえず印刷しに行く、初手3階に行くも結構混んでてたまげた。
帰ってきたらAが通っていてCをやっていたのでDを読む。何となく昔のICPCを感じるが冷静に考えると余裕で間に合いそうなのでCのあと書く。
yosupoが若干Bで冷えていたので、その間にmaroonがE, 僕がF,Gを見る。 Gはやるだけだが実装方針ミスると終了しそうな雰囲気を感じる。Fもうまい方針を選ばないとまずそう
Bが通ったあとmaroonがEを書き始める。その後ちょっと相談して、yosupoがG, 僕がFを担当することにした(これ良い判断だったっぽい)
Eの間にFの実装軽いO(N^2logN)がほぼ完成したが細かいところがつまってない, G も詰める段階だったので無思考で書けるところをとりあえず書く。つまったのでGに変わったらyosupoが爆速で実装していた。まだバグってるので印刷とかして互いにPCを触る。
結局Gが先に書き終わってAC。yosupoすごい。
Fもその後やっとサンプルが合ってinputに対して実行するもクッソ遅くて焦った, コンパイラオプションをいい感じにして再実行(この辺で戦犯っぽさが出てきてたがセーフだった)。通った。よかった

F,Gの間maroonがずっとH考えてて、難しいなあと言っていたのでみんなで考え始めようとしたらmaroonが突然解けた主張し始めたので書いてもらう。解法を説明してもらうか悩んだけど普通にじゃまになるのでサンプルとかを図示しておくことに。
わりとすぐmaroonが実装し終わってACしたので、すごいなあと思いました。残り10分とかだった。優勝した。

問題について:
例年に比べてどれも結構重そう(印刷から帰った時点でB:面倒そうで飛ばした C:ちょっと面倒 D:探索 E:苦行そう F:幾何 G:苦行 みたいな感じで絶望感あった) で序盤少し焦ったんですが、全体で見るとかなりいいセットだったと思います。うまい実装方針を選べば全然苦行ではない(例えばFは幾何パートはほぼない, Gはyosupoがかなり楽な方針で(というか思考停止できるサブルーチンを考えて)解いてた)というのが一つと、あと普通にHが面白かった。

優勝したので人の金で海外に行けると思うので、どこに行こうかな

CodeFestival2017 qualB F問題

F: Largest Smallest Cyclic Shift - CODE FESTIVAL 2017 qual B | AtCoder

この問題のおもしろい解法についてです。

解法1

文字列の集合を持って、「最小と最大を取り出し、この順に並べたものを新たに追加する」をやって最後に残ったものが答え.初期状態は"a"がA個,"b"がB個,"c"がC個.


解法1の正当性を証明するために、まずは次の解法を考えます.

解法2

再帰的な解法.
string solve(int A,int B,int C,string a,string b,string c) という関数を考える.
これは、文字列aを文字'a'だと思い込んで、(b,cも同様)問題を解いた時の最終的な答えを返す関数とします. なので元の問題の答えはsolve(A,B,C,"a","b","c").

内部では次のことをやります.

自明なケース

i) B+C==0 の場合
明らかにaをA個並べたものを返すしかありません.
ii) A==0 の場合
solve(B,C,0,b,c,"")を返します

まともなケース
int q = A/(B+C);
int r = A%(B+C);
string o = a*q;
if(r<=C){
	return solve(r,B,C-r,o+a+c,o+b,o+c);
}else{
	return solve(r-C,C,B-(r-C),o+a+b,o+a+c,o+b);
}

(string * int は string を int 回連結したものとします)

たとえば,
solve(6,3,1,"a","b","c") では、
solve(1,1,2,"aab","aac","ab")が内部で呼ばれ、

solve(3,3,4,"a","b","c") では、
solve("ac","b","c",3,3,1)が内部で呼ばれます.

これでちゃんとsolveが計算できていることを示します.自明なケースに関しては明らかなので、まともなケースについて考えます.

まず非自明なケースのsolveの引数a,b,c(文字列)は、次の条件†を満たします(これは再帰的に簡単にわかります *1 ).

†:どの文字列も,他のどの文字列のprefixではない.

この条件を満たす文字列集合Sに対して、一般に次のことが成り立ちます:


Sを辞書順ソート済みとしてS = {w_1,w_2,..,w_N} とする.この時、
a := w_i1 + w_i2 + .. + w_iI
b := w_j1 + w_j2 + .. + w_jJ
と置く(文字列の連結)と、
a < b ⇔ (i1,i2,..,iI) < (j1,j2,..,jJ) (添字の辞書順)

これは、†を満たしていることから、i1 ≠ j1 ならその時点でaとbのどちらが小さいかわかる ということを考えるとわかります.

これはすなわち、Sの文字列を新たに一つの文字とみなして大小比較しても同じ結果が得られることを指しています.

元の問題に戻ると、これによってsolveを再帰的に呼ぶ時に常にa,b,cを一つの文字とみなしても元の問題が解けていることがわかります.

コードの内容に戻ると、まずaをできるだけ均等に(q+1がr個,qがB+C-r個)分割しています.こうすべきなのは、aの数が連続している部分の最長の長さがより長いとfの値が小さくなってしまうことからわかります(追記:‡不十分で、aaa,aaa,a より aaa,aa,aa の方がよいことを示していない あとで説明します).

なのであとは、さっきあげた例A=6,B=3,C=1でいくと、aa?,aa?,a?,a? (の?に適切にb,cを入れて,)並び替えてfを最小化するのが目的になります.

もしaaの後に全てcを置けるなら、そうでない状態よりfは大きくなる(aabから始まる文字列がなくなる)ので、そうすべきです.すると次の文字列はaac,ab,acしかなくなるのでこれで再起します(コード中のifの方です)

そうでない場合でも(elseの方),実はできるだけaaの後ろにcを詰め込んだほうがよいです(※).すると,次の文字列はaac,aab,abしかなくなるのでこれで再起します.

※の理由:
出てきうる文字列aab,aac,ab,ac は 条件†を満たすので、1,2,3,4と置き直します.

「1,2,3,4からなる文字列sがあって、1と4が共存する場合、ある1と4が存在して、その1を2に、その4を3に書き換えることでf(s)をより大きくできる」
ことを示せば十分.

まずsの4をどれでもいいから一つ固定します.そこから(cyclicに)左に見ていってはじめに見つけた1を固定します.この4,1を3,2にすることを考えます.この文字列をtとおきます.

まず変更の結果tに1がなくなるケースでは、明らかにfは大きくなっています(f(s)は1から、f(t)は少なくとも2からはじまるので)

そうでない場合、
sのcyclic shift の内1からはじまるものの集合を考えると、これはf(s)を含みます. これらの文字列s'においては、さっき固定した1と4の間で切れることはありえません(つまり、1と4はs'にこの順に出てきます)

これらの候補に対応する(同じ分だけshiftした) t の文字列達を考えます.この集合は必ずf(t)を含みます.(tには1があり、かつ1からはじまるものをすべて含むため)

それぞれの対応するペア(s',t'と描きます)に対して、s' < t' を示します.
これが示せれば、f(t) > それに対応するs' ≥ f(s) となるのでOKです.

(s' < t' の証明)
さっきの太字の部分で主張したことから、
s' = ..1..4..
t' = ..2..3..
となるので、OK(おわり)

(※の理由おわり)

よってできるだけcをaa?に詰め込んだほうがいいことがわかったので、解法2の正当性も終わりです.

‡(aを均等にすべきな理由):
上の証明と似たような感じで、b,c,ab,ac,aab,aac,..は条件†を満たすので、aの数が偏っている(2以上違う)時は、その二つを固定してaの個数を平均化するのがいいことがわかる.

解法1の正当性

途中状態でsolve()の再帰と同じ状態になることがわかるので解法2と同じ出力になることがわかる.(ベースケースは明らか)


ちゃんと詰めたつもりなんですが、おかしいところがあったら教えてください.

*1:細かいですが、自明なケースiiによって実は満たさなくなるんですが、まあ本質的ではないです,例えば新たな引数をランダム文字列にしても良いので