WUPC2020 参加記
BのFA狙うか...
A_1 * A_2 + A_2 * (-A_1) = 0
( ･´ｰ･｀)
( ﾟдﾟ) ・・・
(；ﾟдﾟ) ・・・
(つд⊂)ｺﾞｼｺﾞｼｺﾞｼ
（；ﾟ Дﾟ） …！？
以下残りの問題について
A:うん
E:最初謎に迷走したせいでコードが酷いことに
F:知性が終わっているので謎エスパーをしようとしてWA 冷静に考えると謎エスパーをせず全部調べれば良かった...
C:ABの2つを通した後流し読みしたときは複雑そうだったので飛ばしたが、沢山通されているのを見て落ち着いてみると簡単だった
G:こういうの好き 競プロをやっているという気分になる
M:今日のセットの中で一番実家感のある問題だった というか解いたことある気がする...?
J:SCCした後出てくるグラフが有向森だと思い込むやつ998244353回やってる...それはそれとしてこの計算量解析の落とし方は好き
I:落ち着いて考えると壮大なギャグで笑ってた
K:odd/oddとeven/evenは簡単 odd/evenはZ>=2ならokで、Z=1のときは...
うーん...oddが大きいときは分かって...
うーん...
よし、多分こう！ → AC
D:無限ステップあって死んだ顔しながら実装してた 出したらMLEして笑顔
H:謎にWAが出て頭を悩ませていたが、長さ3のパスグラフを試したら答えが2になりやがった。算数パートでコーディングミスしていた。
L:もうこんな感じの式変形何年もやってない...ゆるして...
良いコンテストでした。運営の皆さん有難うございました。
FORCIA Summer Internship 2020 参加記
FORCIA Summer Internship 2020 Rustインメモリデータベース開発コースに参加してきました
業務内容についてはどこまで書いて良いかもよく分からないので、大体業務外のどうでもいい出来事について日記くらいのノリで書きます。ちゃんとした参加記を読みたい人はごめんなさい。
1日目
一番乗りでインターン生待機部屋へ。今期のインターン生は3人らしい。
部屋で待機していると、1人のインターン同期が来る。(以下同期A)
同期A「東京に住んでらっしゃるんですか？」
自分「そうですね〜 東京ですか？」
同期A「そうですね...東京の大学に通ってらっしゃるんですか？」
「あ、この人東大だな」と確信する。
同期A「Rust普段書かれてるんですか？」
自分「いえ、書いたことが無くて、このインターンが決まってから勉強を始めました」
同期A「えっ、そうなんですね...」
ドン引きを感じる。いや、冷静に考えて逆の立場ならドン引きするな。
その後も少し話す。どうやら同期Aも競プロをやっているらしい。
暫くしてもう1人のインターン同期(以下同期B)も来る。同期Bも競技プログラマで、全員AtCoder Jobs経由で申し込んだらしい。競プロer率が異常すぎる。
そして朝会の時間に。インターン生の紹介が始まる。
「1人目は東京大学の(kort0n)さんで〜」
他己紹介されるのって何か小っ恥ずかしいよね。
「2人目は東京大学の(同期A)さんで〜」
やっぱりね。分かるんだよな〜。
「3人目は東京大学の(同期B)さんで〜」
全員東大か...
FFのメンターから説明を受け、業務開始
暫くして休憩スペースへ。某社員(@tempura_cpp)がいたので話し、その後同期Aと話す。
自分「さっきの社員の人知り合いなんですよね～」
同期A「...僕あなたが誰か多分分かりました」
( ＾v＾)...?
先行き不安で仕方が無い。とりあえず退勤時間になったので退勤...
2日目
この日業務以外だと特に変なイベント無かった気がする(?)
3日目
このインターン期間中は昼食は社員数名と食べるのですが、何とこの日は
・勤務n年(社内でもかなり長い方)のエンジニア
・社長
という、明らかに大御所枠の日だったので、流石に緊張していた(他の日はメンターか、若手社員)
蓋を開けてみると、2人で漫才をしているのかというくらいのマシンガントークが炸裂していた 何？
夜は社員の方2名に誘われ、インターン生3人と計5人で近くの居酒屋へ。
インターン同期と時間を掛けて話すタイミングがあまり無かったので良かった。このときに話して分かったのだが、どうやら同期Aは自分のツイッターを相当見ているらしく、競プロを始めてからに限らず、学部1年生の頃のクソツイート等についてもよく知られていた。あまりに恥ずかしい。
例の「2色下は～」が好きだという話をされる。社員(非競技プログラマ)の方が食いついたので経緯を話すと、ウケた。しかし、同期Bに
「あれってそういう理由があったんですね。ただの過激発言だと思ってました。」
と言われた。悪質な拡散をしている民許せねぇよ...
あと京都出身の人達の会話で
「僕京都出身です。」
「え、俺も！」
「あ、でも洛外です」
という会話があって面白かった。こういうの本当にあるんだ
4日目
この日は退勤後に社内バチャがあった
最初の3問は通したことがある問題だったのですぐに通す
4問目は初見だった。暫く考えて実装するとWA
何度か修正しつつ提出するもWAが取れない
仕方が無いので実装方針を大幅に変更して提出するとAC
結果、700近いレート差を逆転され、3位に...
最初のWAが納得行かないので周りと議論するが、どうも会話が噛み合わない。問題文を読み直す。誤読してた。
しかし、誤読していたなら最後の提出が通ったのが納得行かない。ACしたコードを読み直す。バグってた。誤読とバグが組み合わさってACしてた。は？
夜はtempura_cppさんと寿司を食べに行った
小学生チョイスしたらてんぷらさんと丸被りしてた pic.twitter.com/NwITykvD7e
— ABC174 276位 (@kyort0n) 2020年9月3日
人に奢ってもらうときは流石にいくらか遠慮が入るけど、会社の金となるとなんか食べちゃおうかなって気分になる 最高！
5日目
5日間の進捗の最終報告会があった
やったことを話して質疑応答の時間になる
司会「○○さんからチャットで質問が届いています。『～～～』」
自分「それは～～～です。」
司会「(tempura_cpp)さんからチャットで質問が届いています。『実装の鬼』。」
それは質問ではない
その後は懇親会が始まった。頭が付いていないので、カードキー返却後の最後の懇親会でトイレに行って会場から締め出された(暫くして社員の方が気付いて開けてくださった) はやく人間になりたい...
以下少しだけインターンの参加記っぽい記述
Rustについて
- 所有権とかトレイトとか諸々の概念が複雑で、とりあえず書けるようになるまでが難しい
- 型についての厳しさも相俟って、コンパイルを通すまでにかなり苦労する
- しかし、コンパイルが通ってしまえばほぼ勝ち C++等では書いた関数が意味不明な挙動をすることもザラだが、Rustではそういうことは少ない
- 「書いた関数を使い忘れていた」というタイプのバグ等は発生し得るが、そういうのは気付きやすい 総じてバグを埋め込みにくい/デバッグが楽な言語だと感じた
その他雑感
- 例年の同コースのインターン生と比べてかなり進捗を生めたらしい。AOJ-ICPCの修行の賜物。競技プログラミングは業務の役に立つ。
- 他の2人のインターン生は、いい感じにモデルを立てていい感じにやる課題をやっていた。多分kaggleは業務の役に立ちそう。kaggleやったこと無いけど。
- でも業務で使うツールとか用語とか全然知らないと恥ずかしいし不便なのでちゃんとその辺も勉強しないとヤバい。
以上5日間お世話になりました。有難うございました。
チーム練記 2/4 2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
需要があるらしいので書こうと思います
2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
The atama主催の3チームバチャ(The atama, Heno World, 弊チーム)
risujirohにコドフォのチーム名をQWE_QWEにされる これ絶対ICPC本番までにはチーム名変えるからな
risujirohは私用で途中参加の為、Rubikunとkort0nの2人でスタート
初動はRubikunがAから読み始め、僕がGから読み始めることになる
Gを読み始める 読解に5分くらい掛かってキレる まあでもそんなに難しくなさそう
Gを読み終わると、何とCDEがぼちぼち通っている は？
RubikunにCを読んでもらい、Dを読むことにする
何とA>Bの間はAを小さくし続けて、最後に足すだけ 簡単ですね〜〜〜
ニッコニコでsubmit
なんで？
ソースコードを読み返す 奇数判定を x & 2 と書いている あまりに頭がついていない 書き直す AC(0:11)
Eを読む うんうん、連続する部分文字列であって、同じ文字が2回以上現れないものの数え上げか〜 これ見たことあるな 尺取りでホイだね
RubikunがCを解けたと言っているが、カスなので「Eすぐ書けそうだし先書かせて〜」と言ってキーボード使用権を強奪する
ウッキウキで実装
サンプルが合いません
サンプルが合いません
サンプルが合いません
サンプルが合いません
サンプルが合いません
かなり死にたい気持ちになってくる 「ごめん、Eなんか合わないからC先にやって...」と言う
落ち着いて問題を読み返す よく読むと、「(連続していなくてもよい)部分文字列であって〜」であった カス...
この間にRubikunがバッチリCを通す(0:25) あと確かこの辺でrisujirohが合流する
流石に誤読しなければEはクソ簡単 各文字列出現回数を数えて掛けるだけなので実装もクソ軽い
急いで実装してsubmit
なんで？
え、流石に解法は間違ってないと思うんだけど 何で落ちるんだ オーバーフロー？というかこの問題どう考えても答えlong longに収まらなくないか？
問題文をよく読み返すと
お分かりいただけただろうか
頭を抱えながら修正 AC(0:29)
順位表的に恐らくこの3問が所謂自明枠だったのですが、圧倒的活躍によりチームのペナを破壊する
順位表を見て通ってるのに手を着けることにする 確かRubikunがAでrisujirohがBで僕がLだったと思う
Lを読むけど分かりません ウケ
こういうのはrisujiroh担当！と言ってrisujirohに投げてIを読む
Iを読む 最大安定集合を求める問題になることが分かる
ぼく「最大安定集合ってこのサイズは無理だよね」
risujiroh「普通は無理だね 二部グラフとかなんじゃない？」
ぼく「えーこれ二部グラフなのかな (考えると、S="aab"とかで二部グラフにならない) いやならんわ」
よく分からんのでIをrisujirohに投げる AをRubikunに投げられたので読む
なんか全方位木dpすれば通りそうだけどいきなり実装入ると破滅しそう そんなに実装軽くもなさそうだし後回しかな〜などと考えていると、またIの話になる
risujiroh「これ入力長の制限って無いのかな 集合のサイズ決まってても長い文字列来ると入力でTLEしないか」
ぼく「それは思った まあその辺はよしなにやってくれるんじゃない」
risujiroh「これよく読むと同じ文字は2度現れないって書いてあるぞ だから高々26文字だ」
ぼく「あ、そうなんだ ん？」
数分前ぼく「えーこれ二部グラフなのかな (考えると、S="aab"とかで二部グラフにならない) いやならんわ」
ぼく「え、ごめんじゃあ二部グラフになるかも」
考えると、この条件のもとだと結局二部グラフの最大安定集合問題になる risujiroh、超能力者か？
risujiroh「じゃあ解けるね フロー書くかー」
ぼく「え、二部グラフの最大安定集合ってUnion Findで出来なかったっけ？」
↑やめたら？橙コーダー
結局risujirohが実装する AC(1:09)
この間にRubikunが読んでよく分からんと言っていたMを投げられる RubikunにはかわりにLを投げて、Mの概要を読む
え、これでは？
最近解いた問題の弱体化版なので流石に秒で解ける 序盤の個人の動きが酷すぎたので、ちゃんと仕事が出来そうで安心 実装してsubmitする
なんで？
RubikunがLを解けたと主張していたのでPCを譲りデバッグする
コードを読み返すと、H+1列あるのに二次元座標を一次元に潰すときに掛ける係数をHにしたせいでマスがぶつかってしまっていた カス... 修正してAC(1:28)
RubikunがLを実装している間にAの遷移式を詰める
RubikunがLをACする(1:38)
その後Aを実装する 「15分くらいかな〜」と宣言して実装したら16分で実装が終わった ここ冴えてた AC(1:54)
risujirohがBの実装を始める 確かRubikunはFを読み始めて、ぼくはGに戻る
暫くするとGが解ける BのWAが取れず辛そうだったので、PCを譲ってもらってGを通す(2:22)
Hを読む 別の点にぶつかるまで直線を回転させるとかいう意味不明幾何 なんだこり 無理だろ
risujirohにBを相談される なんかよく分からんけどバグが見つかった(のか?) よく分からんけどなんか通る(2:38)
Hが意味不明なので「これは捨て判断だろうな〜」と思いながらrisujirohに概要を話すと、2分くらいで解法を出してくる なんだこいつ
結局本質は幾何パートではなくグラフパートだった為、実装を投げられる 泣きながら実装をする
この間にRubikunはFを、risujirohはJを考える
途中誤読によるミスもあったが何だかんだで修正できて通る(3:37)
この後risujirohがJの実装を始める ぼくはFを考え、RubikunがKを考えることになる
しばらくrisujirohが頑張るもWAが取れない 4:20時点でrisujiroh離脱 さようなら...
risujirohがJと格闘している間にFの考察はほぼ終わっていたので、Fの実装を始める 40分もあれば余裕だと思っていたが、途中考慮漏れがあったことに気付いて焦る ヤバイヤバいと言いながら必死に修正する 何とか通る(4:57)
Heno Worldが全完しててえげつない risujirohフル参加なら@1完は増えていたかもしれないが、Kは多分無理...
別日にバチャをした学科の先輩のチームにも負けていて悲しくなった
まあでも新チーム初陣にしては上手く動けてたかなと思います チームとしてのパフォーマンスを向上させていきたい
ARC014 魂の還る場所
https://atcoder.jp/contests/arc014/tasks/arc014_3?lang=ja
解法
各ボールの色の偶奇性に着目すると、各色円筒に入れられるボールの数が奇数であれば、その色のボールは最後に最低1個は円筒の中に残る。
則ち、答えの自明な下界として、#{色c|円筒に入れられる色がcのボールは奇数個}が考えられる。
以下この答えを達成可能であることを示す。
以下のように状態A, B, C, Dを定める
状態A:円筒が空
状態B:円筒に1個のボールが入っている
状態C:円筒に2個のボールが入っている
状態D:円筒に3個のボールが入っており、この3個は異なる色であり、更に次に入るボールと同じ色が端に存在するか、もうボールは入らない
実は、操作中、円筒がこの4種類の状態のみを取るように出来る。
状態Aのとき
次のボールを入れれば状態B
状態Bのとき
次のボールが円筒の中のボールと打ち消し合えば状態Aへ遷移する。そうでないならば状態Cへ遷移する。
状態Cのとき
次のボールが既に円筒に入っている2つのボールのいずれかと同じ色なら、それと打ち消し合うように入れれば状態Bに遷移する
そうでないならば、更にもう1つ先のボールを見つつ適切な方から入れれば、状態Dに出来る。
状態Dのとき
状態Dの定義から、適切な方からボールを入れれば状態Cに出来る
以上より、操作中常に円筒を状態A,B,C,Dのいずれかに保つことが出来る。
以下、このように操作を行った際の最終状態を考える。
#{色c|円筒に入れられる色がcのボールは奇数個} = 0のとき
偶奇性に着目すると最終状態はAかCだが、Cになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はA。
#{色c|円筒に入れられる色がcのボールは奇数個}=1のとき
偶奇性に着目すると最終状態はBかDだが、Dになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はB。
#{色c|円筒に入れられる色がcのボールは奇数個}=2のとき
偶奇性とボールの個数に着目すると、最終状態はCであると分かる。
#{色c|円筒に入れられる色がcのボールは奇数個}=3のとき
偶奇性とボールの個数に着目すると、最終状態はDであると分かる。
そして、これらは全て前述の下界と一致する。
ICPC 2019 Asia Yokohama Regional 参加記
okimochi(idsigma risujiroh kort0n)でICPC 2019 Asia Yokohama Regionalに参加してきました
Day.1
あ、真紅のぬいぐるみ忘れた...
— こるとん (@kyort0n) 2019年11月16日
かなしい...
#icpc2019yokohama pic.twitter.com/FN3mapsOO5
— こるとん (@kyort0n) 2019年11月16日
おいしい...
韓国で買ってきたお土産毒を配る
C-7で韓国土産配ります #icpc2019yokohama pic.twitter.com/CgCjF1afiG
— こるとん (@kyort0n) 2019年11月16日
こるとんたちからもらった毒を食べます
— beet (@beet_aizu) November 16, 2019
とうもろこしの毒をもらった
— 西條クロディーヌ (@latte0119_) November 16, 2019
こるとんから噂の毒をもらった おいしい
— 碧黴(あおかび)🦇4日目西O42a (@AokabiC) November 16, 2019
失礼な奴らだ
Practiceが始まる
C、Dは過去にチーム戦で出てきた問題
A、Bは初見だけど流石に無
Aを通す
Bをidsigmaさんが通す
Cはチーム練ではrisujirohが通していた為、僕が通すことに
これ確かチーム練だとTLEが出ていた問題なんだよね 注意しないと...
risujiroh「これTLE気を付けてね」
言われなくても分かってるよ えーっと...
よし！next_permutationで全探索すればokだな！
ウキウキで実装 submit
PROBLEM C TIMELIMIT
SeoulのPractice-Bの仕返しと言わんばかりに煽られる しにてえ
ちゃんと実装し直して通す
2つ隣のUKUNICHIAのつぶあんと目が合う まだCが通ってなさそうだったのでとりあえずCの風船をアピールすると、無限に親指を下げられた サイコ〜ｗ
risujirohがDの実装を始める
サンプルが合ったらしいので投げるがWA
何かハマってるので印刷練習も兼ねて印刷して全員でデバッグ
バグを見つけたので指摘して直してもらうと、サンプルが合わなくなる は？
よく調べると、3箇所バグってて、何故か噛み合って奇跡的にサンプルが合っていた なんでだよ
無事 AC
再びつぶあんと目が合う Cの風船をアピールしてきたのでDの風船をアピールすると、無限に親指を下げられた サイコ〜ｗ
clarも練習しておく
そうじゃないんだよ pic.twitter.com/fb6CajXNpH
— こるとん (@kyort0n) 2019年11月16日
チーム紹介が始まる
みんな、TopCoderを、やろう！
ソートなぞなぞをやめなさい pic.twitter.com/rjg42bVYtw
— こるとん (@kyort0n) 2019年11月16日
これすき
あとchoKOdaiのハンドスプリングビックリした
10人くらいで中華街に行く
中華街初めて来た気がする pic.twitter.com/znQU0m3nJu
— こるとん (@ILoveTw1tter) November 16, 2019
メンバーの中で自分が年寄り側だと誤認していたので支払いで「若い人少なめで良いのでは」と言ったら自分が若い側で、無事社会性0になる いやほんとごめんなさい
るましーさんにくそなぞなぞ振ったらめちゃくちゃオーバーリアクションが帰ってきて、え、何こわ……って思ったら話しかけてた相手がこるとんさんだった回
— しーある (@cs_c_r_5) November 16, 2019
絶対に許さないからな。
自宅からだと相当早起きしないといけないので、会場まで1駅のカプセルホテルに泊まる
設備自体は値段を考えれば不満は無いが、近くのおっさんが一生独り言を言っていて本当に怖かった 今度から宿代はケチらないようにしようと思った
ABCがあった 「Eの解法2すごい！」とTLで言ってたら「いやそっちがすぐ思いつくだろ」と言われる 枕を涙で濡らしながら就寝
Day.2
起床即TCO Algo Finalわくわくでゲラゲラ笑う 最高の目覚め
— おきもち (@IKyopro) November 16, 2019
いや持ってこいや
「TwitterだけじゃなくてSlackも見ろ」と怒られる スマン
コンテストが近付いてくる (Yokohamaは前に易しい問題が存在することが保証されているのもあって)初動はSeoulのときと変えて、
idsigma:開始即環境構築 終わったら後ろの問題を読む
kort0n:環境構築後Aをやる
risujiroh:Bを読む 実装が軽ければそのままやる 重ければ実装をkort0nへ投げて後ろの問題へ
となっていた どうしても弊チームは考察が弱めで完数で勝ちづらいので、序盤からペナを切り詰めていきたいということでこのムーブに
9:10頃、ちょっとお腹が痛いのでトイレへ
少し混んでいて焦ったが、9:20頃にはコンテスト会場へ戻る
その後、9:24頃にrisujirohがトイレへ
あと5分か〜 しっかり初動のイメトレしないとな Seoulと違ってYokohamaは問題が3部あるから、自分のを取って残りはチームメイトが取りやすい位置に置いて...
...なんか周りがざわざわしてるな 何でだ？
ぼく「なんか周り騒がしくないですか？何かあったんですかね」
idsigma「なんか開始を5分早めると言っていませんか？」
・・・
（＾ｖ＾）？？？？？？？？？？？？
え、やばいって まだ人揃ってないって
ICPCルールは初動が大切なんだって 開始直後人いないの致命的だって
やばいって
え、どうしよう
などと騒いでいるうちに
ICPC 2019 Wakuwaku Regional Contest スタート
コンテスト
まあいないもんは仕方ない risujirohがB担当だったのが不幸中の幸い
Aの問題文を読みます 題意が分かりません
もう一度読みます 題意が分かりません
かなり帰りたくなる
サンプルエスパーで題意を把握する
この辺でもう環境構築が終わる 待って まだ考察始められてない
とりあえずPCが空いているのも勿体無いので、ガバガバ考察でAのコーディングを始める
なんか多分この辺でrisujirohが帰ってくる 本人も焦ってた それはそう
「上げる高さの最大値決め打てば最適なスイッチの押し方は流石に自明だし、上げる高さの最大値を全探索すればええやろ！」と言って実装する
サンプル1, 2でok
サンプル3で実行に無限時間掛かる 誰か殺してくれ
引き算を毎回馬鹿真面目にやっているところを割り算でサボれば良いのだが、なんかもう色々焦ってるので「上げる高さ限界ギリギリのときだけ試せばいいだろ！」とか考え始めて別のところで高速化しようとする 証明とかなんもないけどサンプル試すと
なんとA問題を通すまで19分 最悪の滑り出し
...と思いつつ順位表見たら10位くらいだった とりあえず大戦犯ではなかったようで安心する
後ろの問題を読むに当たって「何読めば良いですか？」と聞くと、「IとJのFAが出てる」と伝えられる え、マジ？
見ると確かにそれっぽい色の風船がある
ということでIを読む あーなんか出来そうだな え、でもこれ開始数十分で通るの？マジ？
Jに軽く目を通す そっ閉じする
この辺りでrisujirohがBを通してた 自分はこのときIを読んでたけど、なんかCが出来たとかやっぱり嘘だったとか後ろでやってたらしい(?)
それにしてもIが簡単に出来る気がしないのでなんかおかしいなと思ってよく見ると、A、BのFAを表す金色の風船にくっついているただの風船だった ICPC経験が無い人間でチームを組むと、こういう悲劇が...
とりあえずPCが空いているのは勿体無いので、現時点で多少なりとも考察が進んでいるIを書き始める
「うーん、とりあえず潰せるところは潰したいな こういうときは、SCC！」と言ってSCCライブラリを写経し始める
(x_i, y_i)と(y_i, x_i)を全て有向辺として追加してSCCをする
全ての頂点が同じ強連結成分に入る
「あれ〜写経ミスったかな〜？」と言ってソースコードを印刷し、Hが実装出来そうというrisujirohにPCを譲る
席に戻って頭を冷やす
この10分間の自分、IQ2か？？？？？？？？？？？？
本当に死にたくなった こういうときはSCCじゃなくて二重辺連結成分分解だし、与えられる無向グラフは連結なんだから2通りの有向辺を張れば当然全ての頂点は同じ今日連結成分に属するし、写経は完璧だった
こうして無事チームのペナルティを破壊する 何の為にAB速解き戦略を取ったんですか...?
そして以上の考えに至ると同時に、背筋が凍る
二重辺連結成分分解ライブラリ、持ってない...
終わった...
と思ったが、何とidsigmaさんが持ってきていた 終わってなかった
Hで詰まったらしいので印刷デバッグをして、その間にidsigmaさんが二重辺連結成分分解の写経を始める
クソザコニートぼくくんは、ACが出ていたE、Gあたりを読むことに
E:ちょっとDilworthの定理みがある問題だよね こういうのはrisujirohが得意だし後で投げたいなー
G:余る文字列をノードにすればDijkstra出来そうだけど、各ノードに達するごとに全文字列見て遷移先ノードを調べてたら間に合わないな どうしたものか
risujirohがHのバグを見つけて通す
程なくしてidsigmaさんの写経も終わる
risujirohにE読んどいてと言いつつ、Iを再開する 流石に早い段階で手を着けるべき問題でないことは分かってはいたんですが、PCが空いてるのは勿体無いので...
しばらくして、risujirohからEの解法が飛んでくる 多分かなりアタリ解法で、実装が軽かった 10分程度で実装してAC
更にGの解法も飛んでくる 「頂点に来る度に文字列を見るのではなく、最初に文字列を見て辺を張って、頂点と辺を陽に管理する 一見辺がかなり多くなりそうだが、実際は多くならない」と言われたので、「すごい」と言う
これはまあまあ実装が重くて苦戦するもAC
順位表を見ると、流石にそろそろ本格的にIに取り組むべき頃合いだという話になる
二重辺連結成分分解をする、二重辺連結成分の中ではよしなにやる、いよいよ二重辺連結成分同士を繋ぐ橋の処理を行う段階になって、気付く
これ、パスクエリを行わないといけないから、HL分解しないといけなくないか
なんとこるとんくんはカスなのでHL分解の実装が出来ず、チーム戦ではいつもrisujirohに投げていたのです...
謝りながらrisujirohに「これHL分解でやって」と言う
1-indexedの二重辺連結成分分解ライブラリと基本1-indexed処理のコーダーからライブラリ実装完全0-indexedコーダーへ、感動の引き継ぎ
こんなクソ案件でも一切不満を漏らさずに実装を始める 偉すぎるだろ
なんか意外とすぐ実装してくれた サンプルを試す
大体合っていそうなのだが、何故か答えに「頂点0から頂点0への有向辺」が2つ出力される 絶対1-indexedコーダーから0-indexedコーダーに引き継いだせいだろ
カスなので答えを出力するときに「頂点0が関係する辺は無視する」処理を加えると
submit
3人全員が実装に携わっていて、200行以上あるコード
本当にデバッグしたくない
頼む 通ってくれ
PROBLEM I WRONG ANSWER
終わった・・・
人数分コードを印刷 憂鬱デバッグの開始
こんなデバッグどうしろって言うんだ...
そもそも自分の書いたところにバグがあるとも限らないのにデバッグしないといけないなんて...ん...?
...
...
PROBLEM I CORRECT
チームメイト、本当にスマン...
(もう一個カスだったのが、これ木上でimos法すればHL分解いらなかったんですよね ちゃんと考えれば最後まで1コーダーで行けたのに...いやそもそもHL分解出来ないのが最低なんですけど...)
何はともあれ、順位表凍結直前にIが通って無事6完となる 残り時間は30分間程度で、厳しいが何とかあと1問通したいところ
risujiroh「こるとんまだCほとんど時間掛けてないよね 考察してみたら？」
そう、今回は実装で大忙しだったので、残っているCDFJKのうちCは概要は知っているものの殆ど考察していないし、DFJKに至っては問題概要すら知らない状態だったのだ
ぼく「確かに でも一応他の4問も概要知っておきたいな 概要教えて」
risujiroh「DとJは幾何で、間に合わないのでやりません」
ぼく「ok じゃあFとKの概要を教えて」
risujiroh「FはN個のノードがあって、それぞれについて、-10^18から10^18までの状態があって、それぞれのノードについて遷移条件が定められていて、これに当てはまるならこっちの条件に従って状態が変わって、当てはまらないならこっちの条件に従って状態が変わるようになっていて、このとき...」
ぼく「悪かった Cやろう」
改めてCを考える よく考えると、等差数列でchmaxする感じでうまいことdpの遷移が出来るのでは？という感じになる つまりこれは
ぼく「これ線分追加CHTで出来るんじゃね？」
risujiroh「そんなもんないけど」
ぼく「おわりです」
と言っても仕方ないのでもう少し考えると、追加する線分の傾きは高々2種類なので、遅延セグ木を2種類持てば良いのでは？という気持ちになる
これをrisujirohに伝えて遅延セグ木を写経してもらい、ギリギリまで考察を詰める
しかしそんな短時間でこの問題の考察を詰められる訳も無かった
途中座圧も必要で時間がかなり厳しいので、遅延セグ木の写経が終わった時点で即実装に入る 確かこの時点で残り10分くらいだった
とりあえず必死でコーディングする 座圧が終わる 残り5分とか言われる
ぼく「え、これ終わるんか？間に合わんけど？」
ぼく「いや座圧いる？いらなかったよね？ねえ？座圧バグってない？」
ぼく「あーーーーいやギリギリ間に合いそう でもこれ遷移式ちゃんと合ってるのか？何も分からん 誰か助けて」
とか言いつつ、残り1分くらいで実装が終わる
終わった...
つぶあんと目が合う Cの風船をアピールしてきた ばか あほ かす まぬけ
結果は6完741ペナで10位だった
「もっとやれたはず」という気持ちもあるにはあるが、客観的に見ればかなり上手く行った方だったと思う この結果で上手く行った方だと言わざるを得ないのはかなり悔しいんですが...
懇親会
何だかんだでやりきった満足感と重実装の疲労感が入り混じった状態で懇親会へ
他チームやJAGの方たちと談笑してると、企業賞の発表が始まる
"10位"というキリの良い順位だったので、企業賞が無限に贈られる
10位、企業賞が美味しすぎるだろ #icpc2019yokohama pic.twitter.com/FHOyjXm86r
— こるとん (@kyort0n) 2019年11月17日
まだあった クソみたいな順位で無限に貰ってしまって申し訳ない #icpc2019yokohama pic.twitter.com/sJf7ZtFFae
— こるとん (@kyort0n) 2019年11月17日
らてあさんとかに「賞を貰うときに真顔になるな」と言われたんですが、違うんですよ 後半「こんな順位で無限に企業賞を貰ってしまって申し訳ない」と恥ずかしくなってたんですよ ゆるして
その後企業賞を貰ったAobayama_dropoutの喜び方がかなり良かった 斯くありたい
懇親会では最初は周りの競技プログラマと談笑していたのだが、周りの人が謎の紙を持っていることに気付く
どうやらGoogleのブースで「各人ごとに異なる入出力例のみが印刷された紙が1枚ずつ渡されるので、それらから問題を推測して答える」という遊びらしい
当然皆競技プログラマなので、こういうのがあると、着手───
実際にはその場にいた数十人分のサンプルを見て考えていたのですが、流石にそれを全部覚えてはいないので、適当に問題に合わせた入出力例をいくつか作って置いておきます
Input
4 7
4 3 3
3 2 2
1 3 6
2 4 1
2 1 2
4 1 6
3 1 8
1 2
Output
8
Input
3 6
1 2 2
1 3 4
2 1 3
3 2 4
2 3 1
1 2
Output
6
Input
5 7
1 2 8
2 3 4
3 2 1
4 1 3
3 4 5
1 4 2
3 1 6
5 2
Output
8
これだけだと少なすぎるので答えようが無いと思いますが、大体こんな感じです
あえて答えはここに書きません 多分Twitterで調べれば答えが見つかると思います
Googleのサービスは金輪際使用しません
懇親会後、10名くらいでまたしても中華街へ
中華街、料理が美味しいので無限に食べられてしまう 危険
なんとsmikenさんが全員分奢ってくださった...(ありがとうございます)
お礼にJAGの宣伝をしておきます
Day.3
グループCの企業見学に行く
え、Googleマップってトイレ調べられるの
— こるとん (@kyort0n) 2019年11月18日
神！Google様最高！
Google最高！一番好きな会社です！
え、他グループの民すまん... pic.twitter.com/Q0LuFLSleQ
— こるとん (@kyort0n) 2019年11月18日
NEC最高！一番好きな会社です！
お昼はしながわ水族館 大はしゃぎする
うおっｗ おうおうおうおっっｗｗｗｗおうおうおうおうおっうおうおっｗｗｗｗｗｗｗｗうおっｗ おうおうおうおっっｗｗｗｗおうおうっおうっおうっｗｗｗおうおうおうおっｗｗｗパァンッパァンッ(ヒレを叩く音)うおっｗ pic.twitter.com/fjE93C9kwc
— こるとん (@kyort0n) 2019年11月18日
僕「オットセイ好きなんですか」
— てぃーいけ (@1119_2916) November 18, 2019
こるとん「オウｗパァンｗ（ヒレを叩く音）」
イルカショー、1番騒いで楽しんでいるのこるとんさん達のエリアと僕、yamadさんのエリアだった
— ツバサ (@emtsu_ba) November 18, 2019
お恥ずかしい限りです...
その後3社目のHuaweiへ行き、解散する
新宿で集合してICPC勢とボドゲカフェに行ってたっぷり遊んで解散
イルカショー感動しました。特にラストシーンで @kyort0n が親指を立てながらプールに沈んでいくシーンは涙無しには見られませんでした
— るま/ApplePenを手に入れて圧倒的成長（予定） (@lumc_) November 18, 2019
人を殺さないこと
こうして初めてのICPCが終わりました
risujirohとチームを組むことが決まったのが1/20
idsigmaさんがチームに入ったのがその翌日
気付けば約10ヶ月間 あっという間でした
本当に楽しかった お疲れ様でした
ところで
idsigmaさんが今年で引退なので、弊チームの来年の新メンバーを募集しています
後日談(2020/11/08)
久々にAOJ-ICPCが更新されて、ICPC2019の問題も登録された
ウキウキで当時のコードをAOJに投げ直すとWAが出る
？
色々と調べると、2つのことが分かった
1つ目は、AOJで過去にACしているコードを投げ直してもWAが出たことから、AOJのジャッジが壊れていそうだということ
2つ目は、当時のコードがvectorの範囲外参照をしているということ
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
弊チーム、完数マイナス1です...
_aizu/status/1195569694251503618?s
8?s=20
The 2019 ICPC Asia Seoul Regional Contest 参加記
okimochi(idsigma, risujiroh, kort0n)で韓国に行ってきました
出発前夜
明日出発なのにまだチームライブラリ白紙です
— こるとん (@kyort0n) 2019年11月6日
荷造り進捗0だし
— こるとん (@kyort0n) 2019年11月6日
チームライブラリのレイアウトが決まる(出発前夜23:17)
— こるとん (@kyort0n) 2019年11月6日
ライブラリ完成(出国9時間半前) pic.twitter.com/3NSZz7pBMh
— こるとん (@kyort0n) 2019年11月6日
荷造り完了(出国9時間前)
— こるとん (@kyort0n) 2019年11月6日
3時間だけ寝る
— こるとん (@kyort0n) 2019年11月6日
準備は...ちゃんとしよう...！
公式サイトどれだけ探しても持ち込み資料についてのルールが見つからなかったので、去年Seoul Regonal Contestに参加したbeetに色々聞いて準備しました ありがとうbeet
Day.1
韓国着いた！ pic.twitter.com/uWmO2zz04C
— こるとん (@kyort0n) 2019年11月7日
ハングル1文字も読めなくてビビる ただの記号にしか見えない
空港は大体看板に日本語も書いてあるのでイージーだったが、電車等では基本的に駅名が韓国語でしか表示されないのでかなり大変だった
何やかんやでホテルに着く 往復航空券+3泊4日ホテルが3人合計で100k 安すぎておったまげた
安宿だからかホテルWi-Fiがあまりに貧弱 まぁ通信容量無制限の海外用ポケットWi-Fi契約してきたしこれを使おう...
...と思うが、何故かポケットWi-Fiがここで不調に かなり険しい気持ちになる
貧弱Wi-Fiに繋げてなんとかクレームを付ける とりあえず空腹なので外で店を探す インターネットも無しに異国の地を歩くの不安すぎた
Day.2
寝て起きたら昨日投げたクレームに対応してくれて、ポケットWi-Fiが繋がるようになっていた ありがてぇ...
そして外出する準備をしていると
practice当日の10:58に、ライブラリやキーボードの持ち込みについての指示が出ましたが.............. pic.twitter.com/u32V97XIsm
— こるとん (@kyort0n) 2019年11月8日
なんで？
まあ結果的にライブラリの要求仕様は去年と同じだったので問題無かった ありがとうbeet
practiceが昼からだったので、それまで近くのショッピングモールを適当に散策する
— こるとん (@kyort0n) 2019年11月8日
これすき
韓国のネカフェ座席数がやべえ pic.twitter.com/9buzSiEzrw
— こるとん (@kyort0n) 2019年11月8日
これすごい
— こるとん (@kyort0n) 2019年11月8日
これおいしい 日本にも出店して
良い時間になったのでpracticeに向かう
— こるとん (@kyort0n) 2019年11月8日
横浜が基本英語進行だと聞いていたのでソウルも英語進行だと思っていたが、入場案内が韓国語でかなり焦る やばい
何だかんだでその辺のスタッフが英語通じたので何とかなった
注意事項説明は英語と韓国語両方だった 助かった
We will begin the contest on time.(強い意志)
— こるとん (@kyort0n) 2019年11月8日
DO NOT TOUCH ANYTHING
— こるとん (@kyort0n) 2019年11月8日
「コンテストルームに入ったら、指示があるまでは"DO NOT TOUCH ANYTHING." 失格になります。 "DO NOT TOUCH ANYTHING."」と一生言われてた 多分"DO NOT TOUCH ANYTHING"カウンター30くらい
コンテストルームに移り、practiceが始まる
問題は2018 Seoul Regonal Contestから3問
Practice Aは去年のD
Practice Bは去年のE
Practice Cは去年のL
去年のE...?
(解いたことが無い人はこの先を読む前に是非解いてみてほしい
Dashboard - 2018-2019 ACM-ICPC, Asia Seoul Regional Contest - Codeforces
多分考察は新ABC-E程度で、実装は新ABC-E強〜新ABC-F弱程度だと思います)
以下Seoul Regional Contest 2018の重大なネタバレ有り
何なのかと言うと、こういうことです
practiceに去年のE(邪悪コーナーケース問題)入ってるwwwwwwwwwwwwwww
— こるとん (@kyort0n) 2019年11月8日
https://twitter.com/kyort0n/status/1188019884766023681?s=20
https://twitter.com/kyort0n/status/1188019884766023681?s=20
2018-2019 ACM-ICPC, Asia Seoul Regional Contest
— こるとん (@kyort0n) October 26, 2019
9完最遅で(オンサイト参加チームのみで)10位
Eで入出力TLEにハマった上コーナーケースを見つけられず11ペナ出した... pic.twitter.com/mpkE4IYYRp
Eのペナルティを見るとヤバさが分かると思います
去年のセットはチーム練しており、そのときはAはidsigmaが通しており、BとCは僕が通していた
まあpracticeでは流石に1人1問実装した方が良いということになり、BとCの一方をrisujirohに譲ることにする
risujiroh「どっちやればいい？」
ぼく「Bやって(即答)」
idsigmaがAを通したので、Cをやる エディタをいつも通りの感じにするのが思ったより大変ということが分かってビビる 結局色々妥協するもかなりやりづらくて、初めて実装したときより時間が掛かる
riujirohがBを実装して提出すると、WRONG ANSWER
ぼく「よし！！！！！！！！！！！！！！！！！！！！！」
チームメイトがWAを出した瞬間にガッツポーズする人間→@kyort0n
— 自朗 (@risujiroh) 2019年11月8日
自分がコーナーケースで散々苦しんだ問題で目の前のチームメイトが死んだらガッツポーズするだろ
— こるとん (@kyort0n) 2019年11月8日
時間がないのでコーナーケースを教える ブチ切れてた
何だかんだで皆慣れないエディタに苦戦する等の要因で時間ギリギリに 余った僅かな時間で何となくCLionを弄ると、その使いやすさに感動...
CLionの使い勝手の良さに感動した弊チーム、ホテルに戻ってCLion練習会を開くことを決意
— こるとん (@kyort0n) 2019年11月8日
CLion最高！！！！一番好きなIDEです！！！！
— こるとん (@kyort0n) 2019年11月8日
ホテルに戻るとこのリプライが届いている
@kyort0n はじめまして！今日の練習試合お疲れ様でした。ソウル地域大会って外国の参加者にあまり親切ではないですよね😅もし明日の大会についてわからないことがあったら気軽に聞いてください😊
— 南南西🍤 (@Namnamseo_jpn) 2019年11月8日
韓国、あったけぇ...
調べたら789の方だったらしい 本当に有難うございました
韓国、サイコ〜〜〜 pic.twitter.com/XuniwqdOUh
— こるとん (@kyort0n) 2019年11月8日
CLionの最低限の使い方を覚える 「明日構文解析出たらよろしく」と押し付け合いながら就寝(弊チームは構文解析担当がちゃんと決まっていなくて、いつもは大体手の空いた人がやってます)
Day.3
朝が早い
集まると改めて諸々の説明をされる この日の"DO NOT TOUCH ANYTHING"カウンター20くらい
コンテストルームに移る 周りのチームが普通にマウス触ってPCのスリープモード解除しててウケる 前3チームくらい連続して普通にPCのスリープモード解除されてる 治安が悪すぎるだろ
まあスリープモード解除されるくらいは事故でもありそうだし仕方ないかなと思うが、いくつかのチームが開始1分前時点でスリープモード解除した上にログイン画面まで進めていた それはシンプルに不正じゃないか？
コンテスト
idsigmaがABCDEFを読み、risujirohがGHIJKLを読み、ぼくが最初にエディタの設定をすることになっていたので、する
エディタの設定を終えると、「EFGHを読め」と言われたので、読む
E:なんか出来そうな見た目 なんかうまい貪欲とかありそうじゃない？←なさそう まあ後回し
F:あーなんか今年の幾何問題不可能そうだな... とりあえずrisujirohに後で読んでと言って放置
G:なんだこれ むずそう
H:出来なくはなさそうだけど、多分解けても実装重いだろうな 後回しでいい
idsigmaにIが簡単そうだと言われる 読むと確かに簡単で、実装を始める
なんかこの頃にはもうAが通ってたらしい いつ通ったんだ？
無事実装を終えるも、サンプルが合わない 何故か「隣接する2点の距離をans以下にする」ではなくて、「隣接する2点をans以上離す」で実装してしまっていた は？
一旦PCをrisujirohに譲ったらJが通ってた その後Iを通す
その直後、idsigmaにLの解法を伝えられる これはバグらせずにサッと実装して通す
「B得意そうだからやって」と言われ、問題概要を伝えられる
考えると、うまいこと部分木の情報を1つの値で表して木dp出来ることが分かる
しかし、risujirohが「これ最大ケースだとlong longでオーバーフローしないか？」と言い始める 確かに...
「とりあえずlong longで提出して、落ちたらint128で書き直して再提出しよう」と言って、実装を始める int128の出力を書くのが面倒だったので説得出来て良かった
しかし、ここで伝達ミスで、「全ての葉のペア」ではなく「全ての頂点のペア」だと思って解いてしまっていたことに気付く 大まかな解法が壊れる訳ではないが、遷移式が書き直しになる 伝達ミスは最近のチーム練でも何度もやらかしてたので気をつけてないといけないと思っていたのに油断してしまった...
更に最悪なことに、元のコードを少し弄ったらスパゲッティになって酷いことになる コードを印刷して、Hが解けたと主張するrisujirohにPCを譲る
暫くしてバグを発見して直すとサンプルが合う 提出するとAC これに1時間くらい掛かったの本当に酷かった...
ところで
そういえばソウル B、オーバーフローするケース見つけたけど
— 免許更新をする (@rian_tkb) 2019年11月9日
ちなみに -4734320840174338048 になりました
— 免許更新をする (@rian_tkb) 2019年11月9日
これがICPC
順位表を見るとKがそこそこ通っているので読む
未証明だけど、ある平面を固定したときにそれらを跨るような点の取り方をするのは損だなぁ(雑)という気持ちになる 平面の取り方を全探索すると、これでO(N^4)となる
この先は幾何っぽい考察が必要だねという気持ちになる risujirohがHを通したので、これの続きを投げて、自分はGに移る というか、このセット実質幾何が2問か...
何かこの辺で順位表が凍結する 2年くらい前の韓国大会でも1位チームが残り1問になった時点で凍結されたと聞いたので今年もあるかなと思っていたが、実際1位のCafe Mountainが残り2問になった時点で凍結された 自由すぎるだろーと思っていたけど、そういえばルールで順位表凍結時刻は指定されてないんですよね...
Gを考える 色々考えると、左から順番にdpをすれば良いということが分かる これ遷移式が、「2つの異なる区間の中の最小値のうちのmin + 1」みたいになるんですよね こんな遷移式初めて見た...
とりあえず区間minを愚直に求める方法で甘えて残りを実装すると、無事サンプルが合う あとはセグ木を写経して区間minを高速に求められるようにするだけ 勝ったな！
ウッキウキでセグ木を写経してサンプルを試す バグる 人は何故...
写経をミスっていました 提出するとAC
risujirohが「Kの平面全探索は軸を1つfixして、もう1つ通る点を偏角ソートで順番に見ると高速に更新出来るから間に合う」と言い始める なんだそれ やべー
risujirohがKの実装を始める 残りの問題のうち手が出せそうなのはCとEあたり Fはrisujirohが多分無理と言ったので諦める Dはなんも出来る気がしない(これも結局伝達ミスで問題を勘違いしていたんですが...)
眺めていると、Eが解けた気分になる Kと並列で実装を始める(お互い詰まったら印刷して交代)
Kのサンプルが合ったらしいので提出するが、WA というかKのサンプル貧弱すぎるだろ
その後Kを何度か提出していたが、全然通らなくて辛そう
Eの実装が終わる サンプルを試すsample2~sample4はok sample1の3番目の答えだけ合わない
まあこれは後は少し境界条件が間違っているだけだろうという気分になる
暫くしてKが通る なんか尺取りでバグっていたらしい？
KをやっていたrisujirohにEの現状を伝える すると、
「サンプル1で3番目の答えって2で合ってるんじゃないの？これとこれとこれを取り除いたら連結成分数2つになると思うけど」
と言われる 確かに？？？？？これ出力例間違ってないか？？？？？
出力例のミスを信じてsubmitすると、一瞬でWAが返ってくる そういえば3番目の答えは頂点を2つ取り除いたときの答えでしたね......
残り10分くらいになっていよいよ大幅な書き直しをする時間は無くなってきたので、ドキドキソート評価関数ガチャを始める(こういうのあまり好きじゃないんですが、流石に時間が無かったので...)
結局通らずに終了 以上8完1043ペナでした 凍結時点では1位10完投Cafe Mountain 2位9完789で3位以下は7完以下だった為見た目の順位は良いが、まあ凍結から2時間経ってるのでよそのチームも沢山通しているでしょう...
反省点
Bがすぐ通せないの最低 伝達ミスを考慮しても遅すぎる
長いこと順位表が凍結されていたので周りの情報は分かっていなかったのだが、終わってみればEはオンサイト1ACの地雷問だった これ手を付けるべきではなかったのかもしれない...(オンラインミラーはそこそこ通ってた) まあ僕の解法はO(N^2logN)だったんですが、どうやらこの問題はO(N^2logN)はTLがかなり厳しかったらしい？じゃあ実装出来てても厳しかったんだろうか そもそも自分のが本当に合っていたかは分からないんですが
HとKで「試す順番を工夫すれば更新が高速に行えるので計算量を落とせる」に気付かなくて解ききれなかった これ苦手分野なのかもしれない...
コンテスト後
日本勢いつものperiscopeをする しかし進行が韓国語...
結果は11位でした
okimochi、ソウル11位でした！お疲れ様でした！ pic.twitter.com/9R3dkBTpig
— こるとん (@kyort0n) 2019年11月9日
10位以内に入ることも出来なかった 良い順位ではないんですが、でもこれは冷えではなくて多分実力相応くらいなんですよね...
話を聞いてなくて壇上に呼ばれることに気付いていなくて、慌てて壇上に向かう 慌てていたのでiPadを閉じてしまい配信が途切れる 配信聞いてた人すまんな いや11位で表彰されるとは思わなくない？
1位のCafe Mountainが全完だった えぇ...
— こるとん (@kyort0n) 2019年11月9日
こるとん㊙️情報
— こるとん (@kyort0n) 2019年11月9日
辛いものが苦手
誰か助けてくれ
— こるとん (@kyort0n) 2019年11月9日
この夜は何も無かった いいね？
Day.4
最終日にギリギリ少し観光した pic.twitter.com/Ji9rF1I4en
— こるとん (@kyort0n) 2019年11月10日
@potetisensei 石焼きビビンバ pic.twitter.com/gqlkel9csB
— こるとん (@kyort0n) 2019年11月10日
ただいま！ pic.twitter.com/0ZlAFHHJ5g
— こるとん (@kyort0n) 2019年11月10日
次は来週の横浜ですね 横浜でお会いする皆さん、宜しくお願いします
HACK TO THE FUTURE 2020予選
HTTF2020予選に参加しました。結果は22位(4963718点)でした。
① 正の得点(48047点)
Text(cat)
0
② 拡張Dijkstra解法(4961249点)
(座標, 向き)でグラフを拡張して、直進はコスト0, 方向転換はコスト1のedgeを張って、拡張Dijkstraをする。則ち、「このマスでこっちを向いているロボットがいるとき、いくつの方向案内を新たに置けばゴールに着けるか」を求める。
コストが正であるロボットのうち、最小のコストを持つロボットについて、ゴールに着けるように方向案内を置く(そのようなロボットが複数存在する場合は、インデックスで最小のロボットを採用する)
再び拡張Dijkstraを行う。これを、(ゴールまで到達する道が存在するような)全てのロボットがゴール可能になるまで繰り返す。
実行時間は約100ms
③ 拡張Dijkstra + ロボットのインデックスシャッフル(4963153点)
②はロボットのインデックスに応じて結果が変わる。
Time Limit 一杯まで、毎回ロボットのインデックスをシャッフルして②を繰り返す。
④ 拡張Dijkstra + ロボットのインデックスシャッフル + 不要な方向案内削除(4963718点)
最後に不要な方向案内を削除する。
その他試したけど無意味だったこと
コストが同率な複数ロボットが存在するとき、ゴールまでの距離が最小(最大)のロボットを採用する。
スコア下がった
ロボットのインデックス順で焼きなまし
一回のシミュレーションで100ms掛かるのに焼きなまし、意味ある？無いね
試すべきだったこと
Dijkstraの代わりに0-1BFSで高速化
コスト1種類しか使ってないので当然0-1BFSでok
これ気付かなかったの酷すぎる...「本職がマラソンじゃなくてアルゴだから」とか言い訳も出来ないレベルの失態ですね...
非通過のマスを通過するときボーナス
上位陣のコードをいくつか実行して確かめたのですが、自分のコードと上位陣のコードを比較したところ、Bの差はほぼ無く、Cの差で負けている状態でした。
Cを高める上手い方法が分からなかったので殆ど無視してしまったのですが、こうすれば良かったのか...
おわり
ほ゛ん゛せ゛ん゛い゛き゛た゛か゛っ゛た゛
