はじめに
はい、皆さんこんにちは。久しぶりに記事を出しましたが...。
2024/12/08 13:00～16:00にありましたよね、二次予選。
投稿すんの今更過ぎるだろ。
正直怖かったです。
いやー、おなじ学生なのかと疑ってしまいます。中2にとっては異次元な存在に見えます。
そして、今回あったことに対して、いろいろ話していこうと思います。
やる前に
私の精進法
私はAtCoder ABC-ARC (Normal or Div.2) の過去問かJOI二次予選の過去問を読むか、
本を読むか(代表的なものは競技プログラミングの鉄則などがあります)
など、様々な精進方法がありましたが、
私は主に本を読むことと過去問をやる精進法を選びました。
具体的には、
- 本を読んで知識を身に着ける
- そのあとにJOIをやる
ということをしました。よーするに基礎知識を身につけてやる、っていうことです。
しかし私はこれを良くなかったと思っています。もちろん人によることを
大前提としますが、ちょっと効率的ではなかったと思います。
Why wasn't it good? 1
まず、JOIの過去問は年に一回であるがゆえに過去問が少ないです。
なんならJOI2019/2020と2020/2021の間でかなりシステムが変わっているので、
JOI2019/2020以下の問題はもはや使えない代物となっています。
↑JOI用の練習をするという意味では。
そうすると、強制的に少ない問題で精進する羽目になります。
Why wasn't it good? 2
次に、本での勉強法が悪かった原因についてですが、AtCoderとJOIの問題の性質の違い
これがかなり原因となっている気がします。
まず、AtCoderはゴリゴリに数学系の問題を出してきます。
https://atcoder.jp/contests/abc383/tasks/abc383_d
はい、かなり数学ですね。数学のテストに出せよ。
一方、JOIの問題はこんな感じです。
これもバチクソ数学系に見えますが、じつは簡単に言うとこうなります。
棚に商品が並んでいて、当然のようにそれぞれの商品に値段がついています。
なんか特定の日に行くと特定のものが半額になるから、こっからここまで
買った客は何円払ったか求めやがれ
こんな風に、日常生活に凄く関係ありそうな問題が沢山出ます。
まあこれは結構言われてきたことだと思いますが...
そしてAtCoderとの違いが、小課題が設定されていることです。
これはどういうことかというと、クソデカイ制約にもうちょっと制限を付けた、
簡単にした問題が、出されます。例えばこの問題は、
$N,M,Q\le 2000$という制約が追加でつけられています。この制約の上といたら、
なんか15点がもらえますよ、っていうことです。
ようするに最初っから満点を取らなくてもいい加減なやつでも点とれる
ことを意味しています。すごいですね。
初期のころのABCにはあったとかなかったとか(私は知りません)
A問題
ついにやってまいりました。どう解いたかについて考えます。
問題文
高さ$H,W$のマスが与えられていて、最初は0という文字が書かれてるよ。
俺らはなんか2つの操作ができるみたいで、一つ目は2x2の範囲を特定の色に塗り替えて、
二つ目はマスキングテープを2x2の範囲ではるってことをするみたい。
ちなマスキングテープ張られたら塗り替えられないよ。
あれですね。なんか懐かしいというか...Youtube Shortで流れてくる奴ですね。
最初シール張ってスプレーかけてはがしてもう一枚張ってスプレーかけてってやつか...
まああれの低レベル(!?)版です。
これは計算量があーだこーだってわけじゃなかった(愚直)ので
速攻100点AC取れました。
ここは比較的簡単じゃないかなーと。
B問題
問題文
なんかボールを穴に入れるよくわからんスポーツをしてるよ。盤面には$N$この
ボールがあって、このボールを集中して穴に入れなきゃいけないらしいよ。
最初集中力は$X$で、$i$番目のボールは$A_i$の集中力を犠牲にするかわり
ボールを入れられるよ。ちなみにボールを落とす前にあるボールを落とさないと
いけないやつとそうじゃないやつがあるよ、$X$の集中力を使って落とせるボールの
番号の最大値を求めてね。
何がしたいんですか?日常ってよりかは異国の競技な気がします。
ここで小課題1を取るのに大苦戦。 45分位のタイムロスをしてしまいます。
こんなことしてなければ、もっと点を取れた気がします。
そんなこんなでiPadのフリーボードにグラフを書いていると、ひらめきました。
ボールの関係をグラフにすればいいんじゃね?
これはどういうことかというと、まずはボールを落とすという行為を日常の
ルーティーンに例えてみましょう。
例えばボール1を落とすことを「起きる」、2を落とすことを「ご飯を食べる」
3を落とすことを「着替える」...みたいな感じにしてみます。
次に日常のルーティーンには必ず順序が存在します。
絶対起きる前にご飯は食べないですよね。食べられたらおかしいですよね。
ということで、それぞれの日常の関係を「頂点」と「辺」というものでつなぎます。
いわゆるグラフ理論です。こんな感じで、最終的にボール$x$を落とすのにどれだけ
いけるかっていうのを行ける限りDFSしていきました。
しかしここで私はこう書いていました。
void dfs(Graph G ... ) {}
これ、Gがそのままわたるせいで時間をめっちゃ食うんですよ。ヤバくないですか。
Gの大きさは普通に$O(N+M)$を超えてくるため、これを再帰しようとするんなら...
想像したくないです。
しかしこれをグローバル変数へ持っていくことで、解決できました。
Graph G;
void dfs( ... ) {}
あと普通に参照渡しする方が良かった説。
これで200点なんですがこの時残り時間はあと5分程度。
C問題
あーあ、もうだめですわ。
と思いながら、とっさに小課題1の全探索を書いて7点。
合計
207点でした。前は50点とかいう悲惨な点数とってたので、全然いい成果が出ていると思います。
奇跡を信じていましたが、あいにくボーダーは270点越え。
絶望を感じましたね、あれCまで解かないといけないのか...
まとめ
ヤバいです。ただJOIの問題もAtCoder側をもう少し強化すれば解けるんじゃないかと
思いました。やはり安定で解くためにはABCを満点解いた方がいいですね。
あと、Dの小課題30点取ってれば安心かもしれません。ただインフレして
370点ボーダーとかになったらシャレにならないんですが...
自分から見て「難しい」ことは周りから見て「簡単」くらいに思っておかないと
厳しい世界だとわかりました。
来年で中学三年生です。うまく行くでしょうか。それまでに絶対緑コーダーになって
二次予選を突破します。
呼んでいただきありがとうございました