HIR180's diary

ICPC World Final 2020 を目標に競技プログラミングをしています

ICPC 国内予選 2020 参加記

チーム___ KING ___ (yutaka1999, maroonrk, HIR180) で参加して、優勝しました。

f:id:Hiro180:20201107003558p:plain

全完! (3年ぶり2回目)

 

メンバー紹介 (国内予選2020ver)

yutaka... メインコーダー。基本的に何でもできる。

maroon... 何でもできるが、現状唯一の幾何担当なので、後ろに露骨に時間がかかりそうな問題 (主に幾何) があった場合、まずそれを倒す。 

HIR... 他2人を補う形で、主に面倒な問題を担当する。

 

やっぱり全完を目指したいという共通の意思があったのでこのような分割になり、

実際に模擬国内でmaroon幾何ワンポイントがハマって全完できたので本番もこの形になりました。

(僕はと言うとサイコロで炎上してチームメイトを冷や冷やさせていました -19980412点)

 

 

本番

皆自宅から参加。

最初見てHIR: A, yutaka: B, maroon:Hからスタートする。

次に僕がCを解き、

Dが構文解析の見た目をしているので、師匠のEと交換して取り組む。

Dの中身は普通の問題だったが、計算量見積もりが甘すぎて実行に無限時間掛かるコードになってしまったので、とりあえず合っていると信じて既にEFを終えた師匠とGを考える。

Dを何とか通し、程なくGの方針が立ち、2人でフローのグラフ作りと、辞書順最大のための微調整を分担することにする。

割と時間がかかってしまったが、コンパイルが通った後はすんなりACできてほっとする。

最後に、maroonがひたすらHと格闘しているのを応援してたが、残り8分辺りで突然1個目のケースが通った、と言ったのでかなり盛り上がる。

それから間もなくして、全部の問題が緑に光って勝利を確信。やったぜ。

f:id:Hiro180:20201107005310p:plain

これすき

最後に一通り問題を振り返って、国内予選は終わりました。

 

 

感想

個人的なパフォーマンスは良くなかった (HELP!!) のでチームメイトにひたすら感謝です...。

来年3月の横浜までにまたコンディション作って頑張りたい。予定では6月にUT a.k.a Isで臨むWFもあるしね。

ここまで読んで頂き、ありがとうございました。

 

 

 

 

追記

進級が掛かったCBTが2週間後に迫ってるので熱烈QB精進しないとヤバくて困っています 誰か助けてください

TopCoder Algorithm Target になりました

この前のTCO 2020 Round4のレート更新でTopCoder Algorithm Targetになりました

 

f:id:Hiro180:20200915202949p:plain

このマークが自分の名前の左にある事への違和感が凄い...

 

f:id:Hiro180:20200915195824p:plain

灰からTargetになるのは結構珍しい気がする?

 

f:id:Hiro180:20200915200121j:plain

ランキング17位 (TCO2020 R4直後)

 

2012年9月に競技プログラミングを始めたときから最終的に到達できたらいいな、くらいの気持ちでTargetになりたいという思いを持っていましたが、本当に達成できるとは思いませんでした。

僕が競技プログラミングに触れ始めたころはCFは頻繁に遅延 & 鯖落ちする黎明期のサイトで、(直近のラウンドが#670ですが、僕が初参加したのは#139) AtCoderにはそもそもレーティング制度がなく、SRM一強の時代でした。 (今では考えられないですね....)

当時は (JOIも目標にしていましたが、) SRMで赤くなることを目指して頑張っていました。2014年6月に最初に赤くなって、このまま順調に上がっていくかな?と夢を見ていましたが、実際は受験勉強のブランク等々で滅茶苦茶なことになっています (↑のグラフ参照.)

大学に入って、夏まではバイトや部活を頑張っていましたが、もう一度競プロに打ち込みたいと思って秋からはかなり集中して精進する日々を過ごしました (↑のグラフを見ても2017-18の上り幅が凄い)
最近ではICPC WFが延期になってしまい、また上位との壁を感じることが多く、大学も忙しくなってきてしまったので昔ほど時間を取れなくなりましたが、その中でなんとか這い上がって目標を達成できたのはとても幸福なことでした。

スピード + 確実性の比重が重いSRMが比較的得意と自己評価していますが、実際最近はある程度自信を持って出したものはほぼ通っていたので、(R4の既出も含め) かなり上ブレしてる感じです。今後は落ちることも当然あると思いますが、落ちても戻ってこられるようにもう少し地力を上げていきたいです。(あと1年?くらいロスタイムがあるので、まだ伸びると信じています)

 

最後に、後日オンラインでTCO Finalに参加するので、出ただけで終わらないように、見せ場が作れるようになんとか食らいついていきたいです。

TopCoder Open Round 4

試験に追われていたら2日も経ってしまいました。

TCOのprefinalのラウンドはサボったり出られなかったりで2年ぶり2回目です

 

Easy

少し考える、幅を決めて端から埋めていく感じでいいんじゃない (思考停止)

書いてサンプルを通して出す、ここで冷静になって8 8 6 54とかで落ちることに気づく (なんで?)

右上から左下への折れ線で区切れるような形にはなることが示せるので、素直にDPして復元する (が滅茶苦茶バグる)

 

Hard

基本前から解いていくんですが、出遅れた & 解いてる人が多い & 高い点の人が多いのを見てHard開けを決意

この形の遷移見たことあるな... と気づいて

https://codeforces.com/contest/325/problem/E を思い出して、通す (既出判定大丈夫ですか?) (とはいえ7年前のCF・3年前のPetrozavodskで既出と言われても気づけるtesterは多くなさそう....) (この回は実際に参加してたので覚えてた)

 

Med

これ通せば通過ワンチャンあるなと思って開くと、割とすぐ方針が見えたので頑張って実装する (桁数と違う場所と桁の値を決め打てばとても単純な桁DPになる)

ぎりぎりでサンプル全部通ってガッツポーズする、出す

 

Challenge

特に考えてなかったので全然落とせない、落とせそうなのを写経するも全部通って悲しかった

 

 

全部通ってooo +0/-0 3位、TCO Final進出2888 -> 3008 (+120) でTopCoder Algorithm Target になりました。

f:id:Hiro180:20200908225416p:plain

ICPC延期になってしまったのと大学の試験がやばいのでモチベが上がらなかったけど、思いがけない形で長年の夢が叶ったので何だか不思議な気持ちです。

とりあえずTCO Finalと来週のFHC R3に向けてまた頑張ります。

 

(ポエム編に続く)

 

 

東京海上日動 プログラミングコンテスト2020

https://atcoder.jp/contests/tokiomarine2020

↑tokyoじゃなくてtokioなんですね

 

A

B

注意力が本質かな~やっぱ

C

0, 0 \cdots, 0から始めて何が起きるかに思いを馳せると思考要素が無いことに気づくことができる

D

木上のナップサック問題とかあったな~と思い出しながら考える、がとてもじゃないがdp的な方針では解けない

普通に半分全列挙だな~という気持ちになるが、ソートいるし困るな~

冷静になると上半分の候補は少ないから、そこだけ計算結果を持ってやればいいのでは?と気づく 2^A未満を前計算するなら雑に見積もってO(4^A \log + Q N \log / 2^A)

A=10で組んでテストすると普通に間に合いそうなので出すと通る

E

適切な前処理をすればS=0, T=2^k-1の問題になることはすぐわかる

この見た目で包除しないわけないので、どうやるかを考えると、bitごとに全部等しい / そうではない に分けるのが筋が良さそうとわかる

包除の計算で何が必要かと言うと、b_1,\cdots,b_k 番目のbitに注目してそれがc_1,\cdots,c_kになるような個数を求め、適切な場合の数を掛ければよい

b, cを全部試すと3^{18}がついて終わるが、少し考えるとbを決め打ってそのbitだけ抜き出した値ごとに分類すれば十分高速に解ける

F

対称性を使って左の辺から1点、上下の辺から1点ずつ取るパターンに帰着する

色々考えると、上下の点を結ぶ辺の傾きが同じであれば、内部の点の個数は右に行くほど増加することがわかる。

(理由: 1動かすと面積は\dfrac{H}{2}増えるので、ピックの定理より周上の点がHより多く増えなければ減少することはないが、そうはなりません

(もしそんなことがあったら、直感的に嫌な気分になります。))

ここからは、コードテスト上で熱烈枝狩り+定数倍改善で頑張る。何が最大ケースかわかりにくいが、この方針だと1000 100000 100000とかが遅かった。

 

なんか久しぶりに順調に問題が解けて満足したので競プロ最高~~の気持ちになれて良かったです

 

p.s. https://atcoder.jp/contests/tokiomarine2020/submissions/14247904 高垣楓さん誕生日おめでとうございます!

NOMURA プログラミングコンテスト 2020

https://atcoder.jp/contests/nomura2020

5月の個人コンテストはこれが最初で最後となりました (?????)

 

A,B

C

アップダウンとボトムアップを組み合わせるとそれっぽい貪欲になることはわかる

「正しそうだけど示すのむずいな~」と「600点ってこんなに単純でいいの??」の間で揺れて時間が経ってしまう

F

書き換えは1か所だと思っていたので 違う箇所が1つ以下 or 2つの0/1が頭にくる or 違う箇所が2つで0/1 1/0 という条件になり、全く解けない

よく読むと回数は任意なので、1/0があったらそれ以降は等しい だけに言い換えられる

等しくなる部分を圧縮しながらDPすれば良くて、式を整理すると2乗

D

いろいろ試すとループの個数に着目すると解けることが分かる むずいね

(連結成分に注目したり木の数え上げに帰着しようとしたりしませんか?僕はしました)

感想

日本人7位、DF数え上げなのに滅茶苦茶手間取ってしまって辛かったが、問題は面白かったです

6月はちょっとずつ練習してこのブログも更新していきたいと思います

2020/01 - 04

移行後初投稿です、2020/01-04のまとめをします

 

Petrozavodsk Winter

http://karelia.snarknews.info/index.cgi?data=macros/results&menu=index&head=index&round=09&class=2020w&sbname=2020w

やってました 現役2位だけどNNSUにはボロ負けで普通にMIPTと競っている

 

Moscow prefinal

http://prefinal2020.workshops.it-edu.mipt.ru/index.cgi?data=macros/amresults&menu=index&head=index&round=22&sbname=mipt2020f&class=mipt2020f&rid=1

つい先日やってました 同じく現役2位だけど↑よりはかなり良くなってていい感じ

 

codeforces

2778 -> 3043

新年早々にround #614(超重要) でLGM達成してそれから当分出てません (FAKE)

2hコンの調子を取り戻したらまた出ます

 

TopCoder SRM

2755 -> 2842

大阪に行っていた回と眠くて寝落ちした回を除いて全部出た。TCO regionalのために頑張って出てたのにコロナで消滅したっぽいので悲しい....

 

AtCoder

2944 -> 2944

AGC...? 知らない子ですね....

企業コンはキーエンスドワンゴ・(DDCC) までは調子良かったけどここ2回は酷い

 

 その他

opencupに出たり1人ICPCしたりyukicoder埋めを始めたり

 

とりあえず根気が続く限りは備忘録的にメモしていこうと思ってます

 

 

p.s.

過去記事のソースコードが全部壊れてしまっているんですが、同様に過去のブログデータをインポートしてソースコードが破壊された & 治せた 方がいらっしゃったら解説方法を教示頂けると幸いです

2019-12-15

第2回全国統一プログラミング王決定戦 参加記 (冬休み2日目) 01:03

正式名称をちゃんと書いてみました。

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を取っているだけ) ということに注目すると解けたような気もする...?)