ABC156

久しぶりに楽しめたかな。欲を言えばFを通したかったけど。

A - Beginner

実装重いと思いながら時間をかけて書いた。改善するとすればmax(100 * (10 - n), 0)とするくらいか。これも制約や問題文をちゃんと確かめる必要があって大変だけど(さすがにn=10のとき100 * (10 - n)が0でない問題は酷いけどw)。

B - Digits

Kで割っていって何回目で0になるか。まあNは0より大きいので。

C - Rally

これBじゃないの。「整数値の座標」とのことなので全探索した。全探索しない方法もあとで考えたいところ。

(追記)時間計算量O(N)、空間計算量O(1)で解けた。まあこういう式になるのは知ってたけど、改めて計算した(こういう計算たまにしないとね)。

D - Bouquet

けっこう混乱してしまったが、要するに答えは2^nよりすこし少ないくらいだ。そこから、0本とa本とb本のケースを引き算すればいい(0,a,bは相異なる)。nがでかいので、都度計算するタイプのcombを貼る(計算量はn関係なくO(b)で済む)。

E - Roaming

Dと同じような感じだが。n-1回移動すればどんな配置も実現できる(最終的に人がいる部屋が少なくとも一つあるのでその部屋の人は動かなくていい)。1回のときは特殊だが、制約はk>=2だった。2回以上n-2回以下は、n>=3なので適当に迂回させればより少ない移動でできた配置は全て実現できる。0の個数がk個以下が実現できてそれ以外は無理なので、もうちょっと高速化できる気もするが、素直に0の個数がi個の通り数を足していこう。0の個数がi個のとき、n-i個に分けるのでn-i-1個の仕切りを入れる。各部屋に1人以上なのでn人からn-i人減らしてn-i-1個の仕切りを加えてn-1個からn-i-1個を選ぶ。0の入れ方はn部屋からi個選ぶ。掛けて足していく。

F - Modularness

なかなか読むのが大変だけど。aは単調増加っぽいけど停滞することもありm以上になったら戻されたりもして、それでn-1回中何回増えるかと。とりあえずO(kq)の時間は使えるので、a_0からa_kまでk+1個のシミュレーションを書いた。これをどう使うか。a_k-a_0 mod mだけずれていくんだよね。0以上m未満の範囲で棒グラフみたくしてそこから棒の長さをmにして幅mの箱をずらして、とか考えても無理そう。で、k個のペアそれぞれについてa[i]<a[i+1]となるようなオフセットの範囲は求まるなと思った。n/k回のループで毎回のずれをstd::setとかに記録して二分探索で(log付いちゃうけど)個数はわかるかなーとか。しかし、kが小さいかもしれないことを忘れていた。n/kが5000以下とは限らない。

次に思いついたのは、そもそもa[n-1]は求めることができる。基本的には増えていくけど、m以上になったらmを引かれてしまう。増えるはずが減ったということが、a[n-1]/m回くらい起きているはず。という方針をバグと戦いながら頑張っていたが、dがmより大きいことがある(特に、ずっと大きいこともあるのが痛い)ことを忘れていた。当然サンプルは通らず終了。終了後、n--; x %= m;と最初にするようにした。間違った方針に時間を費やしていては、1時間はあっという間だった。ん、dを最初からmod mとっておけばどうだ?(ほんと色々アイデアは出てくる)

(追記)dをmod mにすることで解けた。想定解と同じだ。

ABC155

無限にレート下がるね。水色がちらつくようになってきた。精神状態がはっきり悪い。実力が下がっているのは仕方ないとしても、今の実力は発揮できる状態でいたい。

A - Poor

クソムズ(楽な実装が見えない)。3通りをループで回した。

B - Papers, Please

クソムズ(実装は簡単)。条件を満たすためには、偶数が存在しなくてもいい。チェックする必要があるのは偶数で、3でも5でも割り切れないものが一つでもあったらダメ。いつもの3倍くらい見直してから提出した。

C - Poll

C++を信じてvector<string> s(n);。最初std::arrayにしてたが、入力でつまづいて、脳への負荷を下げる方針にした。しかし、std::mapは実行速度に若干の不安があり使わなかった。まあ大丈夫だけどね。ソートしてカウントする。i番目の時点で同じ文字列が何個続いているかを別の配列に入れて(12312111123112みたいになる)、最大値(さっきの列だと3)のところだけ出力する(ソートしてあるので順番に出力するだけ)。ここはいい実装を思いついて気持ちよかった。

D - Pairs

まあ二分探索+しゃくとりっていう典型。ただし負の数があるので、実装力か考察力が必要。実装力で押した。しゃくとりの代わりに二分探索してTLEしないかは微妙なところ。まあ俺がちゃんと書けば行けるだろうとは思ったけど(後で確認する必要あるな)、しゃくとりのほうが書きやすい面もあると気づいてしゃくとりに。4通りのしゃくとりを書く必要があると気づいたけどそれをなんとかする考察力もなく(ここが今の自分の調子が悪いところ)、4つ書いた。しゃくとり自体は慣れていてすぐ書ける。負の数のときにループを逆に(大きい数から順に)回す必要があるのは最初気づいてなかった(マジで難しいこの問題)。しかしいつまで経ってもサンプルが通らず。自分自身とペアになれないとか入れ替えたものを区別しないとかでサンプルの手計算も複雑になる。結果的に、自作の二分探索がバグっていた。(-3)/2は-2じゃないんだね。けっこう自信を持っているライブラリだったのでショックだった。

3完かと思ったのでホッとした。もうちょっとレーティングを意識した立ち回りが必要なのかなあ。今回だったら、実装は重いが確実に解けるDではなく、すぐに解法は見えないけど解いてる人が多いEに行くほうがよかったか。やっぱり、解けるとわかっている(早解きできるともコンテスト中に解けるとも言っていない)問題をやってしまうんだよなあ(そして時間がなくなる)。

E - Payment

残り10分で問題文は読んであったけどさすがに貪欲を書くしかできず(それを書いたのはえらいが)サンプル合わず終了。こういうのを日常生活の中で考えておかないの、弱いなあ。

F - Perils in Parallel

座標圧縮要らなくない?なんで難しい問題で簡単にできる面倒な操作を加えてるん。まあ座圧なしで解けるやつかもしれんけど。区間の重なりパリティは面白そう。しかしDでハマっていたため、解いている人が異常に少ないFに注力する精神的余裕はなかった(問題文は読んだ(余裕がないときって読むのに時間かかるんだよねえ))。

ABC154

E以外の5完。Dまでが簡単だった。もはやこのパフォーマンス値で落ち込むこともできない。

A - Remaining Balls

けっこうよどみなく書いていたつもりだけど、1分半かかってしまった。これは仕方ない。

B - I miss you...

Aより簡単。string(s.size(), 'x')みたいにするか迷ったけど、range based forでsを書き換える方針にした。

C - Distinct or Not

全部大文字のYESかい。ソートして隣同士同じのがないか調べる。これも簡単。

D - Dice in Line

これも簡単、と言いたいところだが、時間がかかってしまった。やることは簡単で、期待値の区間和の最大を求めればいい。結局シンプルにダイス1個の期待値で累積和を持った。

E - Almost Everywhere Zero

解ける問題であることはわかる。しかし、見えない。問題文や制約が、解法はこれですよと語りかけてこない。いや桁数も少ないしどうやっても解けそうではある。桁DPに見えるんだけど、めんどくさそうだし、Kが小さいことを生かしたくなる。しかしKが3通りあるのをまとめるのがまた難しい。この辺は力があればできるんだろうなと悔しく思う。最終的に使う3つの数を1000通り固定したら?それも、最上位でNと一致するときしないとき、一致するなら次の数も一致するかという場合分けがめんどい。さすがにK固定なら解けそうかなあ。Kが1小さいときに帰着させるのも面倒だよな。元々解きたくなくてFを覗いて解く自信がなかったので頑張ってEをやってた。21:43に諦めてFへ。

Fを解いて戻ってきた。桁DP、というのが何かは置いといて、そういう問題で自分がいつもやってるやつをやった。残り2分で「とりあえず書きあがったか?」という状態にはなったが、サンプルが合わないので終了。まあ最初からKの小ささを使わず桁へ行っとけという話だ。これどうやったら早解きできるのか見当もつかないな。まあもう少し自分でやってみる。

(追記)ACした。ミスしてた箇所は、「N以下」を「N未満」にするため1を足すところで111111みたいのを足していたのと、N=123040,K=3で123000を数えてなかったこと。後者はかなりきついミス。問題の難しさをもろに食らっている。そして解説の桁DPが全く頭に入ってこない。

F - Many Many Paths

パスカルの三角形の和。縦か横か斜めの和がわかるならいけそう。しかし途中で切れてるからなあ。自分はパスカルの三角形について詳しくないけど、どうにかして計算できるものを探す。和を求めたい長方形の上や左のへりにある数に注目する。パスカルの三角形は2つの数の和がその下にあるんだけど、へりの数だけ使えば中身を再現できるわけで、各数の寄与を見てみると、長方形だと広がったものがまたしぼむので難しそうだが、直角二等辺三角形ならへりにある各数がまたパスカルの三角形のように広がって、つまり1段進む毎に2倍になっていく。しかも自分自身と合わせて合計は2冪になるので簡単だ。長方形は、でかい直角二等辺三角形から直角二等辺三角形2個を除けばできるので、これで解けた。

(解説PDFを見て)r1=c1=0のケースが解ければいいの気づかなかった。まあそっちへ行ってこの性質を思いつくかは別だけど。ただ、経路で説明できる性質なのはいいね。直角二等辺三角形に分解するの気に入ってるし、想定解でさらに勉強できるという嬉しい問題だ。

冬アニメ序盤

2月になっちゃったけど。けっこう数が多い。面白さは微妙。クオリティの高いアニメが多いのは確か。最近ニコニコ動画でかわいいサムネのクリックしてあまり切ることもなく、って感じでもうちょい選択にノイズを入れたい気もする。

(追記)ソマリ忘れてたので書き足した。あと順位は一応付けたけどかなりてきとう。やはりアニメを1列に並べる方式は無理が。

恋する小惑星

みらとあおが出会って、それだけで話は終わっている。あとはその幸せな二人の日常を描くだけで1クール持ちそうだ。

痛いのは嫌なので防御力に極振りしたいと思います。

あざとい。メイプルがああいうキャラで、男たちが裏で見守ってるの、やばすぎるでしょ。アニメだからけっこうきれいに見えちゃう。でもアニメだからそれでいい。そういう場所を見つけたのがえらい。あざといアニメ。

マギアレコード 魔法少女まどか☆マギカ外伝

話が難しい。自分で考察するにしてもけっこう空気を読む必要があるタイプだと思ってて苦手。ただ、作画は化け物。この高位安定は凄まじい。

虚構推理

座りながら話が進んでいく1話前半好き。そこから、ちょっと変わった方向へ進んで。そして満を持して2話からあのかっこいいOPを出すのがつよい。ニコニコ動画のコメントでアリス探偵局が出てきたけど、言われてみればあれ解決は次回冒頭だっけ。台詞の文字数が多く一時停止しないとついていけない(自分にとって一回で正確に把握するのは困難)。岩永琴子の声、スカート。キャラデザがとてもよい。

ネコぱら

Switchのソフトにこういうのがあるのは知ってて、アニメ化すると知って実況動画を1個流し見。見た目はすごくいい。これがアニメになってどうなるかというところだったが、かわいい。電車のシーンで闇が深いみたいなコメントあって、そうだなと思ったけど、まあそういう作品だ。初回の時点では時雨をネコだと思っていた。これね、作画があと0.5段階よければ、第1話の作画を平均値にできれば、わりと化けると思う。これは作画で勝負するアニメ。だいぶ好きな世界。欲を言えば小学生くらいの見た目のネコがいてほしい。

ソマリと森の神様

この小野大輔は良い。みんな優しいけど、人間だとばれる不安、確定した別れの存在がスパイスになっている。初回の空気感をどれだけ保てるかというところ。

八十亀ちゃんかんさつにっき 2さつめ

1期は最終回だけ見た。冒頭のナレーションみたいので敬遠してた気がする。やっぱり全体的にかわいいしセーラー服の質感がよい。

へやキャン△

5分アニメだけどけっこうよくできてる。あまりタイプではない。

異世界かるてっと2

4作品全部知ってたのはでかかったんだな。盾は知らないので、それだけでおいてきぼり感がある。内容の安定感はさすが。

異種族レビュアーズ

原作の作画はpixivで「日常」のイラスト見てた人。アニメのキャラデザもけっこう好み。普通のアニメだとお風呂の湯気とかはあったほうがいいまであるんだけど、このアニメは確実に修正ないほうがいいタイプの修正で、その点微妙。天使、ドロップアウトじゃん。女だと思ってたけど、男ともとれるな(どっちでもないみたいな線もあるのかな)。最初は女のほうがかわいいと思ってたけど、だんだん男がかわいいくなってきた。