tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Div1Hard300問チャレンジ 感想と問題の紹介

この記事はCompetitive Programming Advent Calendar 2014 - PARTAKEの5日目の記事です。無事間に合いました。同時にブログに記事を書きます Advent Calendar 2014 - Adventarの5日目でもあります。


一時期話題になった「Div1Hard300問埋め」についていろいろと書き残しておこうと思います。参加記風のことと、オススメ問題について記しておこうということです。

経緯

7/11 ICPC国内予選落ちる。
http://twitter.com/1_000_000_007/status/487563617986805761
http://twitter.com/1_000_000_007/status/487578509775101952

7/12 すべてはここから始まった(実は11日から解き始めています)
https://twitter.com/1_000_000_007/status/487625669484883968

7/15 Google Calendarに毎日解いた問題数を記録するようにしはじめる(この時点で37問)

7月のAC状況
http://gyazo.com/66c0c84f5f9d8c2a295c7df036e11b2c

8月になる。基本的に家にいる日は一日5問を目指す。
時々北海道に行ったり高校の部活の合宿に行ったりしたときは解いていませんが、他の日は毎日休まずやりました。

8月のAC状況
http://gyazo.com/e752c078188a25098219cc9d114d2789
(このくらいのころにただ数だけ解いていたということを指摘されたので、時間に余裕もあるし考える難しい問題も手をつけるようになる。)

9月はもう完全にAC数的には余裕になってきた。24日を最後にAC数も記録していない。
9月のAC状況
http://gyazo.com/031deab1589f03d24100ff4b232e3831

10/1 300問目は456Hard FunctionalEquationでした。
http://twitter.com/1_000_000_007/status/517203880619163649
http://twitter.com/1_000_000_007/status/517204007039672320
http://gyazo.com/cb812a6a362fd4a13ea7aa6963650a08

その後。
http://gyazo.com/3b3edcb172b1ccf2d4ff950bb3a4ea95

感想

  • やっぱり1ヶ月150問(1日5問)というのは目標としてちょうどよい。
  • それにしても、TopCoderとAOJだけで5ヶ月弱で650問解くってどれだけ暇なんですかね……。
  • すでにレッドコーダーの自分が始めても後になったら実力が上がった感じがするので、数こなすのはどれだけやっても有用なんじゃないだろうか。
  • CFまで埋める気はしない。

本編(おすすめ問題の紹介)

おことわり:英語も日本語も苦手なので問題の概要を日本語で書くような親切なことはできません。
オススメ度が高い順に並べられるほど問題は少なくないので、オススメ問題と思えそうな問題を思い出し次第書いていくスタイルにします。
コメントは白文字で書くので見たい人はドラッグして反転させてください。
難易度を1~10で表します。
1(Mediumで出ても普通) ⇔ 5(普通のHard) ⇔ 10(出すコンテストを間違えてる)

SRM535 FoxAndGreed (難易度: 2)
よくある数え上げ。良問というか自分が好きなだけ。本来はもっと制約が厳しいバージョンだったらしく、そのためにmodが小さいらしい。

SRM175 BinaryQuipu (難易度: 3)
問題文がメチャクチャ長い。つらいけど僕もつらかったので読んでください。
解法:実はこの答えを良く考えてみると、メモ化再帰をしたときのメモの個数と非常に関連性が高いことが分かる。それを使って上手くメモ化再帰一発で答えが求められる。

SRM563 CoinsGame (難易度: 3)
http://tozangezan.hatenablog.com/entry/2014/08/09/163444

SRM309 StoneGameStrategist (難易度: 3)
ゲームの必勝法を考える。本当にゲームの必勝法を考えるだけ。でもそれを考えるのが結構面白い問題だった。

SRM589 FlippingBitsDiv1 (難易度: 4)
http://tozangezan.hatenablog.com/entry/2014/07/15/005132

SRM614 TorusSailing (難易度: 4)
期待値を求めるための連立方程式の立て方。次元を落とすという発想から結構素直に解ける。

SRM616 ThreeLLogo (難易度: 6)
40*40の盤面にLを3つ盤面に置く。
解法:一見包除とかで気合系なのかなあ、とも思うけど実は(今みてる行,残っている縦棒の位置)みたいなDPを上からしていくだけで解ける。「3」だからこれでも十分間に合う、ということがなかなか気がつきにくい。分かれば複雑な要素がない。

SRM625 Seatfriends (難易度: 6)
AppleTreesの類題。この特殊なDPと同じようなDPをするのと、もう一つもっと簡単なDPをして二つの組み合わせで答えが求まる。

MSRM478 RandomApple (難易度: 6)
どの箱を使うかをランダムに選んで混ぜたときのそれぞれ色のりんごを引く確率を求める。
それぞれの箱に対する重み付けみたいなのをするけれど、そのやりかたがなんとも面白い感じ。
数え上げたDPの配列を戻して1個減らすというのも面白い。

SRM627 LaserTowersDiv1 (難易度: 6)
レーザーをいくらか発射してなるべくたくさんの敵を倒す。
解法:見れば分かるだろうけどフロー。ただそのフローを上手く構成するのがなかなか考えないといけない。komakiさんのブログにないようなタイプの最小カットを上手く思いつくのは結構大変だと思います。

MSRM489 AppleTrees (難易度: 7)
40個のものを好きなように並べられるので40!かかる、というのを上手く改善する。
解法:特殊なDP.まず、r[i]が小さい順にソートしておく。持っておくのはdp[i][列の断片の個数][使った長さの合計]。これだけだと分かりにくいので遷移も説明すると、遷移は3通りあって、i+1番目のものを追加するときに、
新たに列の断片を作る →使った長さは増えず、断片の個数は1増える。これは1通り。
既存の列の片端に新しいものを追加 →長さが新しいもののぶんだけ増える。断片の個数は変わらず。これは列の断片の個数*2通りある。
既存の列2つの間に新しいものを追加して繋げる →長さが新しいもののぶん*2くらい増える。断片の個数は1減る。これは(列の断片の個数)P2個くらいある。
最終的な答えは、sum{dp[n][1][i]*f(i)}で、f(i)は簡単なので各自考えて。

SRM603 SumOfArrays (難易度: 7)
二つの配列A,Bを好きにならべかえて、C[i]=A[i]+B[i]を同じ値だらけにする。
A,B内で同じ値がないときは自明にFFTというのはわかるけど、これをごり押しでFFTを繰り返すことで
解けるというのがなかなか面白い。平方分割っぽい感じに大きいケースと小さいケースに分けて処理するのがここで出てくるとは。

SRM629 CandyDrawing (難易度: 7)
interpolationのいい勉強になる。

SRM570 CurvyonRails (難易度: 8)
すぬけのブログに概要が書いてありそう。
真っ向から「これは最小費用流だ!!!」といわぬばかりの問題設定のわりに、結構リンクの張り方が難しい。
これ正解者いないのは結構驚きだけど、なかなか上手くグラフを作るのが難しいと思う。
「すべてのマスをそれぞれある一つのループの中に属させる」ということが最小費用流で解けることは知っておいたほうがよさそう。

SRM518 Nim (難易度: 9)
こんなの思いつくかという感じの変換をする→累乗→逆変換、というなかなか不思議な感じの問題。初めて見た。
これは実質FFTと同じような変換らしい。

番外編1(とりあえずDiv1Hardに正解してみたい人へ)

簡単なDiv1Hard寄せ集め。

SRM343 RefactorableNumber (難易度: 0)
ACRushが2分で解いた。Div1Easyでもなんら違和感ない。

SRM151 Gauss (難易度: 0)
有名問題。本当にやるだけ。

SRM181 KiloManX (難易度: 1)
見ての通りのbitDP。問題名はロックマンXからきてるのかな。

SRM409 GridColoring (難易度: 1)
見ての通り独立。このくらいならMediumでも許せるかもしれない。

番外編2(難問好きの人へ)

早々投げ出した問題群をどうぞ。

SRM551 SweetFruits (難易度: 9)
典型的な「知らないと無理」。行列木定理で部品を数えてDPをしていく。行列木定理を使う、といわれても十分難しい。

SRM602 BlackBoxDiv1 (難易度: 10)
鏡の反射という時点ですでにやめたい。
かなり本質っぽい大事なことを言われたのに後半のいかにもDPっぽいパートが全然解けないので諦め。

SRM456 FunctionalEquation (難易度: 10)
前半の関数方程式を解くパートが数学オリンピック勢とかじゃないと無理な上、後半も普通に難しい。
前半は解説を読めば式変形をしているだけなので、理解はできる(でもこんなのIMO勢じゃないと無理だと思う)。
その後半の解説を一回を読むのを途中で諦めたが、二回目で何とかして300問目に解いたことになっている。

SRM400 CollectingBonuses (難易度: -)
問題の傾向が特殊すぎるので難易度はなしで。
あの手この手を尽くして、math.hの普段使わないような関数にも頼ってなんとかして誤差を小さくする問題。
こんなの一発で通せるほうがどうかしていると思う。

まとめ

みなさんDiv1Hardを300問解きましょう。SRM573のpractice roomで(問題として)お待ちしています。