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マスターになるかライブラリを整備するかを早くやってください...
Writerをした時の話
この記事は Competitive Programming (1) Advent Calendar 2018 4日目の記事として書かれたものです。
はじめに
と言っていましたが、予定を変更 (という名のテーマ決めの失敗) して、2016年に書こうと思っていたテーマで書くことにします。
テーマは「Writerをした時の話 (TopCoder SRM 694)」です。
経緯
元々一番好きな競技プログラミングのコンテストはSRMだったので、18歳になったら1回writerやってみたいなぁとずっと思っていて、2016年の春に18歳になった時から問題案を考え初めました。
そして6月の頭に6問(5問)完成して、7/10に行われたSRM 694のwriterをすることに決定しました。準備はJavaで想定解を書かないといけないなどかなり大変でした。
結果はこんな感じでした。
今振り返ってみると、Div1はHardがかなり簡単で、全完が20人近く出るのも当然だなという感じがします。(こういうセットはHard早解きゲーで順位がついてしまうので微妙ですね...) Div2も上位陣は3問とも見た瞬間に解いているような点数を出していて、もう少し捻りがあっても良かったかもしれません。
前置きはこんな感じで、以下各問題にコメントや背景を書いていこうと思います。 (自力で解きたい人はあとがきまで飛んでください)
問題の詳細
MakingPairs(Div2 Easy)
概要:
同じ数字が書かれたカードを2枚組み合わせてペアにできるとき、最大でペアはいくつできるか
コメント:
流石にやるだけだと思います。このスロットに捻った問題を置く必要はないし、変なストーリーを入れて読解に時間を掛けさせるのも本質ではないので、こんな感じの出題をしました。
DistinguishableSet(Div2 Med, Div1 Med)
概要:
N人にM問のアンケートに回答してもらった時、M問の部分集合であり、N人のその集合に対する回答が全て異なるようなものはいくつあるか
(Div2版はN<=50, M<=10で、Div1版はN<=1000, M<=20)
コメント:
もし問題の部分集合2^M個すべてに対して、回答がN人みな違うかチェックしていいなら簡単です。それがDiv2 Medです。
Div1 Medでそれをやるとどう実装しても通らないはずで、もし通ったら定数倍最適化の†天才†です。
ここで余事象の発想で、「ある2人がいて、回答が一致する」(<=>「全て異なる」)ような集合をカウントすることにすれば、
「N人のうち2人の組み合わせを取って、その2人の回答が一致する問題の集合にフラグを立て、最後に各集合からその部分集合にフラグを伝搬する」
という解法にたどりつけると思います。実装は無なので完全なる一発ゲーです。
このセットでは一番気に入っている問題で、「アキネーターってどう実装されてるのかな？」って疑問を持った時に出来ました。
UpDownNess(Div2 Hard)
概要:
長さNの順列で、P[i] < P[j] > P[k]なる(i,j,k)の組がK個あるようなものは何通り？
コメント:
「DPは左から順に見るもの」みたいな固定観念があると全く解けません。(少なくとも今までどの数字を使ったのか？を覚えていないといけないため)
「順列の問題は小さい順/大きい順 に挿入して考えるとよい」っていう典型発想があれば瞬殺です。
完全に教育的問題なので、このスロットに置きましたが、普通にガンガン通されてびっくりしました。
TrySail(Div1 Easy)
概要:
非負整数の集合を3つに分け(空集合はダメ)、各々の集合に含まれる整数のxorを取り、その総和を最大化してください
コメント:
dp[i][a][b][c][mask] = (i番目まで見て、各々のxorがここまでa,b,cで、3つの集合が空集合かどうかはmaskにエンコードされている という状況はあり得るか)
というのがノータイムで出てくると思います。
これだと落ちるんですが、冷静に考えるとi,a,bからcは一意に定まるので、一つオーダーが落ちてこれで通ります。
実は、空集合はダメ、と言っているんですが冷静に考えると (a xor b) <= a+b なので、これは無視しても大丈夫です。(無視すると上の落ちる解が通ってしまったようです)(悲しいね)
流石に競技プログラミングが下手すぎると思う......
SRMDiv0Easy(Div1 Hard)
概要:
初めすべて0の配列に区間加算クエリを何回か行います。加算した値は[L_i,R_i]のどれかであることが分かっています。
このとき、最終的に得られた配列は全要素が等しかった。こういうことがあり得るか、あり得るならその値として考えられるものの最大値を求めよ
コメント:
パッと見めっちゃ難しそうじゃないですか？僕はそう思います(てへぺろ)
配列の差分を取るとフロー(最小流量制約つき最大流)になるので、蟻本に小さく書かれているアルゴリズムを実装すると通ります。
この問題は、「なんか数列の差分を取ってうまく解ける問題作れないかな～」って考えていたら区間加算クエリがフローに対応することに気づいて出来ました。正直トプランの方々には秒で見抜かれていた気がします。
あとがき
多くの人にとって、役に立ったり参考になる記事ではないと思いますが、競技プログラミングの1つの側面として興味を持って頂けたら幸いです。
来年はアルゴリズムの話ができるよう早めに準備をします。
