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によって実は満たさなくなるんですが、まあ本質的ではないです,例えば新たな引数をランダム文字列にしても良いので

JAG 2017 day1 (snukeセット)

Tasks - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder


A:しりとり
適当なオイラー閉路を考えてその途中までを取るとか考えると正当性がわかりやすい

B:リス
ちょっと迷走仕掛けたが、「最終的な場所」で考えればいいことがわかる

C:すごろく
動的FFTみたいなやつ(segtreeっぽい といってもいいかも)
左からDPを埋めるとして、ある区間を正しく計算する関数calc(l,r) を用意する.
calc(l,r)では、分割統治っぽく、まずcalc(l,m)を呼んで、次に[l,m) から[m,r) への全ての遷移をFFTでやって、最後にcalc(m,r)分を追加する とやればよい.

コンテスト中は面に出てくる値の種類が多い時は速く終わるからモンテカルロ とかやってました(カス)

D:くさかべ
ま、幾何ライブラリ写経したんですけどね(ここらへんもはやタイトルが全く関係ない)

E:ベクトル式
BNFを書き換えたほうがいい みたいな問題はたまにあるので、これLLじゃないよ~とか思ったら考えたほうがいいと思います

F:逆から見てにぶたんすると片方向きだけでいい.左から貪欲に取ると右方向には極小(そ)

G:2リストらしい.頑張ってグラフを作ると一般の場合でも解けるが、H=2だとサイクルができちゃうケースが限られているのでそれだけやればOK

H:

過半数がどうこう、よりまず自由度3で条件2だから一つ決めればすべて決まるというのに気づくのが重要

イベルタルってこんな動き方するんですか?(いいえ)

I:
フローに必要な辺 のやつ
正当性は簡単.
あるフローFを固定する.Fの残余グラフの(有向)サイクルに含まれない→確定(Fに含まれてる⇔かならず使う,含まれてない⇔必ず使わない)
含まれてるならそれにそって流せばその辺は消せるので、どっちもありうる.
x→y があるサイクルに含まれている ⇔ sccでa,bが同じ成分 なので余裕

J:
2WA(ha?)

K:パンプキン
一応式を書くとa+bがデカい順でOK.

ちゃんと「ん」で終わってしりとりが終了している.
最近始めたので読解がすんなり出来た.裁きの光ってカードが好きです.

yukicoder ☆5,6

何故か埋めています。解法メモなのでネタバレ注意。

☆5

42:
63:
93:

変なことをすると下から挿入できるが、普通に包除

114:
137:

特異問題です。これはむずい
1,x,x^2,..なら順番に倍数だから、modでピッタシになるようにdpするっていうのが出来たわけだが、今回はxを自由に使えるっていうのをx,2x,4x,..が1枚ずつあると言い換える。それでx_1,..,x_N,2x_1,..,2x_N,..っていう順番で使うかどうか決めていけば、各状態ではSum x_N 通りくらいしか持たなくて良い。
自由DPのときに分割するのは典型っぽいがその後こんなうまくいくのはびっくりしたなあ

214:
234:
243:
248:
263:
271:
283:

カス

284:

異なる二種類の和のmax みたいなのは 上位2種類持っておけば良い Bicycles(蝶々のやつ)とか

295:

まずこういうふうに並べるのが最適なのを示すのがアレだが、無駄に分割するのは意味がない(すべての文字でマージすれば絶対に積が大きくなる)のでOK.
あとはすごく小さいケースだけ場合分け
max制限がある数え上げでパラメーターtがあってn^tオーダーとかだとtが1,2,3とかのケースだけやればいいみたいなのあるよね

377:

Burnsideのいい練習問題だと思う.
不変な(x,y)の集合 みたいなのを考えたくなるが、ちゃんとBurnsideがわかってれば G = Z/HZ * Z/WZ の各元ごとにかんがえればいいことはわかる

382:

最大独立点集合, 乱択おもったより強いなあ(まあ乱数ガバいからまともに作ったケースだと落とされるのかな)

426:

苦行segtree

435:

無.なぜかmod 9 の世界でかけたり割ったりする時に 3^a * b (b = 1,2) の形で持っていたが,bは1,2,4,5,7,8なんだよなあ. 気をつけます

465:
474:

一時期ちょっと流行ったmod2系. Lucasの定理の拡張でmod素べきとかもあるので、困ったら使ってもいいかも(まあ愚直にやれるなら↑435みたいにやればよい).

540:

予想投稿サイトやめろ

UTPC2011

D:探索ゲーでpair<pair<int,int>,pair<int,int>>とかやるのつらいので、tupleを使う.勝手に辞書順が入ってるのでsetに入れられる

	using State = tuple<int,int,int,int>;
	queue<State> que;
	que.push({1,2,3,4});
	int a,b,c,d;
	tie(a,b,c,d) = que.front();
	cout<<a<<b<<c<<d<<endl;

E:
長さNの数列a,bがある、indexのリストを選んで、(prefix sum of a) ≤ bとなるようにせよ.という問題

まずどの順に選べばいいかが先にわかるというのが典型テク.連続する二つのswapを比べるとこの場合はbが小さい順がいいことがわかる.

なので今何個選んだかのDPで出来るんですけど、実はO(NlogN)になるらしい.

b昇順にするのまでは一緒、とりあえず貪欲に選ぶことにしていって、選んだ結果超えちゃったら、その時点でbが一番でかいやつを諦める(b昇順であることから諦めるのは高々一回であることがわかる).
証明:hoge

F:構成.帰納法

G:長さ選んで三角形→連続するように詰めれる

H:キャッシュ戦略→MCF.各sに対して[s,s+1)か[s,t)のどっちを選ぶか決められるんだけど、はじめ全部ちっちゃい方を選んでいると思うと、[s+1,t)を選んで重なりがf-1個 とみなせる,かなり特殊っぽい

I:(x==3)みたいな式が書きたいんだけど、これは(x==4)みたいな2冪にたいしてできれば良くて、でも冷静に考えるとこれはできないことがわかる,ちゃんというと、xの上の桁がyの下の桁に影響をおよぼすことは絶対にない.
なので出力のi桁目を決めるときは入力の0~i桁目を使えば良くて、(x==3?8:0)みたいなのは簡単にかけるのでOK.

J:まずN!通りのうちの数え上げになる.優先度順に見れば単純に二分木に挿入するだけになる.根が何番目か決めることでO(N^3)のDPができる.更新部分が畳み込みなのでO(N^2logN)にできる.hがでかいとこはどうせほぼ0なので、O(Nlog^2N)にできる.double版多項式まともに作ってなかった・・・

K:M≤N+500 圧縮です

L:永続