無事2週目。 @co_bachieさんから「解いたコードを毎日コミットしていけばGitHubに草生やせるね！」とアドバイスを頂き、一石二鳥と小躍りしながらこの週からリポジトリ作って草を生やすようにしました。
ルール(？)
- AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
- 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
今週のおすすめレート: 681
要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)
ABC258が無念の2完で終わってしまったため、先週より100くらいレートが落ちてます。悔しい。
やった問題
2022/07/03
- 自力AC？ 🙆
過去に解けなかった問題の類題だったので一瞬怯み、正規表現？等と焦ったものの*2、冷静に考えれば前から順に素直に"fox"を探し、成立したらそれを取り除いていけばO(N)で解けるじゃない、までまあまあの速度でたどり着いたのでよかった。今度からちゃんと時間測ろう…
ポイントは多分短縮済み(仮)の配列を別に用意しておくところかなぁ。 このタイプはもう20分もあれば解けるはずだ、多分。
2022/07/04
- 自力AC？🙆
- 所要時間: 約40分
「直前の比較結果と今回の値を都度比較していく」的な感じの全探索系でよくあるやつ*3で、入力全部取ってから一気に比較しようとすると実行時間的に危険なやつでもある。圧縮しちゃえば文字単位の比較は高々26回なのでわりと安心。あんまり意識してなかったけど辞書順先頭の指定があるのでsortしておくのが意外と重要。
解法そのものよりも、配列にするのかハッシュにするのかデータ構造で悩んでこのタイム。これはもうちょっとサラッと出来る気がする。
2022/07/05
- 自力AC？ 🙆
- 所要時間: 38分
植木算的なイメージが湧くと解法自体はすぐ出るヤツ。(n - m).absが2以上であればそんな組み合わせは存在しないと言い切れるので、あとは[n, m].minの階乗さえ計算すればサクサクと解ける。
ということで曲者だったのは階乗の方で、素朴に掛け合わせていくと数の爆発がヤバくTLE必至。「解答はmod(109 + 7)でよろ(要約)」というお言葉に全力で甘え、階乗を作っていくときに都度modを取る必要がある。ちなみに109+7の壁は13!くらいでぶち破る模様。*4
これが簡単ですごい効果は絶大。2000msの壁をやすやすと超え、全テストケースが60ms前後に収まりビビる。
2022/07/06
- 自力AC？ 🙆
- 所要時間: 27分
バブルソート風の動きで過去のトラウマ再燃案件かと思いきや特定の操作をN回した後の状態を示せ、というもの。
落ち着いて読み解いていくと「左端にあるカードを右端に到達するまで動かし、右端に到達したらまた左端のカードに移り同じ操作を繰り返す」という規則的な動きなので、「最後に操作したカードはどれか」「そのカードの何回目の移動で終わったのか」が分かればそこから最終的な状態を導けるタイプの問題。
10回分くらい手作業で追っていくとはっきり確認できるんだけど、30回動かすと元の並びに戻るため実はN.mod(30)回動かすのと同じことになり、そうなると愚直に動かしていっても高々29回なので、そっちの解法でも処理時間的には解けたんじゃなかろうか、試してないけど。
2022/07/07
- 自力AC？ 🙅
- 所要時間: 45分
「グラフのデータ構造ってどうするんだっけ？」とかそもそも事案で悩み始めたのでこりゃダメだと思って開始15分くらいで解説を読み始める。多分これコンテスト本番でいきなり出くわしたら解けなくてめっちゃ凹んでたやつ。
要するに片方に対して任意にボール番号を付け直してもう片方と同じに出来ればよい(さすがにそこまでは分かった)わけで、片方のボールの番号をひたすら並べ替えてもう片方と比較していく、というのが正攻法らしい。
N2の配列を最大N!回比較するので計算量としてはO(N^2 * N!)なんだけど、今回のケースならそれでも最大361msで余裕のAC。まぁNの最大値8だからね…
しかしこれ、なんかうまいこと規則的なソート方法を見つけて計算回数減らせないもんなんだろうか、と思って他の人の提出を散々眺めたものの、いまのところRuby最速の人でもArray#permutation使ってたから無理そう。
さっさと解説読んだのに変に時間がかかったのは、N*Nの二次元配列を作りたくてArray.new(n, Array.new(n, 0))とかやってたせい。ちゃんとリファレンスに書いてあるのに……
一応無向グラフなので実は左下半分要らないんじゃないかとは思うんだけど、多分わざわざ削るような処理入れた方がややこしくなる予感はしている。
2022/07/08
CODE FESTIVAL 2014 決勝: C - N進数
- 自力AC？ 🙆
- 所要時間: 30分
問題文を読み取るのにちょっと時間がかかったんだけど、要するにAという値がN進数でNと表記できるかどうかを検証して、見つかったらそのNを答える問題。x.to_s.to_i(x)で出せると楽なんだけど、xが最大10000まであるので途中でArgumentErrorになっちゃう。
とりあえず素直にループぶん回して検証してみたら、わりかし単純な計算だからなのかすんなり通った。でもこれ出来れば一般項出してO(1)で、と思ったものの、解説読んでもこの解き方だったので難しいのかも。少なくとも一般項出すために悩む時間を考えると競技プログラミングとしてはコスパが悪そう。
ここから速度上げていくの、精々二分探索するくらいしかやれることがないみたいで、Ruby最速の人はそれで7msなのでコストパフォーマンスとしても十分っちゃ十分なのかなぁ、と何となく納得してみた。
