[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 暗闇帰り道

004 平均値太郎の憂鬱

問題文：■　自分の提出：■
ひとつ捨ててもさほど平均値は動かない。したがって

N

はだいたい

2 X / Y

周辺。2通りやればよいはず。
細かい不等号の議論に自信がなければ、

2 X / Y \pm 10

くらい調べてしまうと些細な計算ミスは吸収できる（やった）。

005 器物損壊！高橋君

006 積み重ね

007 節約生活

問題文：■　自分の提出：■

N ≦ 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 ダブレット

012 五目並べチェッカー

013 笑いをとれるかな？

014 魂の還る場所

015 変わった単位

016 ソーシャルゲーム

017 無駄なものが嫌いな人

018 席替え

019 最後の森

020 A mod B Problem

021 増築王高橋君

022 ロミオとジュリエット

023 タコヤ木

問題文：■　自分の提出：■
単なる高校数学の典型数え上げ。二項係数を階乗で求めるとTLEだが、

k

が小さい

_{n} C_{k}

しか出てこず、

O (k)

で求めれば十分。

024 だれじゃ

025 ウサギとカメ

026 蛍光灯

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

028 高橋王国の分割統治

029 高橋君と国家

030 有向グラフ

031 積み木

032 仕事計画

033 データ構造

問題文：■　自分の提出：■
ここでも、「x番目の値を求める」と「BIT上で二分探索する」という目的・手法が結びついていなかったので良い学びだった。
BIT上の探索は、少し考えれば

\log N

を2回ではなく1回で済む。各階層で左右どちらに行くか決めればよく、和を求めるのと同時並行みたいな感じに。

034 約数かつ倍数

問題文：■　自分の提出：■
素数表を作り、

A

と

B

の間の数の素因数分解を求める。

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

036 偶然ジェネレータ

037 億マス計算

038 茶碗と豆

問題文：■　自分の提出：■
これはかなり難しかった。Grundy数を順に更新していけばよいことはすぐに分かる。これをどのようなデータ構造で実現すればよいのかいいのか悩まされた。
例えば、seg木で、区間に対してどのようなGrundy数が存在するのかを持たせることが思いつく。各区間に対してsetを持たせても、大きさの合計は

O (N \log N)

で済む。
でもこれだと結局、存在しない値の最小値を求めるところが上手くいかない。各区間にBITを持たせる。いやそれは大きすぎる、無茶だ。
そこで立場を入れ替えてGrundy数に対して何かを持つ形のデータの持ち方を考えていたら、区間をコンプリートするインデックスを持つseg木で要件を満たせることが分かった。

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

039 幼稚園児高橋君

040 Z塗り

041 ウサギ跳び

042 おやつ

043 転倒距離

044 ビーム

問題文：■　自分の提出：■
軸ごとに分けるのは基本。同時刻に来るビームはまとめる。あとは関係のある座標のところだけ書き換えていく感じでdpする。
dpが何を表しているのか（時刻

t

の移動の前の座標なのか、後の座標なのか等）をぼんやりしたまま実装したせいで詰めにやや苦労。定義は明確に。

045 エックスオア多橋君

046 合コン大作戦

047 N!÷K番目の単語

048 足の多い高橋君

049 ぬりまーす

050 LCM 111

051 掛け算

052 高橋くんと不思議な道

053 魔法使い高橋君

054 鯛焼き

055 ABCAC

056 部門分け

問題文：■　自分の提出：■
だいたいそれっぽく探索するだけ。部門間の信頼度を引くよりも、部門内の信頼度を加算する方が、集合の分割に対して加法的にふるまって扱いやすいと思う。
計算量が

O (3^{n})

になることは、私は二項定理

\sum_{k = 0}^{n} (\binom{n}{k}) 2^{k} = 3^{n}

から確かめました（各

k

元部分集合に対して、自身の部分集合を眺める）。PyPy使用。

057 2乗根