雑記

競技プログラミングについての話題(?)

夏、海、空、雲、うく、JAG、ACPC、富、名声、力、ウクニキア。

JAGとかACPCとか最近あったことを書きます

人間というものは反省ができるもので、何が言いたいかと言うと、高垣楓のイベントで心が折れて走るのをやめたのに高垣楓のイベントで走り始めた

さっきたまたまDEGwerさんと順位表で会った

人生

世間一般の高校生が過ごす夏休み期間中に全然出かけなくて、でかけたのが8月31日とかだったと思う(しかも散歩)

昨日あたりに映画を見た、各方面から怒られないのかなあれ

GAG夏合宿

気づき

エメラルドとラズヒルドは勢いが似ている

これはそれを形にしたもの


「バスガス爆発」よりも「8月末夏初外出」のほうが身近で覚えやすい


目にもの見せてやる・・・過度な抽象化

わがままな人間・・・こうも明言を避けられるとパパが誰かかえって気になりますよね

ままならない・・・消去法でパパになるしかない

傾向

「ひとりであそんでなさい」から発展に発展を重ね、ここ1ヶ月くらいはずっとしかるねこみたいな口調になってしまっている


JAG夏合宿

day 1

まず起きることができません

PCKとJAGと椅子があったみたいでTwitter大混乱みたいなTLになってしまいよくわからなかった

day 2

うしくん(我が家の非常食)と一緒に出ることになります

いつもどおりガバガバで、コンテスト開始時にまだアカウントのことで混乱が発生していた

頑張って英語を読むとAがやるだけ、普通に5分くらいかかってるけどまあ書いて提出します AC

開始10分くらいでお腹が壊れます、チームからぼくが抜けうしくんがキリトくん状態になる

なんかうーちゃん☆がマジで寝ぼけていてBやってバグらせておりバトンパス 30分時点くらいでAC

他の問題を読むんですが、何もわかりません(エーーーーーッ)

瞑想していたらうしくんが無言でHを書いてぼくに提出してきます、それを(うしが)苦しい高速化してAC、なんでぼくに見せたんだよ

なんかこのあと13時くらいを過ぎたあたりでお昼ご飯食べたり遊んだりしてチームが空中分解して終了した

day2 : ooxxxxxoxxx(26位)(は?)

day 3

何してたか忘れたけど遊んでたらいつの間にか徹夜してて10時前になっていた、うしからコンタクトきたなと思ってよく見たらうしも寝てなくて草生やす

お互いマジで眠く、2完できればいいだろみたいな頭をしていた

さすがに会話が意味不明なんだが

f:id:Luzhiled:20180925022018p:plain

Aを読む、うーんうくにきあだねえとなる

なんかうしが開始3分時点でBを通せる雰囲気になったので一瞬でパス、生まれる謎のFA

この老眼には苦しい感じすき

f:id:Luzhiled:20180925022232p:plain

Aを考えるとよくわからない感じだったので適当にサンプルだけ合わせて出す、なんかACしたのでよし(うし)

うしにCどうよと聞いたら微妙と言われ、概要を聞いたらそのままやればいいのではとなる、そうじゃんとなる

うしに書きなさーい!とか言ってヘラヘラしていたら2分くらいで書いてきてマジでビビった AC

このあたりで一旦全部の問題みちゃおうなとなり手分けして日本語らしきものに変換していく

Jがやるだけっぽいとなる、うしが書く、素数判定に失敗してWA 直してAC

書いている間にぼくはIみたいなのを処理するべきだなとなるので考えるんだけどなかなかうまくいかない

なんかうしくんが無言でGの実装を始めます(言いなさーい!)、まあパソコン使っていなかったのでよし

なんか実装に苦戦していたみたいで普通に1時間くらいかかってしまっていた記憶がある

1回出してみたらWA、なんかちょっと直せばいい雰囲気があったのでそのまま直してAC(わーい)

うしくんが苦行をしている間にIをつめまくっていたのでノンストップ実装をします 4分くらいでAC

このあたりから意識があやうくなり、

うし「D解けました、解法:うくにちあが解いている、Dやります、Iよろちくでつね」
ぼく「もうおわったものですが」

みたいな会話をしていた

うしが実装する間にぼくが次の問題を考える

なんかKは見た目がいいんだけど誰も通していなかったので一旦スルー、希望のありそうなFを考えるけど全然ダメ(うくにちあ)

うしが // おれたちの接尾辞配列 とか書いているんだがそれが原因でTLE(草)

別のものを写経して // おれたちの接尾辞配列はありませんでした とか書かれていてさらに草、DをAC

なんかどう頑張ってもFはわからず、K得意そうだしやるかと言いながらKを考えてみたら一瞬でいいところまでいける

1から順番に前に寄せていく操作は自明に最適なのでやる、そのあとのパートはふつうにやってO(N)っぽい見た目しているけど証明がパッと出ないので雑貪欲をする、WA

うしにパス 雑貪欲の部分をふつうに書いてもらう ぼくが書いた雑貪欲がまだ残っていてWA(わかりにくい見た目やめろ)

さすがにTLEかな〜と思いながら出したら普通にACして二人で草草言い合う お前そういえば主食草だろ 何ラーメンくってんねん

Hはどう見ても線形計画問題というものですね〜となるが、お互いよくわからない

まあどう見てもF以外解けないでしょ、となりいい加減現実と向き合うぞとなりFの考察にとりかかります

とりかかるんですが、

になり、実験がスタート

Bob(ぼく)あまりにも勝てなくね?となる、全体のxorが1ならBobるということがわかりこれで出すか!wとか言いながら提出 WA(ここにあたりまえ体操の画像)

ぼくが何も考えずに「や、1だけじゃなくて立っているbitが1つとかなのでは」とか言ったらうしくんが「ん、それマジかも」とかいいだして提出をする まだWA

もう少し実験を睨むとxorが0のときが怪しいとなる、しかもなんか全部偶数、あやしいね、マスターこれも追加で とか言いながら書いて提出したらAC(は?)

一切の考察をしなかったのに一切の寄り道もしないACをしてしまったのが面白くて小一時間笑う

なんかEにやばそうな幾何(ライブラリもってねえ)、Hにさっき解けなかった謎がおかれておりこれはダメそうだなあとなる

最後にうしが威圧をする

f:id:Luzhiled:20180925025351p:plain

そしてこれがフラグになります

さすがに流れがキレイすぎるし日本むかし話の続編で日本うし話とか出すなら教訓として編纂してほしい

全体的な感想

睡眠は大切

ACPC 2018

なんか去年は旅行気分で行ったんだけど今年はいかなかった お金は難しい

day 1

や、冷静に考えてデレステのイベント初日では?となる

アタポン形式だったのでまあ序盤は潜伏して集めるだけだよねとなる

まあTwitterでできなかったのでACPCのコンテスト自体についての言及はここですべてさせていただくんですが、

day 2

会津セット、やりたいなあとなる

非常食はオンサイトに行ってしまっているためらてまるたと組みたかったがバイトに行ってしまった

2日目終了時点で潜伏を終える予定だったのでイベントアイテムを9900個まで集めます、疲れたのでそのあと寝た

day 3

らてまるたがバイトじゃなかった(ヤッター)

いつもどおり開始時点では起きててくれない

なんか適当にA書いて出したらWA、なんだこれ

Cになもりから生えている部分を切除するやつが出ていたのでらてまるたに解いてと伝える

パソコン起動するので待ってと言われる

Bがマジでわからねえ、LCTで常勝してやろうか?????となる

順位表を見てそもそもAがWAだったままなことに気がつく 治す 通る

Bがわからない、本当になんだこれは状態が続く

その間にらてまるたがCを通す(わー)

諦めてBを捨てます、Eに某某某某某某某某某+木DPみたいなものが置かれていてうくですね〜って伝えたところ、らてまるたがもっとシンプルに解けるよと言いながらAC

そのあとDが見た目Dijikstraでいけるじゃ〜ん(適当)とか言って実装していたところ、しばらくしたあとにらてまるたがそれまずくね?と言いながら反例を投げてくる

投げられた反例でも正しく動作していることに気づかずにあっそうじゃ〜んとなる ふりだしにもどる

らてまるたがや、これ貪欲じゃんと言い始めるがこれも一瞬で反例が構築され終了

迷走が始まったところで一番最初のやつやっぱりあってんじゃんとなる、わわわわ!とか言いながら適当に書いて出したらなんかWA

これ出す順序決まってるんだからグラフじゃまずいねと言われ、DPに書き直しAC(ぼくならハマり続けるしこの復帰はマジですげえなとなった)

「らず Fみてくれよ」と言われたので「きれいな顔してる」って言ったら流された かなしい

なんかサンプルが間違っていないかみたいな話で、いや問題文読み間違えてそう〜っていって題意をちゃんと伝える

急にGが通る(?????)

F、もしかして簡単なのでは???みたいな空気になる

f:id:Luzhiled:20180925031748p:plain

Dで無駄にハマったことが尾を引いてそう

これもまあ割と瞬時に通ります

あきらかに想定じゃないやろという気分になりつつBはクエリ平方分割!wをします 時間が足りずできませんでした おわり

day 3 : oxooooo(9位)
うーんという感じ

その他競技について

何ヶ月か前に寝ぼけながら書いた桁DPの記事をもとに何らかのプロジェクト?会社?が桁DPの記事を書いていたんだが、どうやら桁DPは上位の桁からしか見ていかないという認識をされてしまったらしく、人生はきびしいなあとなった
たとえば回文数かつ何らかの数を求めよ、みたいな問題が出題されたとすると、上から決めていく場合、何桁の回文数にするのかなどの情報を持つのによけいな次数が必要になると思っていて(ほんとかな)、これは下からやるのが最適だと思う
ジグザグ数も下からのほうが楽みたいな話を聞いたことあった気がする

8月あたりから頑張ってARCを埋め立てていたんだけど4つ埋めた時点で力尽きた 再開しような

総括

競技プログラミングを、やろうね!


何この記事