Osmium_1008のブログ

コンテストの感想とかどうでもいいこととか書き溜めるかもしれません

JOI'22 二次予選参加期

はじめに

Osmium_1008のJOI参加期にブログ名変えた方がいい気がしてきました。例によってむっちゃ適当です。

結果

問題名 得点 経過時間
A 100 00:01:27
B 100 00:09:07
C 100 00:30:37
D 100 00:58:43
E 100 01:49:44
計 500 01:49:44

序盤で詰まらなくなってて成長を感じます。(誰)

行動

競技前後にどのようなことを考えていたかでです。

競技直前

コーヒーを飲んだ上で手元にポカリとラムネとチョコを用意しました。あとノートも

競技中

A問題

どうみてもやるだけなのでやります。

ここまで1分ちょい

B問題

これも適当にDFSで通りそうなのでやります。

ここまで10分

C問題

一方向ずつ考えて合わせるで通りそうなことがわかるので実装すると普通に通ります。

ここまで30分 なんか今回簡単になったなーとか思いはじめます

D問題

普通に前回と前々回を index とする DP で通るので通します。(次見る場所と前々回の見る場所を同時に動かせることを気付くのにちょっと時間かかった)

ここまで1時間弱 え

E問題

とりあえず自明な小課題2を通してから考えると切り離せるようにしたUnionFind(名前を知らない)(切り離しは

size[par[i]]-=size[i];
par[i]=i;

とかで実現できる←(12/12 18:00追記)多分これsizeあたりでちょっと計算量落ちてる けど無視) を使って

  • 各州内の道路はさきにマージしておく。
  • 州のペアごとにクエリを分ける。
  • 2州の間の道路をマージしてクエリを処理する。(判定するだけ)
  • 切る

をやるだけで O((M+Q)log²NlogQ) とかになるので(Map使いまくったりしてなければもっと落ちるはず)通りました。

ここまで1時間50分

競技終了後

いつものスプレッドシートを見るとやはり全完が結構多いのでボーダー417点ぐらいかなーと謎の予想を立てましたが 通る人数160人も確保されてることを考えると多分200点台のどこかで通りそうな気もします。

今年はノートはDで index の足し引きを考える時にちょっと使いました。

感想など

3完+αぐらいかなーと予想してむっちゃ覚悟してたら割と早く全完できたので結構拍子抜けしてました。 やはりノート書いた方が実装早くなりそうとも感じました。

提出したコード(Gist)

JOI'21本選参加記

はじめに

こんにちは。JOI の時ばかり記事を書いている気がします。色変した時などは書くようにしていきたいです。

例のごとく適当です。

結果

問題名 得点 経過時間
A 100 17:28
B 100 1:40:39
C 5 2:47:21
D 0 -
E 0 -
合計 205 2:47:21

といった感じでした。

300点でも32人いるので通過はない気がします。

1日目

朝

珍しいことに弊校の高校入試が同日だったのと僕は中三なので、これを受験していた。JOI 本選参加者ということで午後の試験を免除され、帰宅。

帰宅しようとしたら小田急が遅れていて困っていた。

午後

帰宅したら素早く食事を済ませ、JOI のガイダンスに参加。Zoom で行われていたので画面が共有されたりする度に全画面になり不便さを感じた。 10 秒の動画を視聴してコメントを打つのが音ゲーと表現されていた。動画の本数が 88 本で音ゲーなのでピアノでも弾くのかと勘違いしていた。

自己紹介動画は... define に絶起する呪いをかけられたことが印象深い。あと大量のかわいいを観測していた。

その後は恒例のプラクティス。問題は例年と同じなので速攻で全完してサーバーで雑談をしていた。

しばらくすると質問大喜利なるものが始まり、いくつか質問を投げていた。

終了後は夕食を取り、ARC まで休んでいた。JOI 本選鯖で Among Us が始まったので参加していた。

その後は ARC に参加。ARC で黄変することで本選落ち黄コーダーN銃士に参戦しようかと考えていたがぎりぎり黄色には届かず。

寝ようとしたところ地震が起こったことで就寝できず就寝が遅れた。

2日目

朝

絶起する呪いをかけられていた気がするが難なく起床。

googol 君との会話で 1 時間こどふぉったことを知り、ゆとりをもって行動しはじめる。

朝食を摂取して、準備をした。去年のように寝ぼけてかわいいようなものを観測できない。 前日そこまで長くは寝れていないので眠気があったため、コーヒーと糖分を摂取。 去年は魔剤を飲んだ覚えがあるが家にいればコーヒーを淹れられるのでそこはよい気がする。

ウォーミングアップなどはあまりせず、代わりになぜか音ゲーをやっていた。

例によって驚くほど緊張せずにいた。

競技

家なのでそこそこ食事など行動の自由度が高かった。 昼食やクッキーや炭酸水などを持ちこんで競技中に飲食したりしていた。

1 問目

直感で差を見て満たしていない範囲に足していけばいいと気付くので実装。 いくつかバグらせたが落ち着いて対処し、AC することができた。

2 問目

間の距離を持っておいて入力の合計の幅と比べれば上手く計算できそうだと気付き、実装。 ほぼほぼ AC は出たもののメモリ制限超過に悩まされ、解消するためにバグを生めこんだりして時間を取られてしまう。

メモリ制限もバグも解消し AC はしたものの、かなりのタイムロスになった気がする。

3 問目

考察するが、理解が追いつかないので全探索を実装し 5 点を獲得、ここで点数が確定する。(早い) その後は嘘貪欲を頑張って合わせようとしたものの当然不可能だった。

競技後

コードは取っておかない派閥なので書いたコードをすべてダウンロードし、しばらく休憩していた。 kichi さんが速攻で点数のまとめシートを作っていたので書きこんだ。300 点以上が多かったため本選落ちを確信。

問題の解説が始まった。が競技の疲れや眠っていなかったことなどによりかなり眠く、あまり聞けていなかった。

オンライン交流

oVice というサービスを使った交流だった。指向性を持ったアイコンを動かすことにより実地でのような交流ができた。 コア数の少ないCPUを乗せたPCだと重いという話をしていた。

最初は LT だった。JOI 卒業後の過ごし方など有意義なことが聞けてよかったと思う。

その次はゲーム大会。インサイダーゲームと少角縛り(?)お絵描き伝言ゲームの二つのゲームにわかれて交流していた。

インサイダーゲームを選んだが、前日 Among Us をやっていたメンバーが多く集まっていた部屋だった。 物を当てるのに必死になっていてインサイダーの特定がかなり難しくなっていた。 途中から Among Us をやっている部屋が出来始めていた。(かなり流行っている...)

任意解散の流れだったので夕食をとった。 戻ってくるとまだ結構残ってゲームをやっていたので、 Among Us をやっている部屋に入り、通常モードと宇宙鬼ごっこというものをやっていた。

あまりにも長くやっているので 20 時ごろに撤退した。これを書いているのは 22:30 ごろだがまだやっている。不思議。

感じたこと

去年に比べれば多少は精進をするようになっていたが、それでもやはり他人に比べれば精進不足なので来年に向けて精進を頑張っていきたいと思った。

オンラインだとゲームを介して積極的に交流できるなど利点が結構あった。 交流用として Discord 鯖は残しておいてほしいと思った

終わりに

競プロの能力はそこそこ上がりましたが、文章を書く能力は大して上がってないようです...

こんなに読みにくい文章を最後まで読んでいただきありがとうございました。

JOI'21 二次予選参加記

はじめに

こんにちは。投稿は2回目、前回の投稿は10ヶ月も前です。 こういう時に更新しておかないといつまでも更新しなさそうなのでとりあえず書いておきます。

記録的な意味合いが強いのでわりと適当です。

結果

問題名 得点 経過時間
A 100 10:06
B 100 01:06:23
C 100 01:50:30
D 100 02:28:25
E 7 02:48:01
合計 407 02:48:01

といった感じでした。

407点は 得点集計表 でも16位(12/13 18:00現在)となっているので多分通るんじゃないかなーと思っています。

行動

競技前後でどのような行動をしていたのかを書いていきたいと思います

開始直前

集中力を上げるためにコーヒーを飲んだ上で手元には炭酸水とチョコを用意して、あと一応ノートを開いておきました。

その上で直前まで漫画を読んだりゲームをしたりして出来るだけ緊張をどこかに飛ばすように行動していました。

(集中力も一緒にどこかに飛んでいったような気がしましたが多分大丈夫でしょう)

競技中

A問題

問題を開くとわりと分かりやすそうな問題が目にはいります。Aを中心に左右に広げていけば解けそうなので実装します。 少しバグらせたこともありましたが難なくACします。

ここまでで10分ほど

B問題(ちょっとC)

問題のBです。

まずは初期状態をstringでmapなどに登録し、stringのまま全部の状態を列挙しようとしてみます。 実装が完了しACを確信しましたが結果はTLE、改善出来る場所が全く分かりません。

わからないので一度Cに目を通し実装しようとしましたがTLEしそうな解法だったので諦めました。ここまでで25分ほど経っていたはずです。

Bに戻ってすぐに3進数で管理することを思いつき、実装を始めます。 しかし慣れない数字の管理に実装を狂わせ、デバッグを重ねてACした時には1時間以上経っていてかなりの焦りを感じていました。

C問題

Cは先程諦めたので一度Dを覗いてみます。 pairで愚直に管理してみる解法を思いつき実装してみますがテストケースの途中で嘘であることに気付き、手が少し止まります。これが1時間と25分ほど。

心を落ち着けるためにコーヒーを飲み(2回目)Cを見てみるとどうやら

dp[今いる町][参加したイベントの数]=そこまでにかかる時間の最小値

のようなDPで解けそうだということに気付き、これなら更新時に二分探索しても O(NlogN) で通せるはずなので実装にかかります。 実装時に不注意によるミスを連発しましたが方針は合っていたようでAC、ここまで1時間50分ほどです。

D問題

4問通せれば通るだろうと考えていたため、一度目を通していたDに1時間残っていることで気持ちに余裕を持つことができました。

制約が正解の決め打ちで二分探索してほしいと言っているので何で判定しようか考えながら二分探索を書き始めます。 判定は後ろから適切に人を割り当てていけばいいことに気付き実装し、かなりすぐにACします。残り約30分です。

E問題

Dが案外すぐに解けてしまったためまた若干自信を失い、ちょっとでも通る確率を上げようとEのbit全探索解を実装し7点を得ます。ここで得点が確定。

この後は少し考えれば嘘であることがわかるような嘘解法を実装して提出しましたが当然WAでした。

競技終了後

全完もそれなりに見掛けましたが同期などのそこそこ強い人も同じ点数だったので若干安心しました。

集計表を眺めて意外な点数分布に驚きつつ、非公式難易度表への投票や感想戦などをしていました。

結局ノートを使うことはありませんでした

感想など

考察を重視して精進をしていましたが、実装でバグらせたり手間取ったりする場面が多かったため、実装力を鍛えることも重要だと再認識しました。 あと実装と見比べるために考察ノートはちゃんと書こうと思いました。

終わりに

やはり文章を書くのが下手です。こんな文章を最後まで読んでいただいてありがとうございました。

気が向いたら解法についても書くかもしれません。

JOI'20本選参加記

はじめに

初投稿ですね。Osmium_1008というものです 予選で5問目をググったら予選通過し(おい)、本選に行ってきたので記録を残します。

1日目

午前

同じく本選に行った同期とJAXAの見学に行った。

秋葉原駅に9時に集合とのことだったのでのんびりと行ったら中央線快速が想定以上に早かったので15分ほど早くついてしまった。 他の同期も早くついたので、予定より早い電車に乗ることができた。

TXには初めて乗ったが、とても早くまた長距離移動にしては料金が安かったので驚いていた。 あと日立初期IGBTっぽかったので何故か興奮してた。

45分ほどで筑波に到着、予定より早くついたのもあって目的地まで色々喋りったり自転車レーンを歩いた同期に対して「やーいお前自転車ー」という謎の煽りをするなどをしながらゆったり歩いていた。 道中看板等を見つけたら写真を取ってツイートしていたが、一人だけ時間をずらしてツイートすることではぐれた人を演じようとしていた。

やはり予定より大分早くついたので、申し込んだツアーでは回らない場所を見ていたりした。人工衛星や探査機などの実物大模型がおいてあったが、想像していたよりも大きく、またソーラーパネルをたたんでいた状態でそれだということに気付き驚いていた。

このあともいろいろなことをしていたが詳しくはdefineの記事に書いてあるので書かないことにする。(丸投げ) JOI2020本選参加記 - #define int long long

午後

食事が終わったら本選の会場に向かった。早くついたかと思ったがhir35さんなどもその頃ついた様だったので安心した。やはりhairaさんは可愛い。

hairaさんが受付に手間取っているのを目撃して可愛いと思いながら待機部屋に向かった。待機部屋ではいろいろな人と現実で交流しようとしたが、結局twitterしかやっていなかった。

practiceでは、Eclipseが最初大量のエラーを吐いていたので使用を諦め、Emacsを使ってある程度問題を解いた。ある程度解いたところでEclipseを動かせるように設定方法を探し、Eclipseを使えるようになったことを確認したので使い始めた。

何故か1問だけバグを取り除けずにいたので交流に行った。美少女という言葉が聞こえた際に何も考えずに割と大きな声で反復してしまい注意されてしまった。このときはあったことある人としか話さなかったと思う。

バグを取り除くためにanmichiを膝の上に乗せながらコーナーケースを一緒に考えてもらった。結論から言うとnとmを間違えて書いていたというものだったので申し訳ない。

practiceが終わると夕食会に入った。偏食の極みみたいなことをしながら割といろいろな人と交流できたと思う。途中あった自己紹介では予選5問目が難易度6であると思っていることなどを話したが、過激と思われたらしい。

夕食会の後にはOSSについての話を聞いた。OSSには興味があったし、OSSの定義や有名企業のOSSへの姿勢など割と面白い話を聞くことができたので良かったと思う。

宿に向かった。ベッドメイキングをした後は周りと少し会話を交わして23時頃には寝た。割と寝心地はよく、よく眠ることができた。

2日目

朝

5時半頃に起床した。いろいろな人が起き始めていたが誰も部屋の外に出ていなかったので結果として一人で部屋の外を歩き回る怪しい人になってしまっていた。

朝食は鮭の切り身や納豆、味噌汁とご飯といった内容だった。普段朝はパンをたべていてしかも少食なので食べきれるか心配だったが食べきることができた。納豆をご飯に乗せて食べる派の人を観測することができた。hairaさんが納豆をご飯と食べようとしてご飯を先に食べきってしまっていた。かわいい。

バスで会場に移動した。起き遅れた人がいたようで発車が遅れた。

会場につくまでに

  • UnionFind
  • dijkstra法
  • 抽象化遅延SegmentTree

の3つを空で実装することができた。

基本緊張しない性格なので驚くほど気楽にいた。

競技

魔剤を持って入っていたが、蓋無し飲料がだめなことを知らずにいたので一気飲みをせざるを得なくなった。来年はボトル缶のものを持っていこうかと思う。

競技が開始したら前日に覚えたEclipseの設定をして問題をとき始めた

1問目

最初にとき始めたが何故かWAが出たので先に2問目を説いてから解いた。

前からと後ろからで累積MAXを取ることはわかり、実装したがWAが出た、コーナーケースを見つけてデバッグをしていたところまた変数名間違いをしていたようだ。変数名を直したところACをすることができた。

2問目

1問目で詰まったので見に来た。かんたんに解けそうであったので実装を始めた。

すべての文字について文字の数の累積和を持っておき、あるところを始点と見たときにJがK個以上現れるのはどこか、そこのあとにOがKこ...とやっていってその範囲の長さの最小を取った。尺取り法で解けたそうだが先に思いついていて実装も軽そうであった二分探索で解いた。難なくACすることができた。1問目よりもかんたんだと思っている。

3問目

2完をしたので部分点を集めに来た。解き切ることも考えたがわかりそうにもなかったので部分点に集中した。区間DPというものを知らなかったので解けなかったのはしょうがないと思っている。

0から始めて、次に左右どちらの台に進むかということを頂点につくたびにすることで、15点を取ることができた。時間を保存するところをlong longにし忘れたことで2回ほどWAを出した。やはり#define int long longは正義だと思う。

4問目

ぱっと読んでわからなく、またいくつかの頂点の向きを変えられると誤読をしてやる気が失せ、飛ばした。問題文をちゃんと読んでいればよかったと思う。

5問目

4よりも取りやすそうであったのでとき始めた。

すべての時間についてを事前に計算して累積和を取り、区間の和を見ることで1点の部分点を獲得できた。この部分点もlong longにし忘れたことで1回ほどWAを出した。この後のいくつかの部分点はSegTreeを書けば取れたが4問目を見たりしていて実装をする時間を取れなかった。

結果

問題番号 点数
1 100
2 100
3 15(小課題1,2)
4 0
5 1(小課題1)
合計 216
判定 Bランク

競技後

解析の時間はほしいデータをすべて保存してできる限り早めに部屋を出た。3完が多そうな雰囲気がしたので部分点の取り忘れで落ちると思った。

会場を出ると昼食だった。cobaltさんなどと会話を交わしながら昼食として出た弁当を食べた。割と美味しかったので店で売る弁当はすべてあの弁当にするべきだと思う。(過激)

昼食後には全部の問題の解説があった。3問目のAC数が23人であったことで全てを察した。かつっぱさんの解説がいろいろなネタを含んでいて面白かった。

何かの行事のPRもあったが、参加対象でなかったためほとんどtwitterをしていた。

帰り

またTXに乗った。同期がみんな優先席に座っていたので驚いていた。(基本は立っていた) スタッフの方々と会って、いろいろな話をしていた。

北千住で降りて千代田線に乗り換えようと思っていたら行きと違ってみんな北千住で降りるようだった。

余力があったのでABCも出た。

感じたこと

落ちた結果が経験不足であり時間不足や解き忘れでなかったので少しホッとしている。 しかし精進をしていないために経験が不足していたのでしっかりと精進をしようという気になった。(気になっただけ)

また交流等も結局あまりできなかったので積極的に交流するようにしたいと思った。

終わりに

読みにくい文章書いてしまってすいません。ここまで読んでいただいてありがとうございました。