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つの側面として興味を持って頂けたら幸いです。
来年はアルゴリズムの話ができるよう早めに準備をします。
2017-12-31
■ 2017年まとめ & 2018年目標
今年を凄く簡単にまとめたいと思います。
1月~3月
基本的に2月末までは受験勉強をした。
センターと2次はどちらも大きなやらかしはなく無事に終わり、東京大学理科3類に入学した。
APMOを受験し、10位で3回目の入賞をした。
3月には情報オリンピックの春合宿でチューターをさせてもらった。
長らく大学受験のせいで心の底から呑気に過ごせる時間がなかったのでこの時期は楽しかった。
4月~8月前半
入学する。何をしようか考え、とりあえず色々やろうということで、
- 東大特進のスタッフ
- ボート
- 水泳
を始めた。
最初のうちは授業もぼちぼち受けていたが意味を感じられなくなったので次第に行かなくなる。(は？)
5月の頭に、地元で行われたプログラミングの大会の副賞でアメリカ(西海岸)に連れて行ってもらう。
7月にはICPCの国内予選があり、Isplpl (僕、yokozuna57、namonakiaccount)で出場して3位を取った。
そして、7月中旬 ~ 8月上旬の間には東医体の新人戦に向けて週6でボートを漕いでいた。
(試験勉強で2h睡眠 -> テスト6時間 -> 夕方3乗艇の日は本当に死ぬかと思った)
結果は4位でしたが、真面目にスポーツに打ち込むこととはどういうことかが分かり、良かったです。
8月後半~12月
東医体が終わったところで大きくやることを変え、
- 競プロ
- 研究室
を始めた(再開した)。
競プロはAtCoderの問題がたくさん残っていたのでそれをひたすら埋め、研究室では病理画像をDeep Learningで分析するやつをやることになりました。
競プロは真面目にやったこともあり、すぐRedCoderに戻れ、さらにコドフェスで9位を取ったり、ICPCアジアでSeoul NUに勝って2位を取れたりしました。(最高)
研究室では今コンテストに向けて方針を考えたりコードを書いたりしているところです。
2018年の目標
以上のことを踏まえ、以下のように目標を据えます：
- SRM, CF レート 2700
- AtCoder レート 3200
- 国内予選かアジア地区どちらかで優勝する
- 研究室でまともな結果を残す
- Deep Learning系で何かいいインターンを探してやる
- 生活リズムをまともにして授業に出る
基本的にやるべきことは最低限に、やりたいことをやりたいだけやっていこうと思います。
来年も1年がんばるぞい！
2017-12-17
■ ICPC アジア地区予選 つくば大会 2017
12/16 (1日目)
7:30に起きてつくばに向かう。自分らしからず(？)かなり余裕を持ってつく。
JAXAの見学をして、namonakiaccountを待って、会場入りしてプラクティスをする。
人生で一度も触れたことがないのである程度覚悟はしていたが、あまりに英字キーボードが打ちづらすぎるのでチーム内でアメリカへの殺意を生やした。
懇親会でひたすらめしを食って、適当にチーム紹介をして、yokozunaとホテルに向かう。
ホテルでは大浴場の風呂がプールになっていること以外トラブルはなく、生活リズム破滅太郎にも拘わらず日付が変わる前に入眠成功した。
(ちなみに日付が変わる前に入眠したのと翌日忙しかったのとあり人生3回目のデレステログイン忘れ太郎をした)
12/17 (2日目)
8:00に起きて会場に向かう。今日は自分らしく余裕が全くない会場入りだったが、namonakiがTLEしたので全チーム内最下位の会場入りをした。コンテスト順位と会場入り順位の差で天下を取れるレベル。
まもなくコンテストが始まる。
まずnamonakiがテンプレをうち、自分がAをやる。しかし何故かバグらせ(は？？？？？？？)、namonakiと交代する。
書き直したらなぜかサンプルがあったので出して、Aを通す。(マジでごめんなさい)
まもなくnamonakiがBを通し、自分がCを通す。
DEFGHIJKについては、yokozunaがEを書き始め、FとKは簡単そう、Dは明らかにやばそう、Gはできそう、HIJはよくわからない、という感じになる。
Eが通り、namonakiがGを書き始める。
yokozunaとIを考え、結構解かれてるしギャグなのかなーって言っていたら本当にギャグでキレる。
WAが出たので一旦交代し、yokozunaがIを、自分がFを書いて通す。Gもすぐにバグが見つかり通る。
ここで残りが難しいDHJKになり、取りあえず書けるDをnamonakiが書き始めて残りをyokozunaと考える。
Hはかなり理解不能、Jはやばい(まぁ誤読してたからなんですけど)、Kは解法が分かっているので実装の仕方を考える。
実はKはlcaを考えるだけで良い(それはそうすぎる)ことが分かるので、途中でnamonakiからパソコンを奪ってKを通す。
Jを捨て、Hに全力投入すると、なんか正しそう、かつO(N^3)のDPが生えるので、yokozunaと2人で実装したりデバッグしたりして残り5分で通る。
かなりテンションが上がってハイタッチをする。チーム戦....最高やな！
コンテスト終了し、おそらく2位か3位だけど見える範囲にいたmolamolaの最後の提出への反応が芳しくなかったのでこれは？？？という気持ちになる。
そして、この直後ホールで統計情報が明かされてしまい9完:1チームで2位が分かってしまう。ウケる。
Jはチームで揃って誤読してた(大反省)、Dは幾何力的に仕方なし、Hはなんで通ったの？って感じだった。
最後に企業ブースが乱立する中での懇親会になりひたすらめしを食い (こいついっつもひたすら飯食ってんな)、適当に交流する。
PFNのブースでiwiさん、wataさんに熱烈な企業紹介をしてもらい、さらに蟻本にサインを書いていただいた。やったぜ。
つくば->駒場->前橋と移動して帰宅。このチームはこれで最後な可能性があるけど結構バランス良かったし良いチームでした。
来年は交流力と英語力と実装力と頭を備えて参加できるよう頑張ります～～～
■ KOMABA FESTIVAL & CODE FESTIVAL 2017
ICPCアジア地区予選の前にこちらを書きます (1ヶ月前なんですけどね)
11/23 (駒場祭0日目)
夕方に東京に行き、大学同期4人で飯を食い、翌日早くに用事がある1人を家に泊める。
夜中に起きて、デレマス4th SSA 1日目のBDの鑑賞会をしてブチ上がる。(Radio Happyは最高)(HoMoは3rdの方が好きかなぁ)
11/24 (駒場祭1日目)
昼から高校同期と食堂で喋ったり駒場祭を周って楽しんだりする。
夕方にいつもの勢で家でまったりした後、渋谷のサイゼでいつもの会をやって無限に騒ぐ。最高。
11/25 (コドフェス1日目)
朝遅く起きて秋葉原に行く。結構すぐにコンテストが始まる。
ABを爆速で通したあと、CとDで無限にバグを生やして人生終了する。
Cはすぐに直るが、Dは嘘解法を無限に投げてしまい嫌な気持ちになる。
いったん辞めてEFGを一通り読むと、Gが一瞬で分かったので書いて通す。
Fは昔このような概念を見たことがあったので、何となくやることは分かるが細部がわからんなぁ、となって飛ばす。
Eも昔こんな感じの問題を出したことがあるのでそんな感じで解けるな、と確信したが、細かい部分が詰まらず実装に入れなかった。
EとFを並列して細部を詰めていくと、Fが分かって通し、するとすぐにEが分かったので頑張って実装して通る。
ここでDに戻ると、貪欲の後にdpをしないといけないことに気づき (は？)、dpを書いて通す。
凍結前で10位だったのでこれは1桁順位ワンチャンか？？みたいな気持ちになる。
ほどなくコンテストが終わり、結果発表があり全体9位国内2位でした。明らかに出来すぎ。
(HIJはほとんど思考できませんでしたが、どの問題も、強いて言うならIがめっちゃ好きです。)
コンテスト後はそこらに生えているおいしいめしを食べ、解説を聞いたりいつもの勢で絵ウルフをしたりする。
国内3位以内に入ったのでDEGwerさんとhogloidさんとエキシビションに出て、1時間頭を抱える担当をしました。
海外チーム(tourist, Um_nik, ksun)(敬称略)が全完していて流石に天才すぎた。
ホテルに向かい、即座に寝落ちする。
11/26 (コドフェス2日目)
朝早く起きたがゆっくりしすぎてタクシーを捕まえて会場に向かうことになった。
朝はトーナメントがあり、1-16位グループにぶち込まれてかなり困惑したが、早解きなので意外と戦えた。(R2で嘘解法に粘着して落ちた)
rngさんのクイズ大会がかなり面白かった。
最後にチームリレーがあり、Shikさん、Reynaさん、ポテチ、reewさん、dnkさん、beetさん、btkさん、hamkoさん、suibakaさんと同じチームになる。
H担当になり、解法で大嘘をつき、終了間際にShikさんに冷静に解法を教えてもらうたのしいたのしいちーむせんでした。(死)
こんな感じです。(1ヶ月前なのでかなり記憶が曖昧)
駒場祭もそれにかこつけて普段会えない仲良い人と遊べたし、コドフェスは純粋に楽しかっただけではなくコンテスト本番でめっちゃいい成績だったのですごく満足でした。リクルートさん是非とも来年もよろしくお願いします。
