olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

第4回アルゴリズム実技検定 感想+解法

序盤の問題の読解や細かい設定がつらい感じで序盤でかなり時間を使ってしまった。反面後半の問題で詰まることはあまりなく、全体としてはスムーズに解けたと思う。(100分41秒)

 

A:vectorにpair持たせてソートした。

B:100倍した。

C:全探索

D:左、右に絶対に行く必要のある回数の最小値がそれぞれ分かる。それでカバーできているか判定する。

E:全探索

F:mapに突っ込む

G:全探索

H:全探索を累積和で高速化

I:全探索と累積和とにぶたんで高速化

J:超頂点用意してdijkstra

K:各数列について転倒数と各数字の数を求めておく。数列に数列を追加する度にそれら情報を使って加算、更新する。

L:偶奇クエリと一点クエリを分けて考える。隣接する要素の差(ただし、添え字が奇数のものから偶数のものを引く)をmapに突っ込んでおく。

M:LCA+imos+マージテク

N:dp[i行目まで見て][i-2行目のbit][i-1行目のbit][i行目のbit]のときの通り数を上から更新していく定数倍軽めのO(2^{4W}*HW)の解法をとりあえず書いて高速化するか~って言ってコードテストで最大ケース試したら間に合ってしまった。

O:dp[i番目まで開錠したかしてないか決まってて、i+1番目以降施錠されているときの]=利益の最大値にi+1番目以降の宝箱による利益の総和を足したものを持っておく。人を右端でソートしてセグ木で更新。

ICPC国内予選2020

出ました。結果は5完で7位!nocowの5位には及びませんでしたが農工大記録に迫る好成績でした!アジアでも頑張ります。

 

 

f:id:olphe:20201106213433j:plain

 

A:一瞬で通ってた

B:一瞬で通ってた

C:1/2乗と1/3乗までの約数列挙すれば全探索できることが分かったので、即2分(120秒)探索を書いた。多分FA

D:二人がある程度考察を生やしていて、僕もちょっとだけ考察投げる。Div君がうまく実装してくれそうだったので実装を投げる。爆速で通してて4問分のペナは1番軽かったっぽい。

E:ふぇりんといろいろ喋ってるうちに30*30を4つに出来るね~とか、ドミノ並べるやつに似てるね~って言ってた。15*60を4つにするの賢すぎない?参りました。

F:ちょっと前にこどふぉで似た問題を見たので、ふぇりんと喋りながら詰めていくと解けた。

Undo可能UFで辺を軽い順に消していって、連結成分が最大じゃなくなった頂点集合を潰していった。

G:フローっぽいねって言ったら残りの二人がいろいろ考えてくれてた。

H:不可能って言ったらふぇりんも不可能って言ってた。

 

終盤までATELIERが死んでて大変そうだなあって言ってたら一瞬で2問通しててすごかった。

 

大学別4位でした。上三つはまあ無理。会津東北大阪に勝てたので満足です。

文句のつけようがない成績で素晴らしかった。アジアも勝ちたい。

 

 

去年は予選落ちだったので本当に良かった。MCC民は毎週練習に付き合ってくれてありがとう。

模擬国2020

出ました。

 

ライブラリは、どうしても自分のを使いたいものだけ印刷して、他は他の人に任せるか!wという気持ちで準備した。他の人どうしてただろう。(は?)(模擬国のあとでふぇりんライブラリを共有することになった)

Discordのサーバ(?)立てて各問題用にチャンネル用意した。

 

最初はDiv君がA,ふぇりんがB,僕がDCを担当することにした。

 

A,Bがいつの間にか通ってた。

C,どのセンサーが邪魔になるか判定するの無理じゃんって言って困ってた。あるセンサー範囲に入ってるのは連続で1回だけなので、入るタイミングでだけカウントすればよい。imos

 

D,人々が嘘を言いまくっていたが、僕とDiv君がほぼ同時に独立に解法出してておもろかった。こういう時よほどでなければ実装奪うようにしてるので実装する。

 

E,ずっと安定集合が云々って言ってた。終了30分前ぐらいにDiv君が2-SATって言ってふぇりんが通してた。助かる~

 

F,Eの裏でこっそり考えてた(は?)回転と展開図からの復元が出来れば良くて、回転は楽だったからいけるな!って言ってたけど復元が地獄方針引いて死んだ。

 

G,考えてない。

H,考えてない。

 

ととりにゃあたちに勝って笑顔になった。ありがとうととりにゃあ。

 

2円の共通接線

中心が(0,0)にあって、半径がr_1である円1と、中心が(x,y)にあって、半径がr_2である円2の共通接線を求めたい。

 原点を中心に回転させて、回転後において接線が常にx軸と平行になるようにしたい。またその時、接線があるとすれば、y=\pm\ r_1である。

更に、円2は接線の上側にある場合と下側にある場合があって、回転後の円2のy座標は\pm \ r_1\pm \ r_2である。

rad回転して、円2のy座標の条件を満たせる場合常に接線は存在していて、y= \pm \ r_1-rad回転させたものが回転前の円1と円2の共通接線となる。

 

ACPC2020day1準備

農工大セットを作りました。

やったこと

立命館の人に枠頂戴って言った。くれた。

日程決めるのに会津の人と北大の人と話した。

原案はgoogle スプレッドシートとhackMDで管理して、データセットとか問題文はgithubで管理した。 こういう技術的なやつ何もわからんかったんだけど、くれそんとかふぇりんが(準備して/教えて)くれて助かった。

セットについて

A:合宿のA問題っぽくなって好き。

B:これ正直かなり難しいと思ってるんだけど、解法聞いてたまげた。

C:writerした。結構コーナーケースがあると思っていて、testerが七転八倒していた。これテストケース作るとこまでかなり昔に終わっていて、直前に解きなおしたらはまってキレた。

D:い つ も の

E:TLEめっちゃ出ててウケた。

F:フローの押し戻しめんどくさいらしいけど、二部グラフなので簡単にかけて楽しい。

G:時間経つにつれてなんでここに置いたのかわからなくなってきたけど適切っぽくて良かった。

H:writerした。設定が変わりまくって大変だった。読みにくかったのはごめん。コーナーケース6個ぐらいあったり、片方のルールだけやるTLE解書くのしんどかった。(先に(MLE/RE)になるので)

途中Gまでしかない状態で(Hは設定変わりまくってる途中)hecさんにテスト頼んだら4時間半で全完されたので、90分で7完するチームもそこそこいるであろうことが予想されてかなり焦った。(実際に2チーム(?)がやった)

校正について

堅い文章書けなくてごめんって言いながらねちねちミスだけ指摘してた。

Japan Alumni Group Summer Camp 2015 Day 3

Japan Alumni Group Summer Camp 2015 Day 3のバチャをやった。6完57011ペナ

 

B:

シフトの仕方は以下の4通り

・右シフトのみ

・左シフトのみ

・右シフトした後左シフト

・左シフトした後右シフト

各位置について自分より右にある1の中で一番左にある1の位置を持っておくと良い。

 

D:

和が10^nより大きくなる場合と、小さくなる場合に分けて考える。

大きくなる時

和が9より大きいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを昇順にペアにして後ろに置くことで。最初に決めたペアに対して最小な和が作れる。

 

小さくなる時

和が9より小さいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを降順にペアにして後ろに置くことで。最初に決めたペアに対して最大な和が作れる。

 

ペアの数は高々100個なので十分全探索できる。

 

E:

gcd(a,b)でcが割り切れなかったら-1

cがaかbと等しいなら1

a,b,cをgcd(a,b)で割っておく。

 

aからbに注いでいくことを考える。

操作を(a+b)*2+1回行うと1周し、aもbも空になる。

逆の操作をしても同じ。

拡張ユークリッドの互除法などでどのタイミングでcが登場するか調べる。

 

F:

角度の制約を考えると、N角形のときに直角にできる角の数kは

k<(2n+4)/3

となる。また、実際に上限が達成できる。

 

J:

自分の約数kについて、(N-k)/kの約数の数が分かれば良い。

AGC044-C Strange Dance

ある桁は自分より小さい桁に対して影響を及ぼさないので、操作後の下i桁目について、操作前の下i桁の数によってのみ決まる。

 

 

サルサが流れると、すべての桁が変わる。(0のときは変わらないが、変わると考えても困らないので変わると考える。)

サルサが2回流れると元に戻るので、圧縮できる場合がある。

ルンバが流れると、一番下の桁は変わる。また、下i桁目で繰り上がりが発生したときに下i+1桁目が変わる。

 

p(i,A)を、下i桁がAであって、ルンバによって下i桁目で繰り上がりが発生した時間の集合 と定義する。

 

操作前の下i桁がAで、操作後の下i桁目がどうなるかを考える。

ルンバによって下i桁目が変わるタイミングは、p(i-1,A % 3^(i-1))が分かっていると分かる。それらの間にあるサルサの数は累積和などで分かるので、シミュレーションにはp(i-1,A % 3^(i-1))回ぐらいかかる。

 

pのサイズの総和はO(N*|T|)なので間に合う。