Hatena::Grouptopcoder

Hiro180の日記

2019-02-23

みんなのプロコン 2019 02:43

実は皆勤賞です、皆勤賞なんですが、オフィスまでの行き方が全く覚えられない

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回も解いたことないし、課題が山積していることが分かったので良かったかな...

日経コン本選 02:33

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 02:21

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はどう考えても右で左を管理するのがファーストチョイスのはずで、それで解けるんですよね... なんで思いつかないの... -> 練習、しよう!

BonnieserBonnieser2019/05/23 02:12https://www.pinterest.fr/brawlstarsgenerator/instagram-free-followers-2019-generator-may/

Free Instagram Followers Apk 2019
Free Instagram Followers Trial 2019

2019-01-27

TopCoder SRM 748 16:03

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でやらかしたのでどうしようもない、こういうのは事故にあったようなものなので仕方ないね

2019-01-20

DDCC 2019 01:30

Eの配点の1200(600+)に不穏を感じてしまった

A

-を>に変えると ・>列の長さが+1 ・長さ1の>列が登場 ・>列同士を繋ぐ のどれかが起こる -> これは頑張ればできる -> AC

(実は3番目は考える必要がありませんでした、問題文はちゃんと読みましょう)

B

1,2,...,kの順番はどうでもよい、k+1,...,nをどこに挿入するか? -> (0 or 1) + (0 or 1 or 2) + ....みたいにしてRを達成すれば良い -> もしRが表せるなら大きい方から貪欲に引いて作れることが有名 -> dequeでやる -> AC

C

は? -> 後回し

D

どう見ても実家、segtreeでできるのは知っているので、行列とベクトルまわりの積を頑張って書く -> AC

E

(パスの長さがp_1,...,p_qにならないといけないことを読み落として)これ自明では? -> textで出してWA -> 誤読に気づく、こんなのできるわけなくない? -> 断念

C

別にできない幾何ではないのでやることにする、全く慣れていないので実装が滅茶苦茶になるがなんとかAC

E

N=O(Q)からオーダーが落ちません....

結果

8位、Eが出来る人天才すぎる

感想と反省

幾何と構築ゲーが2大苦手ジャンル (ex. SRM 746) なので、当然といえば当然の結果な気がする....

幾何はICPCのためにやらないとダメなのでまあやることにして、回避不能な構築が出るとコンテスト終了するのかなり腹が立つのでそろそろ真面目に対策するべきなのかもしれない (どうやるの?)

2019-01-19

TopCoder SRM 747 02:57

DDCCと順番入れ替わるけど終わったばっかりなので許して

Easy

問題を把握する、N=2ならなんか適当に選べばよい、Nを1つ増やすと何が起こる? -> 今あるものと足してdになる個数最大を付ければ良い? -> 0とdがあると壊れるけど、最初に0とd以外を選べば絶対大丈夫 -> 出す

Medium

max固定DP以外で解けるものではないため -> long doubleとはいえ精度が怖いのでちょっと工夫して前計算をする -> 出す

Hard

区間DPをすれば解けるがそれはオーダーが壊れる -> プロットする -> 右下へのLISをやればOK -> x座標順に見ていくと、BITをノードにもつsegtreeがあれば良いから、できる -> 出す (上位陣速すぎませんか?)

challenge

System Test

通る、5位

Rating

2562 -> 2634

感想と反省

Hardでもたついた以外の反省がないけどMedもちょっと遅いし全般的に速度が足りないのかなぁ (比較対象がトプランなことには目を瞑る)

BITをノードにもつsegtreeはそろそろ良い感じにライブラリ化したいね

2019-01-16

TopCoder SRM 746 18:35

新年初コンテスト、何故かtouristとPetrと同部屋に入れられて死を覚悟する

Easy

問題文が本当に分かりにくい、頑張って読むと全点間の距離が元のグラフと全て異なるグラフを構成すれば良いらしい

-> 1 / 2以上 は直接繋がるかどうかで分かれるんだから補グラフを出せばOKね -> 出す

Medium

構築だけどこれはDPから復元するタイプに見えるのでそこまで苦手ではないはず -> 何度か嘘をやる -> 最終的に、(ab)*n bb (ab)*m bb (ab)*kみたいにすると、n*n + m*m+m + k*k+k になることを使ってDPしたら全部構成できた、テストを真面目にやりすぎて凄く遅い

Hard

やることは平行なら平方完成するだけ、平行じゃないなら法線ベクトルを求めて平面と点の距離の公式に代入するだけ -> 出す

challenge

PetrにHard落とされる (そう....)

System Test

前2つは通る、35位

Rating

2605 -> 2562

感想と反省

"Changing this to long double and just hoping it will pass is a risky strategy" じゃないんだよね、とは思うもののICPCでは普通に出るレベルだし__int128かpythonか多倍長ライブラリ

Mediumが遅いのはテストに時間かけ過ぎたのと嘘をやったタイムロスだけど、こういうのは方針ガチャだししょうがないね