ABC115

A - Christmas Eve Eve Eve

Dの範囲が狭い。if文で書けるようにした問題だが、これは" Eve"を付け足すだけでいい。けっこう速く書けたつもりだが、やはり文字列の処理は時間がかかるようで、1分を少しオーバーした。

後続の問題名を見る。ネーミングが適当すぎないかw

B - Christmas Eve Eve

これは簡単。いつものBより簡単だが、Bらしさはあまり感じない(強いて言えばCっぽい)。一番高いやつに半額を適用するだけ。実際に素早く書けた。

今気づいたが、問題の設定がちゃんと問題名と同じになってるんだねえ。

C - Christmas Eve

見るからに簡単そうだが、すぐには浮かばない。連続したK本とかの制約はないみたいなので、ソートする。あとはループ回して最小を求めるだけ。ループ回数がN-K+1で、+1がどこから来たかわからず不安になる。まあたまに見る形ではあったが、当時はなぜかわからなかった。さて、最大値と最小値を知る必要がある。んー?しゃくとりみたいにしてもダメか。まあセグ木ならできるけど、もう少し考えよう。ソートしてあるじゃん。これは酷い。なぜソートできたかも忘れている。帰着された問題を次のステップへ丸投げしてるからね(短期記憶なさすぎだろ)。サンプルが合ったので即提出(終了が10分遅くなったこともあってなんか焦ってる)。

D - Christmas

やっぱり今回もルンルンだね。問題文の言いたいことはすぐにわかる。Nが小さいので64bit整数でいける。だが解くのは骨だ。サンプル1を手で確認してから考察に入る。まず、レベルLバーガーの層数とパティの数を求める。2倍して3を足すとかでいける。Nが小さいのでまずそれを全部求める。B(L-1)P(L-1)Bみたいな形。んー、木を根から辿るように、自分が今どこにいるかを確認していけばよさそう。ただ、それで解けることはわかっても、具現化するのが自分の力ではかなり厳しそう。もう少し考える。再帰でどうだ。Nの一つ小さな問題が解けてるなら解けるのでは?解けそうだ。変数をグローバルに移動させる。ラムダ式再帰も知ってるし最近書いたし便利なんだけど、よどみなく書けるほどには覚えてないので普通にグローバル関数で。けっこう冗長気味に書くチキン戦法(それが無難なのかは知らない)。けっこう区切りが多いから境界や実装量で困ってたけど、1段分だけやればいい再帰は素晴らしい。前半部分を足し忘れてサンプル蹴られる。直して合ったらやはり即提出だ。

終わってみれば簡単回(自分にとって簡単だったかはともかく)。基本を確認できるいい問題だった。

ABC114

A - 753

なんかうまい書き方があるか一瞬考えたけど、単に書いて時間はかからないのでそれで。

B - 754

またルンルンが出てくる。あのときのwriter誰だっけ?

やるだけ。文字列を数値にする方法を思い出そうとかと一瞬思ったが、単に書けばスピードが出せる。ここはいい動きができた。

C - 755

ちいさな計算量でできる方法もありそうだが、3^9でGoogle検索して19683と小さいので、10^9未満(10^9は七五三数でないため)の七五三数を全列挙する方針にした。桁数で分けて、k桁なら3^k(この計算はpowを使った)回ループして、k桁の数を構成しvectorにpush_back。forのネストが何個か最初は見えてないので頭を使う。列挙したらソートと思っていたが、よく考えたらN以下のものが何個あるか単に数えればいい。解いてる途中で「1回以上現れる」という条件を忘れたが、修正すれば通った。

D - 756

N!の約数のうち約数をちょうど75個持つ正整数の個数を求めろという問題。「約数」が2回出てくるので意味を把握しにくい。N!が都合のいい特徴のありそうな数じゃないので、とっかかりがない。とりあえず単に七五数かの判定を考える。75=3*5^2(最初5で割って15*5にまず分解してしまったが75が25の倍数に見えない文脈ってあるんだね)。素因数分解したときに、例えば素数が3個出てきてp0^2*p1^4*p2^4とかなってれば約数は75個になる。他にもあって、全部でたぶん 4,4,2 24,2 14,4 74 の4つ。これを手動でソースコードに入れさせる問題なのがちょっと嫌な感じだ。100!の扱いは、わからんけどとりあえずN!を素因数分解するんじゃないかと思って実装した。既に10分くらい過ぎてて更に5分くらいかかったけど。それでもわからない。うんうんうなる。まさか解けないなんてことは。このころのことはよく覚えていない。とにかく解法がわかった。N!に各素因数が何個あるかの配列aから、各hについてh以上のa[j]が何個あるかの配列bを作る。そしてb[74]とか書く。4,4,2のパターンが心配だが、他の3つのケースを書いていく。組合せの重複を除くのが大変だったが、なんとか全部行けそう。しかし微妙に合わない。ここからデバッグ地獄だった。合ってるはずなのにサンプルが合わず、バグは全く見つからない。永遠とも思える時間が流れ、24,2を24,4で書いてることに気づいた。14,4からコピペして14のほうだけ直せばいいと思い込んでいたのだ。見た目もきれいだから気づかない。さて、ここを直してもサンプルは合わない(今回は全体的にサンプルが親切でそれでも難しいといういいセットだったね)。9だけずれてるので、6と3を見つけて/2を消すという普通のデバッグができる。2つの素因数は区別されるから割る必要がなかった。理解の浅い最初のころに書いたコードだ。提出してAC。1時間近くかかったABCは相当久しぶりじゃないか。

デバッグ力というか、この特殊な計算をバグらせにくく書く技術がなかった。そのバグを取り除いたうえでも組合せの間違いがあったが、これは、状況がまあまあわかっていても言語化しにくいゆえのミス。とにかく、b[24]とか調子に乗って書いて、そこをバグがわかるように書く技術もないのに自覚せず、ただ長時間悩むだけになった、それがよくない。

第5回ドワコン予選

3完早解き勝負とは思わんよね。結果的にはわりといい順位だった。

A - Thumbnail

設定が難しくてサムネの話なの忘れた。わかってみればABCのBだ。怖がらなくてもやるだけ。

B - Sum AND Subarrays

これも怖い見た目をしているが、よく見ると部分列の美しさを全列挙できる。400点だからね。階層が深くて問題を把握できないと思っていたが、ここまで来れば、あとは列挙したものからいい感じにK個選ぶだけだ。最大値を求めたいので、上位ビットから見ていく。K個以上の数で立ってるビットのうち最上位のものは採用するに決まってるので、それ以外は捨てる。それを繰り返せばO(N^2*log(max(a)*N))くらいで行ける。10^6にlogがかかるの珍しいけど、まあ実行時間制限がいつもより微妙に長いしね。vectorをswapすることで定数倍に最低限の配慮。12msで拍子抜け。今回は計算量が顔なじみのやつじゃなくて多少の負荷があった。

C - k-DMC

ただでさえわからんのにkが設定されてるとか。DとCではさむ、あるいはMから左右を見る。とりあえずkがNの場合を考える。この問題が解けたらk=Nのケースも解けてるはずだからそれがわからないんじゃ話にならない。DMCが入り交じった文字列で色々考えるが、複雑そう。計算量的には、クエリ毎にO(N)の時間をかけられる(そういう解法とはかぎらないけど)。Mの右にあるCの数は累積和でわかる。Dの右にあるMについてそれを足せばいいのかな。じゃあそれも累積和にしたら?これはいけそう。一般のkについては難しそうだが、あれ、この削られるCの数って Mの個数*区間の右にあるCの数 で簡単に求まるのでは?累積和をきれいに書いて、本体部分の実装もけっこう軽い。「解いてる感」がある。解いたあとでも難しかった感触がありつつ多くの人が解けている。かなり満足感の高い問題じゃないだろうか。
ところでDMCという文字たちはこの問題の本質に何も関係ないのにDMCで考えちゃうのよくあるね。

DとE

主にDの部分点を考えていた。回転は相当難しそうだが、同値類と考えるとD=1なら任意の配置にできるんじゃないかと気づく。正方形に配置して、一番大きいやつたちを上手く配置すれば。縦横別々に考えられるか。ループさせてもっとも離れた場所を見つけてそのぶん節約できる。しかし、正方形より縦横どちらかだけ細くできる場合があることに気づいた。どうしようもない。縦横どちらに使うかを全部に対して決めないといけない。そもそも部分点は何が楽なのだ?部分点なら、どれを基準にするか900通り試せるってことか?それでいけるかもわからんが。
Eは(かなり考えて)置換か。いい問題っぽさがあるので解きたいけどなあ。