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完以上が出なかったので逃げ切って優勝。
感想
本番では日頃しない実装はあまりやらない方がよい (壊れるので)、やっぱり競プロは通してなんぼなので実装力上げないとダメですね....
アジア地区も勝てるよう頑張ります。
2019-02-23
■ みんなのプロコン 2019
実は皆勤賞です、皆勤賞なんですが、オフィスまでの行き方が全く覚えられない
A
えーっ何これは.... -> まあ積分すればいいけど受験数学2年くらいやっていないため... -> サンプル合わない、どぼじで -> 飛ばす
B
流石に2つの木の直径の端4つから2個取るのがベストのはずで、それなら簡単 -> AC
C
まともにやると絶対やばいのでスマートな方法を考える -> 4つに分ければ全て長方形反転クエリになる -> Fortune Telling (JOI 2012 sc)って、知ってるかな...?僕は知っています -> AC
D
setで管理して、幅に対応したフィボナッチを掛ければOK -> 無限にバグる (行列をsegtreeに乗せるか、setに番兵を載せるのが良いですね....) (フィボナッチも相当バグらせたので頭がない) -> なんとかAC
A (再)
冷静に見るとh-aをaにtypoしてる...(許せね~~~) -> AC
E
数え上げ、数え上げなんですけど、分からない (は???)
結果
8位
感想と反省
順位に関してはADで嵌ったのが悪いんですけど、Eが分からなかったの不味いなあ (N<=100, M<=10^9の時点でそういう方向性の思考をしなきゃいけないし、良く分からないものを左から順に切った時の条件で表現する系は結構見るし、色々とダメ)
行列周りのライブラリ全然整備できてないし、「面倒なことで有名なDP」も1回も解いたことないし、課題が山積していることが分かったので良かったかな...
■ 日経コン本選
1週間前なので記憶があいまい
最寄りが後楽園だと思っていてしばらく歩く羽目になった、会場はなんか豪華な見た目をしていてすごかった
A
やる
B
制約が優しい、やるだけなんだけど遅い
C
縦横のにぶたんの変数が被っていて無限にバグった、すぐに気づいたので良いけどやばい
D
この問題の上位互換 (スタートの長さ自由、伸びるペース自由、長さの上限あり、各切断クエリごとに切断長のsumを求める) が出題されたことがあるため.... (貼りました、カス)
E
数え上げ典型、v番目が最初の埋まらない場所として考察するとdpを下から更新できる
F
ちょっと考えたけどよくわからない、飛ばす
G
少し考えると「どこかの辺までダイレクトに行き、その辺を残り反復」が良いことがわかる。
様々なパスに対してmaxを求める -> 重心分解、コストの形がax+b -> envelope -> い つ も の -> ライブラリを貼ってちょっとやる
-> こどふぉのテストで通るけどAtCoderだとCEする (どぼして) -> ちょっと直す、AC (やったー)
F(2回目)
よく考えると、動き方が限定できるので普通に1D segtreeで出来ることがわかる、頭がバグりまくってダメダメだったけど一発で通ってくれたので良かった (ちょっと複雑になると遅くなるの直したいね....)
結果
2位
感想と反省
DとかGの「ハマった」感に大いに助けられた、Eがすぐ見えたのも良かった
Hはチーム練習の時に解法が錬成されたんですがまだバグっていて辛い、誰か助けて~~
エキシビションは相手も相手だし人も多いしで相当緊張してダメダメだった、もっと図太くなりたいね
また開催されるらしいので次回は懇親頑張りたいな
■ TopCoder SRM 751
749, 750は爆発したので見なかったものとします
Easy
かなりびっくりしたが、どうせ枝狩りすれば早い系だろうと思って書いて最大ケースを投げたら0.3secだったので出した
Med
しばらく変なことを考えていたんですが、冷静になるとg^K ≡ h なるkがわかれば良いだけ、これはBSGSで出来る -> h=0だとやばくないですか?やばいね -> 出す
Hard
しばらく変なことを考えていた(xを挿入するときxの前と後ろを同時に管理しようとしていた)、もうちょっと落ち着くべき
challenge
h=0チャンスかな、いうても赤5だしな... -> +3 (問題が悪いね)
System Test
通る、1位
Rating
2479 -> 2626
感想と反省
なんか優勝してしまった... Hard解かないで勝つのあまり格好良くないのでいつかカッコよく勝ちたいですね (小並感)
真面目な話をすると、Hardはどう考えても右で左を管理するのがファーストチョイスのはずで、それで解けるんですよね... なんで思いつかないの... -> 練習、しよう!
2019-01-27
■ TopCoder SRM 748
touristと同部屋率が高すぎませんか?
Easy
本当に無でびっくりした、全く詰まらなかったのに4位で世界のレベルを感じた
Med
何故か座圧しようとしたり長方形に区切って管理しようとしたりして無限時間溶かした(最悪)、(i,j)が答に入るか?を考えたらすぐに出来た
Hard
ほぼほぼこれと同じなんですよね、なので解けます、座標が10^5オーダーであることに目を瞑る必要がありますが
challenge
TLE/MLE不可避では??みたいなのがあったけど勇気が出なかった (systestで落ちてた)
System Test
通る、33位
Rating
2634 -> 2597
感想と反省
HardがtouristだけでEasyが無なのでMedium速度+chalのみが重要だった回ですがMedでやらかしたのでどうしようもない、こういうのは事故にあったようなものなので仕方ないね