2020/01 - 04
移行後初投稿です、2020/01-04のまとめをします
Petrozavodsk Winter
やってました 現役2位だけどNNSUにはボロ負けで普通にMIPTと競っている
Moscow prefinal
つい先日やってました 同じく現役2位だけど↑よりはかなり良くなってていい感じ
2778 -> 3043
新年早々にround #614(超重要) でLGM達成してそれから当分出てません (FAKE)
2hコンの調子を取り戻したらまた出ます
2755 -> 2842
大阪に行っていた回と眠くて寝落ちした回を除いて全部出た。TCO regionalのために頑張って出てたのにコロナで消滅したっぽいので悲しい....
2944 -> 2944
AGC...? 知らない子ですね....
企業コンはキーエンス ・ ドワンゴ・(DDCC) までは調子良かったけどここ2回は酷い
その他
opencupに出たり1人ICPCしたりyukicoder埋めを始めたり
とりあえず根気が続く限りは備忘録的にメモしていこうと思ってます
p.s.
過去記事のソースコードが全部壊れてしまっているんですが、同様に過去のブログデータをインポートしてソースコードが破壊された & 治せた 方がいらっしゃったら解説方法を教示頂けると幸いです
2019-12-15
■ 第2回全国統一プログラミング王決定戦 参加記 (冬休み2日目)
正式名称をちゃんと書いてみました。
C
N^2 log N、4secとは言え流石にやばくない？と言い続けて線形解を探してしまった (AtCoderのジャッジサーバーは速い！(素振り))
E
やることは実家 (長方形sum + setで区間管理) なんですが、実装の仕方がヤバすぎてバグった... (大反省)
G
解法は簡単で実装も簡単 (完)
ちゃんと書くと、dp[u][v] = 木に辺u-vがあり、頂点uをsubtreeに加えることが決まっているとき、辺u-vを切断したときにできる頂点vを含む方の木から最適に頂点を0個以上選んだ時に辺の重みはいくつ増えるか を全方位木DPで計算 (これは簡単) し、sum[v] = dp[v][*]のsumとします。
すると、クエリ(a,b)に対する答えは、a-bパスをa-v1-v2-...-vk-bと書くと、sum[a]+sum[v1]+...+sum[vk]+sum[b]-dp[a][v1]-dp[v1][a]-dp[v1][v2]-dp[v2][v1]-...-dp[vk][b]-dp[b][vk]+(a-bパスの重み)になって、これはどれも根からの累積和 + lcaだけで計算可能です。
何も知らないけどtoptreeとかいうの強すぎる
D,F,Hはどれも教育的なので後でちゃんと解く
結果は4位でした。頭じゃなくて精進量で負けたと思えるコンテスト、最高なのでこれからも続けていきたい
今回の懇親は渾身ではなかったです (<-これはなんですか？)
2018-2019 ACM-ICPC, Asia Xuzhou D
何も考えないとdp[i][j][k]みたいな配列に対してN通りの遷移を考える必要があって4乗になりTLEする。
dp[I][J][K] <- dp[i][j][k] (a[I]=a[J]=a[K] & a[i]=a[j]=a[k] & A_{a[i],a[I]} = 1) の遷移を睨むと、
dp[i][*][*]の更新はdp[(i未満)][*][*]のsumだけ分かっていればできるので、(新たに追加されるのはa[i]なので、A_{*,a[i]}=1なる*だけ取り出して2次元累積和する) これで3乗になる。
(例えばdp[i][x][x]とdp[i][y][y] (a[i]=a[x]=a[y]) を計算する上で大きな差がない (同じグリッドの違う領域のsumを取っているだけ) ということに注目すると解けたような気もする...?)
2019-12-14
■ 冬休み1日目
2018-2019 ACM-ICPC, Asia Xuzhou Regional Contest
AGHILMを解いた。
I
LIS長がN-1の順列はそう多くはないので、それぞれを生成するような順列を直接数える。
勿論、swapが起きる所を辺で繋いだ時の連結成分ごとに考えれば良く、これは前から見る(順列全生成)と絶対間に合わないが、後ろから見る(いい感じに探索)と間に合う
M
各々の光源がどこからどこまでを照らせるかわかれば解ける。
そのためには必ず照らせる頂点を求めて、両方向に伸ばしていけば良いが、前者はユークリッド距離が一番近い点、後者はccwだけで判定可能。見た目は幾何だけど幾何ではない
L
acyclic olientationは(-1)^N * P(G,-1)で数えられるので、結局彩色多項式の一点評価ができればよい。
N <= 36なので、色が高々37種類存在する時の塗り分け方を数えれば良く、これは面倒なDPをやればできるんですが、バグります
DとJはまともに難しいので後でちゃんと解く
Codeforces Round #604 (Div. 1)
ABCを(信じられないほど遅く)解いた。
Dはまともに難しいので後でちゃんと解く
明日大事なコンテストなので早寝
2019-12-13
■ 冬休み0日目
今日から練習した問題を記録します。
Codeforces Round #604 (Div. 1)
ABCDEを解いた。
C
checkpointで区間に分けると値の増え方はかなり単純で、segtreeに乗るのでできる
D
「(,)の割り当て方全てに対して深さの総和」= 「(が入りうる場所について、(左の(の個数) < (右の)の個数) になる割り当て方の総和」になるので、これは二項係数の累積和を計算しておけばO(1)
E
どう見てもフローなのでその方向性で考えると、「サイクルになっていない」 <=> 「出次数が2になる頂点がただ1つ存在」なので、各頂点について出次数 choose 2の総和を最小化すれば良いことがわかる。これがmincost maxflowで解けるのは典型
DDCC2020 予選 F
本番誤読したやつ。
W,TのgcdとH,Tのgcd分同じ問題を解くことになるので、前処理でgcdで割る。
前処理後はT = 1として考えて差し支えないので、実験したり予想したりすると答えが求まる (雑)
2019-11-04
■ ICPC 2019 Bangkok regional contest 参加記
経緯
アジア地区の日程のうち実習・試験・個人的な都合と無理なく両立できるのがバンコクと台北しかない -> 台北ワクワクらしいしNTUいるしバンコクだな！
コンテスト前
(-11/1 生理学 やばい たすけて)
11/1の夕方に成田で集合、11/2の深夜にバンコクに着く。
空港直結のホテルに泊まり、翌朝タクシーでチュラロンコン大学に向かう。
この日はopening ceremonyとpracticeがあった。opening ceremonyはチュラロンコン大学の紹介とかタイの偉い人の話などがあったけど、よく覚えてない (ごめん)
会場は横浜とは違って大学の小さい教室に10チームずつを割り当てる感じになっていて、practiceと本番で教室が変わった(!?) ので、使うキーボードも変わった (!?!?!?)
Cafe Mountainがpracticeから異常な速度でびっくりした。
夜は現地で人気がありそうなシーフードレストランに行って贅沢した。試しに東南アジアっぽい料理を頼んだら異常な辛さで全員の口が大変なことになった。
22時くらいに就寝した。
コンテスト
順位表がrandomized (????) されている、14問 (????) ある、問題文が壊れている、ジャッジが壊れている などかなり異常コンテストだった。問題そのものはそこそこ面白かったような気もする。(パクリ疑惑はあったけど)
最初にDに着手して、バグを埋めてWAを出す。
Mを解いて、Bも1WAの後通る。
Fを書くとこれも落ちるがDのデバッグが優先だったので無視していたらリジャッジでACになった。
IはWAが出たあと原因を考えていたが、mod 10^9+7で答える、とのclarが来て通る。(意味不明)
Dも原因がわかり無事通る。
この次はA / G / Kを3並列でやって通す。
その次はH / Nを着手したが、どちらもミスりやすい系の問題でかなりハマって時間を食った。ここまで10問通ったのが258分。
C / Lは解法が出ていたが、Lの実装を始めた裏でCは間に合わなさそうということでJにスイッチする。
数学をしたり実験をしたりして解法ができたので、急いで実装し何とか297分 (3分前)に通る。Lは通らなかった。
コンテスト総括
かなり冷えたが、それでも明らかに重い3問以外は通せたので多分2位だろうとは思っていたが、かなりヒヤヒヤした。（蓋を開けて見たらJのACがなかったら4位だったことが分かり、実際ヤバかった)
Cafe Mountainは強すぎた。opencupなら(一部を除き)どれも低~中難度なのでLGM 3並列でガンガン潰されるとまあ勝てないよね...
序盤に順位表情報がないせいでFとかKとかの秒殺ゲーを後ろで解いていてかなりダメダメだったし、問題把握をちゃんとやることの大事さを学べた。
コンテスト後
closing ceremonyは偉い人の話もそこそこにYes/Noが始まった。
特に溜めることもなく淡々と公開されていき、2位であることがわかる。上とも下とも完答数が違うので(ペナルティ的に)ガバガバムーブが結果に影響しなくて安心した。
結果発表が終わると、普通に各チーム帰り始めて大会が終わってしまった。交流イベントが全くなくてびっくりしたが、まあしょうがないね。
最後に2位の賞金で30000 THBを(現金で)もらって富豪になった。(やったね)
ガイドさんと別れたのち、ショッピングモールを観光して夕飯を食べて空港に向かった。タクシーに1時間弱乗って205THB (740円くらい) しかかからないのは日本人からすると信じられなかった。
深夜の飛行機で帰宅した。
総括
旅行自体は突貫だった割に本当に順調でトラブルは全くなくて良かった。コンテストは不調でトラブルだらけだったけど、最低限の結果は出せたので良かったと思う。反省点はちゃんと今後に生かしたい。
横浜は勝つよ (強気)
2019-09-29
■ 第1回 最強コン 決勝
実家から2時間半電車に乗って新橋に行き、中高の部活の後輩にばったり会って会場まで連れて行ってもらう。
席がめちゃくちゃ狭くてびっくりした。隣がDEGwerさんだった。
コンテスト
A
和でペアを管理して、2つ以上見つかったら終わり -> 要素が被りませんか？ -> 数列がdistinctなので大丈夫 -> FA
B
やることはすぐ分かったが実装に時間がかかる
F
O(N^3)では確実にできて、高速化しないといけない -> 区間を伸ばすのはO(N)でできる、縮めるのも戻すDPでO(N)でできる -> Moだね
D
解法は先に出ていたので実装をするだけ、凸関数の極値を求めるのに傾き二分探索してバグりそうで怖かったけど大丈夫だった
C
ちょっと手を動かすと左右に分ける方法が一意に決まることがわかる -> multisetでゴリゴリ (番兵を入れておくと楽)
G
Eの地獄のような解法を思いついていたがやりたくなかったので考えたが、できなかった (想定解と同じ解法を考えてたが、根を消すと部分木たくさんに別れちゃって手に負えないな〜って棄却してしまっていた、なぜ？)
E
地獄のような解法を書く、SA+LCPライブラリがlog2乗で遅いので速いのを探すはめになったし実装もバグりまくるし涙が止まらない.....
G (再)
よく考えるとマージテクでできそうなことに気づくが、実装が全く間に合わない
結果
3位
コンテスト後
いつも以上に人と話せて楽しかった、渾身の懇親 (ふふっ....)
感想
コンテストもコンテスト以外もかなり満足度高めだった、でもいつかは雲上人バトルに割って入りたいね
オンサイト楽しいがちなのでもっと増えてほしいな〜〜〜
ICPC 国内予選 2019
3度目の正直で優勝しました！！ (嬉しい)
チーム編成
yutaka1999 (2年), yokozuna57 (3年), HIR180 (3年)
本番
Aをやる、1回目の提出でプログラムのところに変なファイルを送ってしまい (その時は気づかなかった、) 2回目の提出の時心臓が止まる。
落ち着いて3回目の提出をしたら通る。
続いてBをやる、終わるとDが出来ているのでDの実装の間にCを詰めて、DとCが通る。
Cが終わるとFが出来ているので (！？！？)、Fが通る。
Eの実装が始まって、GとHを考えると、Gはパターン数が少ないから遷移先を持つみたいな感じで出来そう、と解法を伝えられたので実装することにする。
Gの実験をしたりEのデバッグをする、ほどなくEが通る。
Gの実装をする、書き上がってコンパイル通ったが配列の確保の仕方が下手で永遠にセグフォする (パソコン弱者やめろ)
6完のまま終わり、7完以上が出なかったので逃げ切って優勝。
感想
本番では日頃しない実装はあまりやらない方がよい (壊れるので)、やっぱり競プロは通してなんぼなので実装力上げないとダメですね....
アジア地区も勝てるよう頑張ります。
