Hatena::Grouptopcoder

Hiro180の日記

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

2018-12-31

2018年の目標振り返り 20:20

  • SRM, CF レート 2700

  • SRMは2605 (MAX: 2646)、CFは2918 (MAX:2918)でした。 SRMに関してはHardを5-10人くらい解く回が多くて、そういう回にEasyMedしか解けないと1桁順位が取れないので2600近辺で停滞しています。
    ちゃんとHardを解けるようにならないと大きく上げるのは無理だし逆にそれができれば一気に上がると思います。
    CFは完全にインフレしているんですが、(バーチャルを含め)外れを引かなければかなり上位に入れることも増えてきたので形式が得意なのかもしれません。

  • AtCoder レート 3200

  • 2989 (MAX: 2989)でした、夏場までAGCでやらかし続けて恐怖症を発症してたのでしょうがないね。
    直近3回は14位->45位->21位なのでだんだん自信がついてきました。

  • 国内予選かアジア地区どちらかで優勝する

  • 3位と4位です。(去年より悪くなってないか?)(ごめん) どちらも戦犯をしてしまったのでICPC練習をしていかないといけない......

  • 研究室でまともな結果を残す

  • これも完全にごめんなさいで、あんまりコミットできなかった (来年はやるぞ)

  • Deep Learning系で何かいいインターンを探してやる

  • PFNに行きました、パソコンに少し詳しくなりました (詳細は秘密です)

  • 生活リズムをまともにして授業に出る

  • さすがに二十歳にもなると自分の人間性がわかってきたので今後この手の夢物語を語るのはやめます

Good Bye 2018 10:10

5年ぶりにGood Byeに出ました、前回は+168してるらしく相性が良いと信じたい


コンテスト開始、前から潰す派なのでAから順に見ていく

A

流石にやるだけ、制約に優しさを感じる -> pass

B

ちょっと考えて、sumを取って/nするだけでよいことがわかる、がintだと溢れるね -> pass

C

本質はgcd(x,n)だからnの約数を見ればOK、典型 -> pass

D

そのものと、跨るものを数える必要がある -> 跨るものって1....nのpermutationじゃないとダメじゃない?

-> なんで? -> 差分が 負 -> 正(max-minが足されるので) -> ..(足される値は単調減少).. -> 0 になってるからだね -> pass

E

次数列としてvalidか判定するのはUSACOとみんプロでみた -> みんプロの解説pdfを見る

-> 追加するものが0...n各々に対してlogくらいで判定できればOK -> どこに入るか分かれば、左と右の値の変化は簡単にわかる (実装は楽ではない) -> .... -> pass

F

飛べるのはLだけだと思ってて自明すぎるだろって思う -> テストすると合わない(それはそう) -> 誤読に気づく -> うーん、よくわからないけどダンジョン(JOI)とかガソリンスタンドのアレみたいなタイプだろう -> とりあえず飛べるのはLだけと思ってやって、実際に使った分(歩きと泳ぎ)を後から飛行に変える、でうまくいくね -> 泳ぎより歩き、手前より後ろを優先するのはいいけど手前の歩きと後ろの泳ぎってどっちを優先するべきなんだ -> どう考えても手前の歩きだね -> 遅延評価segtreeを貼る、N<=10^5だし1secでも大丈夫だろう -> pass

E(見直し)

なんとびっくりにぶたんの初期化を間違っていて明らかにやばい挙動をするケースがすぐ作れたが.... -> 許せね~~~~~(リサブ) -> pass

F(見直し)

解法は正しいと信じる、実装にミスはなさそう

G

なんとあれだけ痛い目を見たのにまだ多倍長のライブラリを作っていない + I hate reactive problems -> 閉じる

H

読解が難しいがサンプルを見るとわかる -> 座標に意味はないので差分を取る -> 2*n個の山から1つ選んで石を取る問題に帰着される -> grundy数計算 -> ... -> 埋め込み??? -> 無理そう -> OEISにはない... -> パッと見値が大きくならなそう? -> 30000まで計算してもMAXで25 -> ということは、bitsetで/64する系で攻めればまともに解ける気がする -> 動かせる数を前計算して「鋳型」みたいなbitsetをつくって、xのgrundy数がkだったらk番目のbitsetにxシフトした鋳型をorする、とかすると簡単に計算できる、計算量もsum(grundy_number)+200000^2/64だし絶対通る -> pass

System Test

全部通る

Rating

2833 -> 2918

感想と反省

Eのリサブ以外はOK。落ち着いて実装を詰めてから始める癖をつけたらバグりにくくなった気がする。

多倍長に関してはpythonマスターになるかライブラリを整備するかを早くやってください...