[AtCoder] ARCコンテスト過去問（～057・C難易度）感想

ABCコンテスト過去問感想 → ■
ARCコンテスト過去問（～057, A・B難易度）感想 → ■
ARCコンテスト過去問（058～, C難易度） → 近日

全体感想
難問リスト
個別感想

全体感想

20番あたりまでは全体的には易しめ。難易度変動は大きめで、難しいのは難しい（トートロジー）。その後、特に30番あたりからは、私にとってはかなり手強い問題になってきたなと感じました。

ABCコンテスト等だと、ソート・累積和・dfs・bfs・二分探索・漸化式など、競技プログラミングや情報科学に特化した勉強をしていなくてもすぐに扱えそうな技術が多い印象がありました。
敢えて悪く言えば、
・易しい知識に基づく速解き競争が中心。逆に、高度な専門知識を持っていても報われにくい
・問題を解く楽しさはあっても、高度な手法を学ぶ場としてはそれほど適していない
という印象も持っています。

今回の難易度帯から一気に、データ構造などの知識が問われ始めたように感じます。私としてはそういう分野特化な思考法を吸収できる方が嬉しいので、この難易度帯はこれまでと比べるととても充実していました。

難問リスト

個人的に数時間単位でかかったものなど。考察が難しかったもの、実装が難しかったものなどごちゃまぜ。一応雑にリストアップしておきます。個人差もあるかと思います。
・ARC019 最後の森
・ARC030 有向グラフ
・ARC038 茶碗と豆
・ARC046 合コン大作戦
・ARC052 高橋くんと不思議な道
・ARC054 鯛焼き
・ARC055 ABCAC

個別感想

ネタバレ防止も兼ねて、折りたたんでみました。

001 パズルの手伝い

問題文：■　自分の提出：■
8-queens puzzle は、バックトラック等で枝狩りしながら探索していく方法が有名かと思います。
本問題では、探索空間がそもそも $5! = 120$ 通りしかないので、全部試して判定しました。

002 コマンド入力

問題文：■　自分の提出：■
ボタンの割り当てを全部試す → 左から順に貪欲に短縮していくのが最善。

003 暗闇帰り道

問題文：■　自分の提出：■
難しくて時間がかかった。
スタートから点Pまでの経路は、その時点での最善を尽くすとは限らない。一方、点Pからゴールまでの経路は、その時点からの最善を尽くすことになる。
したがって、各点からゴールまでのコストをデータに持つ。あとはゴールから遡って、幅優先探索で効率の悪い経路を捨てつつ探索すればよい。

004 平均値太郎の憂鬱

問題文：■　自分の提出：■
ひとつ捨ててもさほど平均値は動かない。したがって $N$ はだいたい $2X/Y$ 周辺。2通りやればよいはず。
細かい不等号の議論に自信がなければ、$2X/Y \pm 10$ くらい調べてしまうと些細な計算ミスは吸収できる（やった）。

005 器物損壊！高橋君

問題文：■　自分の提出：■
各点に到達するまでに必要な破壊回数を求めたい。これは単純なグラフ最短路問題。
2回を超えたら打ち切って良いとか、距離が1ずつ増える最短路はデータ追加時のソート（heapq）の類が要らないはずとか、改善できるところは割とあるけれど、あまり気にせず書いてAC。

006 積み重ね

問題文：■　自分の提出：■
問題文を読んで何となく、その場その場で収められる最小の箱を選ぶのが効率良さそうと思った。証明がパッとはできない。サンプルを手で書きながらやっていくと、「そうでない箱に入れた状態」が完全下位互換になることが分かり証明完了。証明の際にも実装の際にも、初期状態を大きさINFの箱が並んでいると思うと簡潔に考えられた。

007 節約生活

問題文：■　自分の提出：■
$N \leq 10$ なので、開始時刻の選び方の組み合わせを全部試しても、$2^{10}$ 通り程度。ちゃんと全探索しましょう問題？

008 THE☆たこ焼き祭り2012

問題文：■　自分の提出：■
分かってしまえば難しい問題ではないのだが、かなりの時間悩まされた。
司会者からの供給が遅いので、各参加者が律速段階になる心配はしなくてよい。
したがって、司会者が投げ始めさえすれば、そこからは各参加者に理論値時間で届くとしてよい。
このことに気付くと、ただの最短路問題になった。

dx = X[:,None] - X[None,:]
dy = Y[:,None] - Y[None,:]
graph = np.sqrt(dx * dx + dy * dy)
graph /= np.minimum(T[:,None], R[None,:])

$(i,j)$ 成分に$X[i] – X[j]$, $\min\{T[i],R[j]\}$ 等を持つarrayを作るにはこのようにします。X[:,np.newaxis] と書いても等価です（np.newaxis is None）。

009 高橋君、24歳

問題文：■　自分の提出：■
固定点を持たない順列は、攪乱順列・完全順列などと呼ばれ、その数え上げは漸化式・級数表示ともに有名です。
一応高校数学の問題集とかでも見かけうる範囲だったような気がする。

010 積み上げパズル

問題文：■　自分の提出：■
$m$ が小さいので、集めたブロックの種類と最後に積んだ色に対するスコアを持って漸化式。

011 ダブレット

問題文：■　自分の提出：■
グラフの最短路の計算・経路復元をする問題。
csgraph.dijkstraで最短路を計算し、返り値にpredecessorsを持たせることで、経路復元できる。

012 五目並べチェッカー

問題文：■　自分の提出：■
最後の1枚を除いて、5目並びの判定をすればよい。マス目も小さいので、全探索の下手実装で十分。

013 笑いをとれるかな？

問題文：■　自分の提出：■
Nimのゲームと同値。知っていれば一瞬だし、知らなければ自力で解に至るのはかなり難しいかもしれません。

014 魂の還る場所

問題文：■　自分の提出：■
全然方針が立たないなーと思いつつ、自分だったらどういう戦略をとるだろうと考える。簡単な1手先読みまでで、2手連続消せないことがほぼ起こりえないことが分かる。もうちょっと考えると、常にどの色も1個以下という状態を維持できることが証明できた。ちょっとくだらない^^;

015 変わった単位

問題文：■　自分の提出：■
何かを1と決めると、順次決まっていく。比率が有理数倍になるので、Fraction型を利用した。意外と利用機会が少ないですよね。

016 ソーシャルゲーム

問題文：■　自分の提出：■
添字がごちゃごちゃしててややこしいけれど、状態遷移を考えて漸化式を作るだけ。

017 無駄なものが嫌いな人

問題文：■　自分の提出：■
ABCコンテストから埋めたので、ほとんど ABC-032D で経験済。

018 席替え

問題文：■　自分の提出：■
全部一致する場合を除くと相異なるのでどの行に行くかが決まって、1次元で自由な場所に座る問題に帰着。

019 最後の森

問題文：■　自分の提出：■
最初20問の中では一番苦戦した。かなり変な解き方をしてしまったと思ったけれど、解説PDFと同じ方針だった。そもそも結構難しいし、マップに6種類もマス目があるので、実装ミスが起こりやすいところも難易度があると思います。
次元が増えると面倒なので、マップは1次元化して実装しました。

020 A mod B Problem

問題文：■　自分の提出：■
ABC 129-F と大体同じ題意。

021 増築王高橋君

問題文：■　自分の提出：■
戦略は簡単で、各時点で安いものを増資する。最終的に増資されず残る金額を二分探索。

022 ロミオとジュリエット

問題文：■　自分の提出：■
ABC 019-D と同じ。

023 タコヤ木

問題文：■　自分の提出：■
単なる高校数学の典型数え上げ。二項係数を階乗で求めるとTLEだが、$k$ が小さい ${}_n{\mathrm{C}}_k$ しか出てこず、$O(k)$ で求めれば十分。

024 だれじゃ

問題文：■　自分の提出：■
個数分布の一致を確認する。やることは簡単で実装に少し悩む。26個組のtupleがだるいので、適当にhash化すればよかったかな？

025 ウサギとカメ

問題文：■　自分の提出：■
距離の一覧を計算して、Rx>Tyというようなx,yの組を数える。scipyで距離を作ってnp.searchsortedで集計。コメントも結構はいった状態だけど、shortest codeをもらった。

ついでに少しだけ自明な短縮をした：■。

026 蛍光灯

問題文：■　自分の提出：■
左端から。ある蛍光灯を使うとき、そこより左は最善の状態であるべき。これは、蛍光灯を左から順に見ていって、（低コスト・右端座標）という状態を優先度queueで持てばよい。次の蛍光灯に繋げられなくなった状態は捨てる。そこまでの最安値に付け加えて状態に追加。
解答にあるseg木やBITは使わず簡潔なコードになったけれど本質的には似たようなものかな。

027 最高のトッピングにしような

問題文：■　自分の提出：■
ただのナップサック問題。numpyで簡潔に。

028 高橋王国の分割統治

問題文：■　自分の提出：■
根付き木と思って下側の成分の大きさを計算。残り1成分は引けば分かる。

029 高橋君と国家

問題文：■　自分の提出：■
小さいコストでグラフを連結にしたい問題。と思うと最小全域木っぽい雰囲気。帰着できそうと思ったら上手くいった。scipy.sparse.csgraph.minimum_spanning_tree を利用。

030 有向グラフ

問題文：■　自分の提出：■
強連結成分で縮約みたいなことをするとDAGになって適当にdpという問題。
発想は至る所平易だけれど、実装量が多く経験も少なかったところなのでやや苦戦。

031 積み木

問題文：■　自分の提出：■
隣接互換の回数は、初期状態と最終状態の転倒数。なので操作順は気にせず最小値から決めていけばよい。
順にxを見ながら「これまでx以下の元をいくつ数えましたか？」というような集計を扱う必要があり、BITを使用した。
BITは「区間上の値を更新し、区間和を求める」手法として知識としてはあったが、区間内の出現件数の更新・集計に用いるというイメージを持っていなかった。
この目的の使用はこの後の過去問では頻出で、どうやらBITの典型利用の1つだったようだ。

032 仕事計画

問題文：■　自分の提出：■
各時刻からいくつの仕事を詰め込めるかを求める。後ろの時刻から戻っていく。

033 データ構造

問題文：■　自分の提出：■
ここでも、「x番目の値を求める」と「BIT上で二分探索する」という目的・手法が結びついていなかったので良い学びだった。
BIT上の探索は、少し考えれば$\log N$を2回ではなく1回で済む。各階層で左右どちらに行くか決めればよく、和を求めるのと同時並行みたいな感じに。

034 約数かつ倍数

問題文：■　自分の提出：■
素数表を作り、$A$ と $B$ の間の数の素因数分解を求める。

035 アットコーダー王国の交通事情

問題文：■　自分の提出：■
グラフを更新しながら距離行列を更新していく問題。新たな道を通る方法のみ更新していく。
簡単な割にpython, pypyでのACは他に居なかったので、少し計算量の厳しいやつかと。numpyは実装も手軽で計算速度も良い。

036 偶然ジェネレータ

問題文：■　自分の提出：■
累積和が適当な範囲に収まっているような場合の数え上げ。和そのものを持つとパラメータが多いので、現在地との位置関係で持つ。あとはnumpyでdp。

037 億マス計算

問題文：■　自分の提出：■
いかにも二分探索。決め打ったときの集計は、np.searchsortedで簡潔に。

038 茶碗と豆

問題文：■　自分の提出：■
これはかなり難しかった。Grundy数を順に更新していけばよいことはすぐに分かる。これをどのようなデータ構造で実現すればよいのかいいのか悩まされた。
例えば、seg木で、区間に対してどのようなGrundy数が存在するのかを持たせることが思いつく。各区間に対してsetを持たせても、大きさの合計は $O(N\log N)$ で済む。
でもこれだと結局、存在しない値の最小値を求めるところが上手くいかない。各区間にBITを持たせる。いやそれは大きすぎる、無茶だ。
そこで立場を入れ替えてGrundy数に対して何かを持つ形のデータの持ち方を考えていたら、区間をコンプリートするインデックスを持つseg木で要件を満たせることが分かった。

seg木やseg木上の二分探索はBIT以上に経験がなく実装も時間がかかる。独学の適当なseg木だと、最下段に奇数番号の1元集合を配置してBITライクな添え字付けをしていたのだが、
アリ本を見直すと最下段を連番で持っていて、確かにその方が実装に頭を使わない気がしてきた。seg木が計算用紙なしでも書けるようになった。

039 幼稚園児高橋君

問題文：■　自分の提出：■
1度飛ばせると分かったところはメモして次回も飛ばせるようにする。簡単な発想に感じた、UF木や過去問を学んだおかげもありそう。

040 Z塗り

問題文：■　自分の提出：■
030あたりから難易度が高めに感じるものが続いていたので、これはかなり簡単で拍子抜け。

041 ウサギ跳び

問題文：■　自分の提出：■
右移動・左移動を一塊として、1カ所に集合するグループに分けられる。グループ内では集合場所を左右に動かすと総コストが単調に増減。
境界の場所の持ち方とか（結局タプルにした）、左端・右端の処理とか、地味なところの実装に少し気を遣う問題。

042 おやつ

問題文：■　自分の提出：■
dpする順番をうまくやることで、適切な範囲のアイテムだけで計算した状態を順次追える。

043 転倒距離

問題文：■　自分の提出：■
転倒数は数度過去問で扱われていたので方針はすぐに立つ。半分遡るところも、転倒数の計算を半分になるまでやる感じで。

044 ビーム

問題文：■　自分の提出：■
軸ごとに分けるのは基本。同時刻に来るビームはまとめる。あとは関係のある座標のところだけ書き換えていく感じでdpする。
dpが何を表しているのか（時刻$t$の移動の前の座標なのか、後の座標なのか等）をぼんやりしたまま実装したせいで詰めにやや苦労。定義は明確に。

045 エックスオア多橋君

問題文：■　自分の提出：■
LCAまでの距離が相殺するので、根からの距離だけ持てばよい。ことに気づけば単にdfsで距離集合を求めて集計すればよい。

046 合コン大作戦

問題文：■　自分の提出：■
とても難しかった。それっぽい貪欲ライクな手法がいろいろと考えられる。条件が多いので、アルゴリズムの正しさの証明も地味に混乱しやすい。
アルゴリズムが分かったあとの実装も、座圧してBITに入れて二分探索となかなかややこしい。
・弱い男から順にペアを作っていく。
・各時点で、女→男が条件を満たすように、見る女の範囲を広げていく。
・いま見ている男から選べる女がいるならば、そのうちで最弱の女を選ぶ。
・いま見ている男が「選ばない」利点はない。
・「より強い女を選ぶ」利点もない。今後の展開において、女からの要求レベルは完全に無視できるため。

047 N!÷K番目の単語

問題文：■　自分の提出：■
その時点で下から何番目の数を使うべきかが簡単に計算できる。そこから先はいつものBIT。

048 足の多い高橋君

問題文：■　自分の提出：■
はじめは最長の区間に注目した（ここを決まれば一意に決まるので）。しかし結局議論しなければいけないところが最小の長さより上に寄っていて、
気分を入れ替えて最小の区間に注目してあげると条件を整理しやすかった。

049 ぬりまーす

問題文：■　自分の提出：■
いかにも混乱しやすい条件だ。よく見るとBが非常に小さいので、タイプ2の制約の対処法を固定して解く発想にはなる。
そうすると操作の順番は非本質的になって、貪欲に塗るゲームに帰着された。

050 LCM 111

問題文：■　自分の提出：■
易しいが、割り算をするときにmodが分からなくなっちゃうところだけ少し工夫が要る。ABC 129-F の類題。

051 掛け算

問題文：■　自分の提出：■
いかにも二分探索っぽい雰囲気。はじめはlogをとってどれに何回かけるのかを評価しようと思ったが、ちょうど一致する場合などの計算誤差が面倒くさそう。
epsilonでごにょごにょやっても良いが…。しかし掛け算が定数倍なので、一回追いつくと周期的になるやつだった。指数はすぐ大きくなってくれるので、実際に追いつくまでやればよい。

052 高橋くんと不思議な道

問題文：■　自分の提出：■
1回で済ませたいところだが、よく分からず2回bfsする形に（でも想定解法と同じっぽかった）。
定数倍の節約をさぼったためか、PythonではTLEしてPyPyで提出した（AC者は居るので私が下手だっただけ）。

053 魔法使い高橋君

問題文：■　自分の提出：■
自然なリスクの少なさそうな順番に並べればよい。証明も易しい。

054 鯛焼き

問題文：■　自分の提出：■
かなり悩んだ。相当難しいと思う。私は、漸化式の遷移を考えているときに、行列式に似てるなーってなった。1本とって見ると、余因子行列が残ります。解説の考え方も確かに。

055 ABCAC

問題文：■　自分の提出：■
難しめ。AとCに注目して集計すればよさそうなことはすぐに分かる。文字列の共通prefixの長さは…アリ本をあたった。
文字列周りのアルゴリズムは難しいなあ。ひとまず、一番手軽に思えたrolling hashによる方法を用いた。解説で挙がっているキーワードは未履修。私的なタスクリストに積んでおく。

056 部門分け

問題文：■　自分の提出：■
だいたいそれっぽく探索するだけ。部門間の信頼度を引くよりも、部門内の信頼度を加算する方が、集合の分割に対して加法的にふるまって扱いやすいと思う。
計算量が $O(3^n)$ になることは、私は二項定理 $\sum_{k=0}^n\binom{n}{k}2^k=3^n$ から確かめました（各 $k$ 元部分集合に対して、自身の部分集合を眺める）。PyPy使用。

057 2乗根

問題文：■　自分の提出：■
Pythonは多倍長整数の演算が標準であるので、こういうのはすぐですね。