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でやらかしたのでどうしようもない、こういうのは事故にあったようなものなので仕方ないね
2019-01-20
■ DDCC 2019
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
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
新年初コンテスト、何故か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年の目標振り返り
- 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
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マスターになるかライブラリを整備するかを早くやってください...
