20番あたりまでは全体的には易しめ。難易度変動は大きめで、難しいのは難しい(トートロジー)。その後、特に30番あたりからは、私にとってはかなり手強い問題になってきたなと感じました。競技プログラミングや情報科学に特化した勉強をしていなくてもすぐに扱えそうな技術が多い印象がありました。・易しい知識に基づく速解き競争が中心。逆に、高度な専門知識を持っていても報われにくい・問題を解く楽しさはあっても、高度な手法を学ぶ場としてはそれほど適していないという印象も持っています。今回の難易度帯から一気に、データ構造などの知識が問われ始めたように感じます。私としてはそういう分野特化な思考法を吸収できる方が嬉しいので、この難易度帯はこれまでと比べるととても充実していました。難問リスト個人的に数時間単位でかかったものなど。考察が難しかったもの、実装が難しかったものなどごちゃまぜ。一応雑にリストアップしておきます。個人差もあるかと思います。ABCAC個別感想ネタバレ防止も兼ねて、折りたたんでみました。バックトラック等で枝狩りしながら探索していく方法が有名かと思います。通りしかないので、全部試して判定しました。左から順に貪欲に短縮していくのが最善。難しくて時間がかかった。スタートから点Pまでの経路は、その時点での最善を尽くすとは限らない。点Pからゴールまでの経路は、その時点からの最善を尽くすことになる。したがって、各点からゴールまでのコストをデータに持つ。あとはゴールから遡って、幅優先探索で効率の悪い経路を捨てつつ探索すればよい。自分の提出:■ひとつ捨ててもさほど平均値は動かない。2通りやればよいはず。調べてしまうと些細な計算ミスは吸収できる(やった)。各点に到達するまでに必要な破壊回数を求めたい。これは単純なグラフ最短路問題。2回を超えたら打ち切って良いとか、距離が1ずつ増える最短路はデータ追加時のソート(heapq)の類が要らないはずとか、改善できるところは割とあるけれど、あまり気にせず書いてAC。問題文を読んで何となく、その場その場で収められる最小の箱を選ぶのが効率良さそうと思った。証明がパッとはできない。サンプルを手で書きながらやっていくと、「そうでない箱に入れた状態」が完全下位互換になることが分かり証明完了。証明の際にも実装の際にも、初期状態を大きさINFの箱が並んでいると思うと簡潔に考えられた。分かってしまえば難しい問題ではないのだが、かなりの時間悩まされた。司会者からの供給が遅いので、各参加者が律速段階になる心配はしなくてよい。したがって、司会者が投げ始めさえすれば、そこからは各参加者に理論値時間で届くとしてよい。このことに気付くと、ただの最短路問題になった。等を持つarrayを作るにはこのようにします。呼ばれ、その数え上げは漸化式・級数表示ともに有名です。一応高校数学の問題集とかでも見かけうる範囲だったような気がする。小さいので、集めたブロックの種類と最後に積んだ色に対するスコアを持って漸化式。自分の提出:■グラフの最短路の計算・経路復元をする問題。csgraph.dijkstraで最短路を計算し、返り値にpredecessorsを持たせることで、経路復元できる。最後の1枚を除いて、5目並びの判定をすればよい。マス目も小さいので、全探索の下手実装で十分。自分の提出:■Nimのゲームと同値。知っていれば一瞬だし、知らなければ自力で解に至るのはかなり難しいかもしれません。方針が立たないなーと思いつつ、自分だったらどういう戦略をとるだろうと考える。簡単な1手先読みまでで、2手連続消せないことがほぼ起こりえないことが分かる。考えると、常にどの色も1個以下という状態を維持できることが証明できた。何かを1と決めると、順次決まっていく。比率が有理数倍になるので、Fraction型を利用した。意外と利用機会が少ないですよね。添字がごちゃごちゃしててややこしいけれど、状態遷移を考えて漸化式を作るだけ。全部一致する場合を除くと相異なるのでどの行に行くかが決まって、1次元で自由な場所に座る問題に帰着。最初20問の中では一番苦戦した。変な解き方をしてしまったと思ったけれど、解説PDFと同じ方針だった。そもそも結構難しいし、マップに6種類もマス目があるので、実装ミスが起こりやすいところも難易度があると思います。次元が増えると面倒なので、マップは1次元化して実装しました。戦略は簡単で、各時点で安いものを増資する。最終的に増資されず残る金額を二分探索。単なる高校数学の典型数え上げ。個数分布の一致を確認する。やることは簡単で実装に少し悩む。距離の一覧を計算して、Rx>Tyというようなx,yの組を数える。scipyで距離を作ってnp.searchsortedで集計。ついでに少しだけ自明な短縮をした:■。ある蛍光灯を使うとき、そこより左は最善の状態であるべき。これは、蛍光灯を左から順に見ていって、(低コスト・右端座標)という状態を優先度queueで持てばよい。次の蛍光灯に繋げられなくなった状態は捨てる。そこまでの最安値に付け加えて状態に追加。解答にあるseg木やBITは使わず簡潔なコードになったけれど本質的には似たようなものかな。自分の提出:■ただのナップサック問題。根付き木と思って下側の成分の大きさを計算。残り1成分は引けば分かる。小さいコストでグラフを連結にしたい問題。思うと最小全域木っぽい雰囲気。帰着できそうと思ったら上手くいった。強連結成分で縮約みたいなことをするとDAGになって適当にdpという問題。発想は至る所平易だけれど、実装量が多く経験も少なかったところなのでやや苦戦。隣接互換の回数は、初期状態と最終状態の転倒数。操作順は気にせず最小値から決めていけばよい。順にxを見ながら「これまでx以下の元をいくつ数えましたか?」というような集計を扱う必要があり、BITを使用した。BITは「区間上の値を更新し、区間和を求める」手法として知識としてはあったが、区間内の出現件数の更新・集計に用いるというイメージを持っていなかった。この目的の使用はこの後の過去問では頻出で、どうやらBITの典型利用の1つだったようだ。各時刻からいくつの仕事を詰め込めるかを求める。後ろの時刻から戻っていく。自分の提出:■ここでも、「x番目の値を求める」と「BIT上で二分探索する」という目的・手法が結びついていなかったので良い学びだった。N$を2回ではなく1回で済む。各階層で左右どちらに行くか決めればよく、和を求めるのと同時並行みたいな感じに。間の数の素因数分解を求める。自分の提出:■グラフを更新しながら距離行列を更新していく問題。新たな道を通る方法のみ更新していく。pypyでのACは他に居なかったので、少し計算量の厳しいやつかと。numpyは実装も手軽で計算速度も良い。累積和が適当な範囲に収まっているような場合の数え上げ。和そのものを持つとパラメータが多いので、現在地との位置関係で持つ。あとはnumpyでdp。自分の提出:■いかにも二分探索。決め打ったときの集計は、np.searchsortedで簡潔に。自分の提出:■これはかなり難しかった。Grundy数を順に更新していけばよいことはすぐに分かる。これをどのようなデータ構造で実現すればよいのかいいのか悩まされた。seg木で、区間に対してどのようなGrundy数が存在するのかを持たせることが思いつく。これだと結局、存在しない値の最小値を求めるところが上手くいかない。各区間にBITを持たせる。いやそれは大きすぎる、無茶だ。そこで立場を入れ替えてGrundy数に対して何かを持つ形のデータの持ち方を考えていたら、区間をコンプリートするインデックスを持つseg木で要件を満たせることが分かった。seg木やseg木上の二分探索はBIT以上に経験がなく実装も時間がかかる。独学の適当なseg木だと、最下段に奇数番号の1元集合を配置してBITライクな添え字付けをしていたのだが、アリ本を見直すと最下段を連番で持っていて、確かにその方が実装に頭を使わない気がしてきた。seg木が計算用紙なしでも書けるようになった。自分の提出:■1度飛ばせると分かったところはメモして次回も飛ばせるようにする。簡単な発想に感じた、UF木や過去問を学んだおかげもありそう。自分の提出:■030あたりから難易度が高めに感じるものが続いていたので、これはかなり簡単で拍子抜け。右移動・左移動を一塊として、1カ所に集合するグループに分けられる。グループ内では集合場所を左右に動かすと総コストが単調に増減。境界の場所の持ち方とか(結局タプルにした)、左端・右端の処理とか、地味なところの実装に少し気を遣う問題。自分の提出:■dpする順番をうまくやることで、適切な範囲のアイテムだけで計算した状態を順次追える。転倒数は数度過去問で扱われていたので方針はすぐに立つ。半分遡るところも、転倒数の計算を半分になるまでやる感じで。軸ごとに分けるのは基本。同時刻に来るビームはまとめる。あとは関係のある座標のところだけ書き換えていく感じでdpする。dpが何を表しているのか(時刻$t$の移動の前の座標なのか、後の座標なのか等)をぼんやりしたまま実装したせいで詰めにやや苦労。自分の提出:■LCAまでの距離が相殺するので、根からの距離だけ持てばよい。ことに気づけば単にdfsで距離集合を求めて集計すればよい。自分の提出:■とても難しかった。それっぽい貪欲ライクな手法がいろいろと考えられる。条件が多いので、アルゴリズムの正しさの証明も地味に混乱しやすい。アルゴリズムが分かったあとの実装も、座圧してBITに入れて二分探索となかなかややこしい。・弱い男から順にペアを作っていく。・各時点で、女→男が条件を満たすように、見る女の範囲を広げていく。・いま見ている男から選べる女がいるならば、そのうちで最弱の女を選ぶ。・いま見ている男が「選ばない」利点はない。・「より強い女を選ぶ」利点もない。今後の展開において、女からの要求レベルは完全に無視できるため。自分の提出:■その時点で下から何番目の数を使うべきかが簡単に計算できる。そこから先はいつものBIT。自分の提出:■はじめは最長の区間に注目した(ここを決まれば一意に決まるので)。気分を入れ替えて最小の区間に注目してあげると条件を整理しやすかった。自分の提出:■いかにも混乱しやすい条件だ。見るとBが非常に小さいので、タイプ2の制約の対処法を固定して解く発想にはなる。すると操作の順番は非本質的になって、貪欲に塗るゲームに帰着された。易しいが、割り算をするときにmodが分からなくなっちゃうところだけ少し工夫が要る。自分の提出:■いかにも二分探索っぽい雰囲気。はじめはlogをとってどれに何回かけるのかを評価しようと思ったが、ちょうど一致する場合などの計算誤差が面倒くさそう。epsilonでごにょごにょやっても良いが...。掛け算が定数倍なので、一回追いつくと周期的になるやつだった。指数はすぐ大きくなってくれるので、実際に追いつくまでやればよい。自分の提出:■1回で済ませたいところだが、よく分からず2回bfsする形に(でも想定解法と同じっぽかった)。定数倍の節約をさぼったためか、PythonではTLEしてPyPyで提出した(AC者は居るので私が下手だっただけ)。自然なリスクの少なさそうな順番に並べればよい。自分の提出:■かなり悩んだ。私は、漸化式の遷移を考えているときに、行列式に似てるなーってなった。1本とって見ると、余因子行列が残ります。解説の考え方も確かに。AとCに注目して集計すればよさそうなことはすぐに分かる。文字列の共通prefixの長さは...アリ本をあたった。文字列周りのアルゴリズムは難しいなあ。hashによる方法を用いた。解説で挙がっているキーワードは未履修。私的なタスクリストに積んでおく。自分の提出:■だいたいそれっぽく探索するだけ。部門間の信頼度を引くよりも、部門内の信頼度を加算する方が、集合の分割に対して加法的にふるまって扱いやすいと思う。元部分集合に対して、自身の部分集合を眺める)。自分の提出:■Pythonは多倍長整数の演算が標準であるので、こういうのはすぐですね。感想ARCコンテストの過去問(A・B)を埋めました。以降のA・B問題は、ABCコンテストのC・D問題と共通になっています。問題名で検索すると、他の方の解説をたくさん書いてくださっています。共通として二分探索による解法が多くとりあげられていました。JSC2019予選問題F)において、類題として並べた問題の1つを解説していきます。10000$の2次元配列全体に、何らかの処理をするとします。2重forループが思い浮かぶところですが、pythonのforループが激遅いというのは有名です。本質的には、解説PDFと同一の解法でしたが、考察の手順は割と違っていた気がします。人によっては、着想が分かりやすくなると思うので、記しておきます。形式的べき級数解説pythonその他タイトルとURLをコピーしました。