C 白昼夢 / Daydream

コード
https://atcoder.jp/contests/abc049/submissions/6953590


微妙に迷った問題。
ちょっと考えて「これ後ろから調べていけば被らなくないか？」と思ったが、どうも裏道っぽかったからパスしてしまった。
というのも、仮に被るような文字列だった場合に解けないのはちょっとどうなんだろうということで、これは違うだろうと考えたからだ。
解いてから解説を見ると意外にもこれが想定解でびっくり。

その後しばらく考えて思いついたのがdp的な解法。
Sのi番目から始まる文字列で、指定の文字列(dream, dreamer, erase, eraser)が作れるかどうかは、Sのi-1番目以前には関係しないので、i=0から順に調べていこうという感じ。
こういうdpの典型例的な問題あっても良さそうだけどあるのかな？
重複なし優先度付きキューとしてSTLのSetを使ったが、dpでSetなんか使うのかなー違うのかなーとも思ったが一発でACできてほっこり。
計算量を計算しようと思ったけど思ったより難しかった・・・。
重複なしで計算量を多少落としたつもりだが、指定の文字列の文字数が短かったり、文字数のバリエーションが多かったりすると結局ほぼ全探索になる？
そういう場合は後ろから調べると被らない、という部分を活用しないといけないのかな。
そっちの解法も後で解いておこう。

D 連結 / Connectivity

コード
https://atcoder.jp/contests/abc049/submissions/7033954


今回はUnion-Find！やったー！
データ構造を扱う問題を調べながら理解できるとテンションが上がる。
何ならライブラリとして理解しながら実装していく瞬間が一番楽しいかもしれない。

もちろんUnion-Find使うよっていう部分は分からなかったから最初は解説頼り。
公式の解説は想像以上に簡素で、本当にUnion-Find使うよっていう部分しか分からなかった。
実際にUnion-Findを使って実装してみると、その後に工夫がまた1つ必要で、愚直に計算するとO(n^2)でTLEした。
「n<=2*10^5ならそんなに重い処理じゃないだろうしO(n^2)くらいけるのでは？」と思ったが全然そんなことはなかった。
10^8が相当軽い処理でギリギリとのことで、10^6,7程度を目安にするべきらしい、覚えておこう。

その後の工夫を実装してスッキリ解けたのだが、工夫部分説明がなかなかしっくり来るものがなかったから記録しておく。

Union-Findで道路のグループroadと鉄道のグループtrainを作成したとき、i番目の街とj番目の街が道路と鉄道のどちらでも繋がれているかどうかを求めるには、
・i番目の街が属する道路のグループにj番目の街が属しているか
・i番目の街が属する鉄道のグループにj番目の街が属しているか
この論理積を取れば良い。
これはグループ内で街が条件に合っていくか走査していくようなイメージだと思う。
これをi,jで2重ループすることで総数を数えられるが、この考え方に固執すると2重ループを外せず工夫部分をすんなり理解できない。

考え方を変えて、
・i番目の街が属する道路のグループとj番目の街が属する道路のグループが同じかどうか
・i番目の街が属する鉄道のグループとj番目の街が属する鉄道のグループが同じかどうか
の論理積を取ることを考える。
どちらもやっていることは同じだが、考え方は結構変わる。
片方が属するグループ内でもう片方の街を探していくのではなく、それぞれの街が属するグループを求めてから同じかどうか判別するイメージ。
こう考えると、道路と鉄道を分けて論理積で考えずに、(道路のグループ, 鉄道のグループ)のペアで保存しても良いことが分かる。
後は連想配列なりで総数を保存してあげれば1重ループで解けちゃう！

Union-Findの操作的には後者の方が近いが、単純に考えると前者の方が直感的だと思う。
自分は前者の考え方からなかなか抜け出せずに、多くの解説がなかなか理解できなかった。
図説を見て、さらに自分で書いてやっと抜け出せた。
考え方を固定してしまうのは怖い怖い。

C 単調増加

コード
https://atcoder.jp/contests/abc038/submissions/6927104


最初の提出ではいくつかのテストケースでWAをもらった。
なんでだろうと最大値を考えた場合に、10^5と10^4を書き間違えて1～10^4まで合計してもint型でいけるだろ！って思ってしまったせいで少し時間を食った。
本番ではWAはもちろん避けたいところだけど、こういうミスもするだろうなぁと思うと気が重いなぁ。

まぁさくっと解けて良かったのだが、解説を見てみるとどうも少し違う。
確かに計算結果を答えに加えつつ、それとは別にiの増加ごとに答えを+1するのは少し違和感があったが、数式の理解が自分とは違う感じ。

解説では

D プレゼント

コード
BIT
https://atcoder.jp/contests/abc038/submissions/6942401
LIS
https://atcoder.jp/contests/abc038/submissions/6934327


この問題は完全にお手上げだった。
dp使いそうという、ソートしたら計算量減りそう、という予想は合っていたが、添字に持たせる意味を思いつけなかった。
なんとか思いついたのが、添字に入れ子にする箱の(高さ,幅)のpairのvectorを載せて、対象の箱の高さと幅が、vectorの中でソートした場合の高さと幅が同じインデックスになった場合にdpに1追加する！、なんていうのはあまりにも無理そう。
そもそもこれは漸化式(そもそもなってる？)として入れ子にできるかどうかを判別するだけで、dp[vector]になんてしてしまうとそもそも添字が絶対に被らないからただの全列挙である・・・。

BIT

まずは解説にもあるBIT。
解説を見るとそもそも添字に持たせる意味じゃなくてdpに持たせる意味を変えてきた。
i番目までの箱で作れる入れ子の最大数ではなく、i番目を一番外側にした際の入れ個の最大数とは。
i番目まででなく全体の情報を入れてしまうとdpにならなくないか？、と思ったが、なるほどソートすれば実質i-1番目以内の情報のみで更新できるすごい。

これらの情報のみで実装したらきれいにTLE。
なるほどここでついにデータ構造、競技プログラミングらしくなってきたなと結構テンションが上がった。
BITは分かるようで分からないようでな状態でライブラリとしてクラスを作成したが、やはり書いているうちにかなり理解できてくる。
完全な単体の情報を一部しか持っていないため、更新関数・クエリ関数に求められる条件が組み合わせによって異なることはしっかり理解できた。
結局和を保存するBITと最大値を保存するBITを作成し、今回使用したのは最大値を保存するBIT。

ここからはすぐにAC！、と行きたかったがそうはいかず、BITの使いみちの理解に手こずった。
確かに最大値を素早く取り出したいからBITを使ったものの、結局2重ループになりそうだった。
というのも、dpをBITとして実装し、i番目のdpテーブルを更新するために、j番目(0<=j<i)までのdpから最大値を取り出す、という方向性で考えていたからだ。
BITに持たせる情報を、幅ごとの入れ子の最大数にするというのはなかなか理解できなかった。
要するにjループの情報をそのままBITに持たせられている。

確かな理解を持ってACすることができたが、難易度の高さに対する驚きもかなりあった。
ABCでこのレベルが出るのかと少し自信をなくした。
データ構造というものをそもそも使ったことがなかったためなんとも言えないが、このような使い方が一般的なのかどうか分からない。
この使い方の感覚を慣れで養えるなら良いが、そうでないならつらいものがあるなぁ・・・。
dpはかなりバリエーションがあるらしい中で典型的なdpしか知らないし、その上データ構造を使ったことがないときたら仕方がないのかもしれないが。

LIS

次にLIS(最長増加部分列)。
解いたのはLISが先だが文脈的に後に。
解説を見てもいまいちピンと来なかったので、調べてるうちに見つけた解説とは別解。
LISなんて言葉知らなかったし、知っててもこんなのなんのために計算するんだよと思うこと間違いなし。
この問題でLISが使える理由を理解すると、心からなるほどなぁと思えた。
こういう場面において有効に使える、というのが分かったのはかなりの収穫。
解説に乗っていたのは次のBITを使った方法だが、正直それよりもかなり直感的で納得のいく解法だと感じた。



いやー難しかった。
継続してかないとレベル上げられないな。

それと文章見にくいなーと思ったから見出し機能なんてものを見つけて使ってみた。
多少ましになったかな。

半年ぶりの投稿。
上半期忙しい予定が1年中忙しくなりそう。

ここ2ヶ月くらいでHTMLとかCSSとかJavaScriptとかTypeScriptとかReactとかReduxとか使えるようになってChrome拡張をリリースしたりしてた。
このTwitter・ブログはあまりリアルとは紐付けたくないのでリリースしたものは秘密。
WEB系は初めて触るので色々苦労したけどさすがにWEB系全く触れませんはちょっと頂けないなと思ったよね。



今日は半年ぶりに競技プログラミングの問題を解いた。
もちろんC++。
JavaScript触ってるときはそもそも型という概念がなくてC++の静的型付けが恋しい。
TypeScript触ってるときはJavaScript本来の自由度の高いオブジェクトと相反する無駄に厳しい型付けからC++の適度な静的型付けが恋しい。
そんなことを思いながら勉強していたが、改めてC++触ったらやっぱり不満出るんだろうなぁ。
久々に触ったC++はそんな杞憂は吹き飛ばす書きやすさ・・・。

以下本編。


コード
https://atcoder.jp/contests/abc030/submissions/6923058


ABC030全部解いたうちのD問題。
A問題は"DRAW"と"DROW"を間違えて「は？？？」って何度もWA食らってた。
10^100000とかいう異常事態にどうしようかと為す術がなかった。
10^100000 ≒ 2^332192
BITSET<340000>とか使うのかな？なんて考えて素直にギブアップして解説をちょろっと見た。
なるほどmodは多倍長整数使わなくてもStringから1桁ずつ計算できるのか。
その部分でどうしようもなさすぎてその先はあまり考えていなかったが、ループ部分とループ外の最初の部分に分けて考えるのは思い付けてそう。

その後部分点があったのでとりあえずlong long型に入れてやってみると意外とすんなり部分点が取れたものの、Stringのmodを使うと今まで部分点取れてた部分の一部もWAになるのが非常に困った。

原因はこちら

新年初(記事にする)問題。


コード
https://atcoder.jp/contests/caddi2018b/submissions/3928826


解説見たらだいぶ簡単だけど思いつけない。
問題読んでまずゲーム木の問題なんだろうなぁと考えたけどゲーム木っていう言葉くらいしか知らないからどうしようかと。
結局諦めて解説見たわけだけどたぶん数時間考えても解けてなかったと思う。

今回の学びは、2人が順番に何か操作する問題を解くのコツは自分が完全にコントロールできる部分を把握するべし、ということ。
「1～3までの数字を順番に言って最後に10言ったら勝ちゲーム」でも、自分と相手が言う合計は最小で4にコントロールできることから、4の倍数を考えることが勝つためのコツとなる。
今回の問題だと、「各種1つずつまでしか取れない→各種の2の倍数を考える」と考えればよかったのだろう。

これが3人になるとどうすれば良いのだろうか。
取る数が0か1だとすると、2人の取り方で0～2の範囲がある時点で自分が取れる0,1では全くコントロールできない。
0と3は能動的に避けることができるが、1か2に絞るのが精一杯だろう。
そういう問題が出たらどう解けばいいんだろうか？
再帰で解ける範囲なら解けそうだが、それ以上になると無理だろう。
また別の考え方があるのだろうか。

1つ挟んだけどしっかりやり遂げた。


コード
https://yukicoder.me/submissions/306799


前の記事で言った通り、ダイクストラ法そのものは関数として実装していた。
典型的なダイクストラ法の問題(頂点とコストだけ)しか知らないので、これをどうやってダイクストラ法で解くのか割と悩んだ。
解説見ても頂点とコスト毎に最短距離を求めるダイクストラ法としか書かれておらず、分かりやすいコードを見つけるのに苦労した。
見てなるほど、取り得るコスト全てを探索して、それぞれの最短距離を保存していくのか。
イメージとしては、グラフの頂点それぞれにとり得る総コストと同じだけ頂点が連なっている感じだろうか。
拡張ダイクストラ法を調べていて、どこかで3次元で上から順に求めていく、というようなことが書かれていた気がするが、今になってなるほどと思う。
しかし、この方法だと計算量がかなり多くなるような気がするがどこまでやれるのだろうか。
とり得るコストの量が多くなってくるとゴール手前はかなりループするんじゃないかと思うのだが。
処理自体は大小関係の比較と配列への代入と、かなり早い処理しかないから大丈夫なのだろうか。
計算量のオーダーについても考えていかないとまずそうだと最近感じた覚えがあるが、これもその一種だろうか。
単純に考えれば最短距離[頂点][コスト]全てに代入される可能性があるのだからO(n^2)だろうか？
だがどう考えても町やコストじゃなく道の数に比例して計算量は増えるだろうからよく分からない。
要勉強。
どちらにしても今回の制約内ではまず問題ないだろうということは分かるからとりあえず良しとしよう。


次にコードのお話。
以前自力で作成したプログラムの道情報は、いわゆる隣接行列というもので、無駄が多いらしい。
隣接リスト形式に書き換えることで無駄が減るのはもちろん、スタック・キューへの適応もより自然になった気がする。
そもそもグラフについての知識がなさすぎたな。
そんなこんなで蟻本見ながら自分が分かりやすいようにプログラムを完成させた。
なんでも乗ってる蟻本しゅごい。

で、ダイクストラ法の関数を実装している時点でうすうす気づいていたが、こんな典型的なダイクストラ法の関数作って意味ないだろうと。
なんならオブジェクト指向で形式さえあっていればどんなグラフでも返せる形にしている。
そんなことを考えながらとりあえず作った関数を改造していたのだが、関数作っておいてよかったとしみじみ感じた。
どこを変更してどこを拡張すればいいか、ということを考えたいのであって、素のダイクストラ法に対してリソースを使いたくないからだ。
ダイクストラ法の処理を何度も何度も書いていれば別かもしれないが、そんなことをする予定はないしもそもそれが無駄だろう。
おそらく与えるグラフの形式は毎回変わるので、オブジェクト指向云々は若干どうでもいい感じはする。

この改造したダイクストラ法のプログラムを作成してすぐ解けたか、というとそうではない。
大体答えが出るが、いくつかランタイムエラーが出ていた。
こういう場合、おそらく配列の範囲外参照だと当たりをつけているが、大体問題ないだろうと思っている。
さぁそうなった場合にどこを調べるか。
もちろん多少ややこしい処理をしているダイクストラ法の関数内だ。
グラフの頂点の数が小さいのかとか、判定の順番的にコストがオーバーする可能性があるのかとか、色々調べてみたが解決しない。
学生時代に研究で使って何も解決しなかったGDBまで使って調べると、なんとmain関数内でエラーが。
原因はグラフの要素数だった。
町の数を要素数とすべきところを、道の数を要素数としていた。
大体の場合、街の数より道の数の方が大きいので多くがACだったわけだ。
確かにREのテストケースは短いものが多かった。
似たような要素数のミスがあったABC017 D サプリメントのときは未だに問題が悪いと思っているが、この短期間に同じようなミスを繰り返すのは少し凹む。
要素数でミスしないようにするのはもちろんだが、テストケースが分かる場合、そのテストケースの傾向から間違いの検討をつけられる気がしなくもない。
これも1つの学びとして吸収していこう。
コンテスト本番ではサンプルだけから考えるのは少し厳しそうではあるが、学習段階では無駄に時間を取られずにすむかもしれない。




今年中は新しいアルゴリズムが必要な問題はもう解かない予定。
簡単なのはちょっとくらい解きたい気持ちはある。
年末だしゆっくりしたいところだけど普通にやることが多い。
何よりスマブラ練習しないといけない。
普通の格ゲーとあまりにも操作感が違ってかなり苦労している。
サタパでやらせてほしいなぁと思うけどCスティックないからだめだね。
それでは良いお年を。