rickytheta's blog

競プロ

CODE FESTIVAL 2016 予選A

3完で通りました。全体順位120位。

code-festival-2016-quala.contest.atcoder.jp

開始前

100-200-400-800-1200のWAペナ無しレート変動あり。明らかにやばい。めっちゃ緊張した。

A

前4文字と後8文字の間にスペースを入れるやつ。

最近stringのsubstrを使っていたので結構すぐに書けたけどコンパイルとテストをしたので若干FAから遅れる。

B

相互リンクの数を探すやつ。

最初若干解釈をミスって逆写像が一意に定まると勘違いした(？？？)。

setに被リンクを突っ込んでおいて入ってるかどうかをチェック、相互リンクの数を数えて2で割った。

C

指定された回数ちょうどだけ文字を1個後ろ(A→B、B→C、…、Z→A)にずらして辞書順最小を作る。

前から貪欲にAにすればOK。調節は一番最後の文字で。

ここまでで6分24秒。通ったな(確信)

D

左上+右下 = 右上+左下 になるように非負数でグリッドの表を埋めるやつ。動機が謎すぎる。

W*H<=1010 なのでなんかヤバそう。これは早解きセットだな勝った(確信)

一応Eを読む。

E

数列がいっぱいあっていじる。いかにもAGCのEあたりにありそうな問題。

操作には与えられた数列を使うように言われてるので、直感で逆から見るんだろうなぁと思った。

でも逆から見るんだろうなぁ系の問題を本番で通したことが無いのと、点数傾斜から敬遠。Dに戻る。

D

まず与えられた式を変形すると任意の長方形の四隅で成り立つことが分かる。

で変形するとある列と列の間の差が等しいということは分かった。行についても同じ。

なので式の条件を満たすには行間と列間が求まればいいことが分かる。ついでに座標圧縮しても問題は変わらないことも分かる。

ここで全てのマスを実際に埋めるという明らかなTLE解を思いついたが、階段状に数字が埋まったケースがO(WH)個のマスに影響を与えるため即却下。

行ごと、列ごとに見て、行間の差がいくらか、というグラフを作り、BFSである点からの差(距離)がどれぐらいかというのを埋めていく。矛盾が生じたら即終了。

で、後は負数のチェックで、これはあるマスから行の差を足していけばそのマスを含む行の最小値が分かるので、RMQみたいなことをした。

ここから提出を繰り返すけどWAが取れず終了。初期化をバグらせたり非連結を対処してなかったりで散々だった。

終了後

結局早解きでも通過できそうだった。

Dの解説を読んで、行と列の値を決めたらr_i+c_jで表現できるとか書いてあって感動した。

Eは予想通り逆から見るやつだったけどこっちの方が簡単そうだった。残念。

賞金欲しいので本戦までにもうちょっと精進する。

天下一プログラマーコンテスト2016本戦 参加記

予選Bの本戦出場権持ちの予選A通過勢を除いた繰り上げの繰り上げの繰り上げで本戦に出場しました。

実質最下位。

予選A

ABCやるだけD発想EつらいでABC3完

予選B

AやるだけBはDPやるだけ

Cで確率DPが苦手なのにバグらず一発で通ってしまう

DEが死

でもABC早解きと繰り上げで本戦出場

本戦

なんかエナジードリンク(カフェイン含む)が無限供給される。闇

カフェイン含有量だけ書いてなかったんだけどレッドブルとかと同じと考えていいんですかね……？

A/B

講義で巡回セールスマン問題をやっていたのでTSP来いと思っていたのですが4彩色問題。

なんかとりあえず辺がいっぱいあれば強そうなのでAはランダム配置に張れるだけ辺を張ったやつを適当に組んだ

Bは特に考えずにrandom_shuffleした(参考 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2550)

D

Cは文字列が苦手なので後回し

Dは制約からして2Nの形をしてるんだなぁと思う

予選AのCと似てる気がするので、どっちの部屋から始めて、どの作業をどっちでやるのかだけ決めちゃえばシミュレーションできるなぁと思って書く

なんか部屋の交代とか新しくできるようになったタスクの探索に変に計算量つかったからか数秒だった

C

すごい文字列

Aho-Corasickなら結構行けるのでは？と思ってスパソを見よう見まねで写す

が、スパソのAho-Corasickはfailした際にacceptを回収していないらしく、そこだけ回収するように変更する

後はその情報をまとめてからDPする

上記のスパソの回収漏れと、血迷ってKMPでO(M|S|)なのを出したのを含めて4WA吐いた

後で解説を聞いてトライさえ組めれば文字列長最大200だから各開始地点につきたかだか200しか探索しないと聞いてなるほど～～と思った(1パターンごとの文字列長制約をあまり大事だと思っていなかった)

E

Cが終わった時点で2時間10分ぐらいだったので軽くあきらめモード

見た感じ刺す位置を固定しさえすればあとはN個の肉は独立に考えられるのでそれぞれO(logL)ぐらいで「位置kに串を刺す時の最適解」が求まれば嬉しいなぁとか思った

ただコストが2次関数で駄目だ～～～ってなっていた

この辺で予選BのDEを思い出してsegment treeなんじゃないか？とか思ってしまう

が、ここらへんで時間が終わる

ちなみにFも読んだけど無理

解説

Aの解答例としてグリッドグラフに斜線入れたやつを出される。random_shuffleで倒せるか不安になった

EでL個のクエリをO(LlogL)で処理すればいいというのを聞いて昇天した

Fは聞いてて本当に天下の人間向きの問題なのかと疑った

AB結果・表彰

懇親会会場に移る。

A問題とB問題の最終結果が発表された

http://tenka1.klab.jp/2016/stands/

下から順に発表していく感じで追い抜いたりするのが面白かった

乱択で張れるだけ張ったケースは17撃墜、random_shuffleは11ACでした

で4完の中では1位の14位に。最下位スタートだったので嬉しい

A問題全撃墜ケースはドロネー三角形分割らしい。不可能。

B問題上位はしっかり枝刈りDFSをしていたらしい

ちなみにこの後懇親会中ずっとA問題ケースをプロジェクターで映されていたのですが多分僕のケースが一番緑々してて目に優しかったと思います(頂点がオレンジ、辺が緑でビジュアライズされていたため)

表彰はめっちゃ拍手してました

懇親会

🍕🍕🍕🍕

なんかすぐに🍕が消えた

あと適度におしゃべりをした

感想

緊張してた割にはかなり楽しめた気がする

来年はそもそも予選通過できるか怪しいけど賞金を目指したいなぁ

KLabの人へ

エナジードリンクごちそうさまでした

モバイルバッテリーも結構重宝するので助かります

あと本戦会場後ろにあるスクフェスの折りたたまれたパネルがすごく気になりました

CODE RUNNER 2015 参加記

競プロ

交通費支給のイベントで夕飯分の食費を浮かせる一般的なテク。のつもりが10位入賞で嬉しい誤算。

以下ツイート付けながら参加記を書きます

予選

A:ランダムに線分を取り続ける戦略。脳死。99位。

B:閾値に達したら攻撃する、みたいな戦略。途中誰も攻撃しないとかあって辛かった。63位。

本戦参加権は予選Bの63位のおかげだそうです。

開始前

結局ほとんど準備せず。(環境整備を少しだけ)

開始

本戦は「お国からタスクを受注するか、市場に出てるタスクを外注として引き受けて、自社の社員に割り振って報酬をいっぱい得よう」みたいなゲーム。他プレイヤーとの相互作用ポイントは外注システムのみ。

社員は酷使していくと経験値が溜まっていって、タスク処理速度が上がっていく。

最初のうちはとりあえずinfoを叩きながら、全員でお国から受注した1つのタスクをこなす、というところを自動化した。

これが自動化安定した時のツイートのはず。

プロフィール文を「🍣」に変更。その時プログラムを稼働させている人が少なく上位だったためちょっとだけ目立つ。

中盤

お国からいくつか受注して、能力の特化した社員がいれば充てるようにして少しだけ効率を上げようとしたが、無駄に受注してリスクが発生してしまい順位が下がる。

ここで減衰のシステムを知ったので、減衰したタイミングで戦略を切り替えて逆転を考える。

悲しい誤算。焦る。

終盤

ここで、リスクが発生しない外注システムを読み返す。

外注のinfoを叩いてタスクを見てみると、割と報酬の良いタスクがいっぱいあったので、これで行くことに。

閾値以上の報酬がもらえる外注タスクを一つ一つ見て、今使える弊社社員のうちそのタスクを処理する速度が速い順に並べて、社員の能力がそこそこ活かせるようにタスクがこなせる(速い順に使って行って、最低の速度が3以上みたいな判定基準)なら受注する、みたいなアルゴリズムに変更。

この時点で30位前後だったはず。

うまくハマって少し安堵。

このツイートから20分間ターミナルとランキングに張り付いていた。

自分が12位の時に11位の人が「ここから下は賞金なし」ってコメントに変更していて非常に辛さがあった。

終了

滑り込み10位でした。歓喜。

表彰

"rickytheta"のIDが読みづらい事案が発生。「リッキー」でお願いします・・・

その後

"#coderunner2015"ではその後考察が多く流れていたが、「社員ガチャ」「社員厳選」など、思いつかなかった(というよりそのAPIを無視していた)戦略があって奥が深いと思った。

超ホワイト。

あと、今回は外注を受ける側にひたすら回っていたが、外注を出す戦略でももしかしたらかなり儲かるのかもしれない。もうちょい早く考察するべきだった。

感想

すごく楽しかった。

他の普通の[要出典]競プロと比べるとかなり違う頭の使い方をした。

かなり勝手が違うし、APIも仕様も多くてかなり難しいと思ったけど、3時間でどのように使いこなせるか、というのを競うは結構お仕事のプログラミングに近い気がした。

懇親会ではいろんな企業がインターンの募集やってたしそういうのにも手を付けたい。

なお、懇親会で🍣は出なかった。

Code Festivalに参加した

競プロ

初参加 & こういう参加記みたいなの書くのも初

本戦

パーカーの入手ノルマが5完になっていた。コンテストは3時間あったが、最初の1時間ぐらいで5問解いて後は座ってたのが非常に辛かった。

Bで愚直にシミュレート(dp[0][i+dice] += dp[1][i]/6.0)したら誤差死を繰り返していた。よくわかんないけどそれで無理やり通した。

Eはかなり余裕だったので最初に開いていればFA取れたかもしれない。

Eまで終わった後はIをやっていたが、TLEをもらって(O(N2)だったのでわかっていた)意気消沈していた。O(NlogN)にする必要があるのでsegtreeかBITだろうなとは思ったがどう適用するか分からなかった。segtreeは使いこなせるようにならないといけない。

後で解説を聞いたりchokudaiさんの講演聞いたりして、グラフじゃない(グラフに見えない)グラフ問題が苦手なことを実感した。

あさプロ

ホテル勢だったが寝坊決めてタクシーで会場入りした。

難易度はMiddleでAとCの2完。21位には入れず。

BはLCS(Longest Common Subsequence:最長共通部分列)という概念を完全に忘却していて、蟻本を肘の下に置いてあったのに解けなかった。基礎力不足を感じる。

リレー

「主菜と副菜」を担当。N個の主菜から1つ、M個の副菜から任意の個数取って、L以下のコストにおける価値の最大化。01ナップサック問題。

-INFで初期化していないために2WA。微妙にグループメンバーを悩ませてしまって申し訳なかった。

気になったのはPlatoonの問題。うまいこと状態を取るとDPのオーダーが落ちるらしいけどこれは思いつかない。

RedBull美味しかった。

講演

初日は秋葉さんのペアプロ、2日目はchokudaiさんのプロコン講演とりんごさんの謎ゲームを見ていた(名前の表記ゆれが激しい)。最後を除いてかなり役に立った気がする。

りんごさんの色当てクイズゲームで評価をRGBのマンハッタン距離というあたりが競プロ勢っぽかった。

感想

非常に楽しかった。有名人を間近で見られたり、エキシビジョンマッチではコードの様子も見ることができた。特にプログラムについて語れることが想像以上に楽しく、グループ戦はかなり満足感があった。来年は是非賞金を取れるよう頑張りたいと思った。

また環境も最高で、食事も飲み物も菓子も豪華だった。ホテルまで用意してもらって、このあと巨額な請求が来るのではないかと怯えている。

来年も寿司が食べたい。