ABC143

5完。終了10分前37.0度。体調が不安だったので風呂に入らなかった。おかげでいい感じに解き進めることができた。結果がよかったわけではないがコンテスト中は楽しめた。

A - Curtain

max(a - b * 2, 0)。カーテンってひだがあるから「長さとは」って感じだよなと思いながら解いた。

B - TAKOYAKI FESTIVAL 2019

「これ絶対O(N)解法あるだろ」と思いながら愚直を書くのは微かな悲しさがある。

C - Slimes

簡単すぎて不安になりながら書いた。実装は、最近パターン化してる書き方できれいに書けたので満足。(解説PDFを見て)std::unique気づかなかったあああ!!使うかはともかくこれ気づけないのは。必ずしもソートと一緒に使うわけじゃないって知ってはいるけど、知ってるだけなのでこういうときに出てこないんだよなあ。

D - Triangles

3乗が通らなそうなのを確認。少し考えてから、あまりよくないけど制約から2乗の解法を探して2つの棒を固定することを思いつく。三角形になるというのは、もう1本の棒の長さがある範囲に収まるということ。幸いLの範囲は狭く、これは簡単に解けそうだ(実装が簡単とは言っていない)。累積和を使う(二分探索も思いついたがTLEを気にする時間が無駄(AtCoderでこれがTLEするわけないけど))が、範囲外アクセスをしないよう気をつけないといけない(長さ1500以下の本数というクエリが来たら、長さ1000以下の本数と同じなのでそれを返す)。選んだ2本がその範囲の中に入っていたら引き算しないといけない。とりあえずサンプルで様子をみて、3倍っぽいので3で割る(やる気なさすぎだろ!)。順番でも区別したら6倍になるが、自分のコードでは1つの大小関係だけ固定してるから半分になってる(と逆算したほうが思考を節約できるという当初からの読み通りですね(ほんとに考えるの疲れる))。できそうだという見通しはすぐに立つが、これを素早く実装するのは無理だなあ。(解説PDFを読んで)長いほうから固定するのいいな。いや探索する範囲が動的なのも発想としてはあったけどなるほどそういう。

E - Travel by Car

ただ最短距離を答えるだけならワーシャルフロイドでいけるなとまず思う。さて、距離とは。この問題設定は距離なのか?何であればワーシャルフロイドが使える?何であればダイクストラが使える?何もわからない、みじめな自分。まあ考える。ちょっと逆から考えてみるか。タンクの容量が100で、燃料0でゴールして、距離51なら燃料を51まで増やす。次にまた距離51なら空にしてから51まで増やす。かなり考えづらいが、いけそうに思える。そうすると、逆じゃなくてもよさそうだと気づく。ダイクストラ的に考えると、例えば「3回の補給と距離51の移動」のような情報を持てば更新していけそう。その情報もlong longの値として表現できるし、比較もそのままできる。さて、できればワーシャルフロイドでやりたい。ライブラリを漁るとなんかあったのでそれを持ってくる。メンバ変数の初期化順がアレだ。これだから普段使わないやつは。さて、2つを結合する処理を書く。書こうとして、このタンク容量でそもそも移動できないやつをINFにすることに気づく。けっこう複雑な問題。下位32bitに走行距離、上位32bitに補給回数とする。繰り上げみたいな感じで。移動距離は、最初のLまでなら0回補給で行けるので、Lを超えたら繰り上げという変則的な処理。サンプル合わないので気づいたけど、これダイクストラじゃないとダメでは。2つの経路を合成できないよ。当時は深く考えてなかったが、こう、ダイクストラの1個ずつ伸ばしていく更新方法ならできるやつに見えた。ダイクストラは、こっちのコードだと辺が多いグラフで定数倍が遅くなるとわかっているがさすがに使い慣れたほうを使う。コードを移植する。移動できない辺はそもそも追加しないことにする。N^2個の距離は別の配列を用意することにした(このへんもけっこう悩む)。なかなかサンプルが合わず困っていたが、そもそも距離の足し算が全然違ってる。繰り上げじゃないじゃんw(酷い)(余った燃料は意味がない)。いみふなミスを直すとサンプルが通るので一呼吸おいて提出。いやあ時間かかった。発想としてはけっこう早い段階で出てるのに。(解説PDFを読んで)何これ。やばっ。

F - Distinct Numbers

個数だけが重要だ。親切にもA_iはN以下だし。個数を数えたらソートしてしまってよい。なんか調和級数でO(NlogN)っぽい気もするがどうか。最初は上手く貪欲にK個を取っていく方法を見つけてそこから解法への道をうかがうという方針だった。多いのから順に取るの繰り返せばとりあえずOKっぽいがそれ以上のアイデアは出ない。しばらくして、多いK個を見てそれ以外のやつでそこを埋めるというのを思いつく。それ以外のやつの個数は累積和でわかるし情報は個数だけでいいから簡単(これも実際の実装を思うとそこだけでも時間内には無理だろうなと思った)。問題は埋め方だが、階段みたいになってる形はKによらず変わらないので、なんか難しそうだけどできそうではある。もう少し考えて、階段の空いてるとこの面積を事前計算しておいて、どこまで埋めるかを決めればその面積からちょっと掛け算で面積補正すればO(1)でできそうだから二分探索できそうと気づく。この時点で残り10分なので、諦めてしまった。解法が見えてると逆に無理なのが確定する感じ(実際は解けてない可能性も高いし、10分で書ける解法が存在する可能性も(低いけど)ある)。まあその方針で残り時間も考えてたけど。体温測ったり、ツイートが浮かんできたりね。

AGC039

体温測り忘れた。15分くらい経ってるけど36.8。

A - Connection and Disconnection

1回と2回の差を求めて掛け算するだけ系に見える。連続してX回同じ文字があったらX/2回必要。さて、本当に3回目以降も同じ増え方なのか?Sの最初と最後が同じ文字のときに現れる同じ文字の区間があるけど、それは1個でも違う文字があればそこで切られて3回目以降も同じになりそう。そうじゃないケースは簡単なので場合分けしてしまう。コードがかなり複雑になってしまったが、なんとかACできた。

B - Graph Partition

問題文の1行目を5回くらい読んでた気がする。問題文読むのほんと大変。問題を把握するのに5分以上かかった。有向だったらトポロジカルソートっぽいなと思った。最大値を与える向きがわかってたとしてどうするかとか考える。ダメそうなので普通に。二部グラフである必要があるのはすぐわかる。色々なグラフを考えてみるがよくわからない。グラフが木だったら簡単だ(直径より大きくはならないし直径は達成できる)。問題は偶閉路があった場合、それも複数あった場合だが、どう考えていいのかさっぱりわからない。例をいじっても何も出てこない。二部グラフを保ったまま変な辺を加えたら一気に縮こまっちゃうしな。Cも読みつつ21:45くらいまでBメインで考えていた。

C - Division by Two with Something

残りの100分ずっとCをやっていた。まず実験をしてみた。N=8の場合、256通り全部16。偶数の場合は簡単なのか?N*2だ。「本当に元に戻るのか?」と思わせといて1bitずつ反転させながらrotateしてるだけなのでN*2回かければ戻ると気づく。他も色々試すとだんだんわかってくる。もっと短いループもあるよという話だ。000111000111000みたいなのは周期3で同じのが交互に並んでるので3*2回で戻る。000が5回でなくとも、101が5回でもいいし、長さ3なので2^3通りが全部同じことになる。少しずつだけどけっこう考察が進むからずっとやってたわけだ。

こういうのは「X以下」より「X+1未満」のほうが考えやすいので1を足す。といってもXは20万桁だったりするので面倒。まあこのくらいなら簡単に書けるのでとりあえず書いちゃう。問題はN+1桁になってしまう場合だが、キャリーフラグをとりあえず持っておいた(結果的にそれでよかった)。N+1桁必要なのが不自然にも感じるけど、こういうのは2冪個ずつ処理するので、2^0から2^NまでN+1通りと考えればまあ。

実験していて他のパターンがなさそうなのでこれでやってみる。周期(ブロック長と呼んでいた)をMとして、N=M*奇数 となるものを見つける。計算量的にNの約数の個数が気になるが、「高度合成数」でググって(けっこう時間かけて)最大で160らしい。なんかNとlog(N)を混同していたみたいでNlogNとかメモしてあるけどN^2のことかな?計算量がきつそうだと心配していたけど、約数毎に上位j桁を見るのをjが小さい順にやっていけば、(約数毎に)O(N)で済む。約数のこういうのはyukicoderか何かで最近やった。周期Mは周期M*2とかにも含まれるのでそれを引いてしまう。例えば周期6なら、周期2と周期3と周期1を引けば、6未満の周期を持たない周期6だけが残る。これは逆に約数を小さいほうから見ていき、そういう周期を持つものが何個あるかを求めて、その約数のN以下の倍数から個数をマイナスしておけばいい。

さて、問題はその個数だが、2^N未満の全部ならわりと簡単で、M*2回以内で戻るものが2^M個ある。パターンとしては、例えばX+1が10011だったら、0以上10000未満と10000以上10010未満と10010以上10011未満を足せばいい。これはできそうだ。周期Mを調べてて上位j桁が確定してるとして、j>Mなら確定部分が周期になってたら1通り、j<=Mなら2^(最初のMbitのうち確定してないbit数)通り。確定部分が周期になってるか確認するのは順番にやればO(N)。個数の変数を小さい約数たちからもらったマイナスにして、足していく。それにM*2を掛けれたものを足していく。ん、もう解けてるのでは?サンプルを試すが落ちる。約数を探すときNと偶奇が一致する必要があるのでn%2を初期値にしていたが1+(n+1)%2とすべきだった。これで落ちなくなったが、しかし微妙に合わない。8多かったり少なかったりする。

この時点で23:00くらい。実装にめちゃくちゃ時間かかった。デバッグが全然できない。仕方ないのでソースコードを最初から丁寧に読み直す。しかし誤りは見つからない。なんか、(周期1でなくて)周期2でも周期3でもあるみたいの存在する?いやないよなあ。ちょっと自信なくなる。終了2分前くらいに気づく。10000以上10010未満を調べるときの確定ビットは1001?ではなく1000?だ!適当にソースを直すがこの残り時間で全然できない。終了後2分くらいで修正できたが、提出してWA。うーんコンテスト終了直後にACする実績解除したかった。コンテストが終わるとね、結果が確定した終了時と比べてどんどん落ち込んでくる。しばらく考えていたがわからず、ブログを書き始める。するとわかった。奇数と言っていた部分を奇数かチェックしてなかった。なまじNと約数の偶奇が一致する必要があるとか気づいたのがなあ。当時は解けてなかったからどんな情報でもメモしていた。そして、一から見直すべきだったのはソースコードではなく考察部分だった。そういうこともあるんだねえ。とはいえ、自力ACできたのはよかった。(終了直後は「まあそんなこともあるか」という感じだったのに)相当落ち込んでイライラしていたので、最低限それができてよかった。

夏アニメおわり

なぜか大量に見てたね。合わない作品も多かった。↑のタイトルがぶれると検索しづらくなるがまあええやろ。

まちカドまぞく

古典文法に則って丁寧に描かれるから見やすい。危機管理と予告が同じBGMなの最後のほうまで気づかなかった。お母さんがかわいいの珍しい。妹の良子は桃もぶれるかわいさ。ナレーションの伏線回収も気持ちよかった。

女子高生の無駄づかい

ようやくこの赤﨑が来たかと思っていたけど、キルミーベイベーの一挙放送を見たあとだと特にキルミー感なかった。ワセダにドン引きするところから始まって、いつの間にかとんでもない完成度のアニメになってる。

ソウナンですか?

8話の特殊EDが好き。というか普段のEDが好き。なんか作画も内容も微妙だと思ってたらいつの間にか好きになってる。全然違うけど「無人惑星サヴァイヴ」を思い出す。

可愛ければ変態でも好きになってくれますか?

こういう本編とEDのギャップがいいの既視感あるけど何だっけ。OP/EDがいい。本編は謎解きに1クールかけたけどかわいいキャラばっかなのでよし(南条とか藤本さんとか)。自分はこういう作品の妹が好きだけど最後に来てくれた。血がつながってないのは微妙。OPのパンツが妹のだったとわかるシーンがよい。

1年生だよ大作戦はあまり好きじゃないけど最終回でOP回収してきたのはよかった。微妙なところではあるけど。ロリコンをネタにするの好きじゃないんだけど、まあ先輩かわいいしいいかという感じ。

手品先輩

先輩と助手、名前が出てないのマジ?「助手って意外と痛いんだね」が好き。後半は微妙だった。やはり二人だけの時間がよい。先輩の助手に対する思いがいい。化学先輩の出番は本当に少なかった。

博多明太!ぴりからこちゃん

日曜日の癒し。明太子は狂気がなくてもいいんだよ!

ダンベル何キロ持てる?

ひびきがかわいい。冬服が冬セーラー服なのかわいい。

通常攻撃が全体攻撃で二回攻撃のお母さんは好きですか?

内容がゴミクズ。コメ付きで見てたけど、その内容に耐えられる人だけが残っていくので地獄感ある。というのは大げさだけど。後半は内容がだいぶ丸くなっていて普通のアニメみたいだった。とにかくポータがかわいいだけで見ていた(ワイズもいいけど活躍シーンが全然ない、ポータは存在そのものがかわいい)。最初は見てらんなかったED曲が最後にはけっこういい曲になっていた。EDはポータがかわいい。

お母さん萌えなアニメってけっこうあると思うけど、この作品はダメだ。その意味でのターゲットが自分じゃなかったということ。作品の作りが下手だとかは思わないけど、自分には本当に合わない。

荒ぶる季節の乙女どもよ。

見るのがつらいタイプだけど後半はだんだん見やすい内容になってきた気がする。ももがかわいい。本郷さんの2年生っぽさがいい。女キャラが尖ってるのがこの作品という感じで、男キャラも濃いけどよく見ると典型的な男。よくわからんけど、最後はこの作品に乗り切れなかった。この世界を構築するのすげえなあとは思う。

とある科学の一方通行

なぜか面白くないけど、エステルっちのキャラがよかったので。たまに出てくるラストオーダーはかわいいし、ひるみは名前が良い。芳川さん好き。

ダンジョンに出会いを求めるのは間違っているだろうかII

J.C.STAFFの悪いところが出てる。表面上きれいな絵でつまらないやつ。1,6,7,8,9,10話が虚無だった。リリのいいシーンが全然なかったもんね。

異世界チート魔術師

どうしてこうなった。初回付近はまあ普通の異世界ものだったと思うんだけどなあ。これは、スマホ太郎と違って楽しめない。内容が酷い。国王に言われるがまま戦争に参加してるのが意味不明。かわいいキャラいないんだよな。まあ凛はかわいいけどそれを前に出してくるアニメじゃない。エアリアルが見た目大人なのもアレ。木野日菜をもっと出せよ。ニコニコ動画で、つまらないのになぜか見てる人たちと一緒にだらだら時間を過ごす、そういうのもいいと思った。

ABC142

開始前37.0、Fを考えてるとき37.1、終了後37.2。開始前体が熱かった。昨日のyukicoder調子よかったから期待してたけど3TLEを出すなどの惨状で気分が転落した。本当につらい。こんな気分のまま寝るの?眠りにつくまでの30分から3時間くらいの時間をこんな気持ちで何もせず。うわあああああ!!!!

(追記)復習とゲームで眠くなるまで時間をつぶし、結果的にはそこまで苦しまず眠れた。よかったー。

A - Odds of Oddness

めちゃんこ難しいやん。奇数の個数を求める方針。n/2って書いたら偶数の個数だったのでnから引いた。

B - Roller Coaster

Bなのに10^5。でもAより簡単だった。

C - Go to School

遠まわしな言い方だけど、要するに、出席番号iの生徒はA_i番目に入ってきたということ。よくある書き方で b[a] = i; とすればよい。

D - Disjoint Set of Common Divisors

丁寧に説明されていて、よい。公約数は最大公約数の約数と同じことなので、最大公約数がどんな素数たちでできてるか調べて、K種類の素数が使われてたらK+1が答え。解けてみると、10^12という制約があからさま。

E - Get Everything

Dまで簡単だったのでこれもまさか超簡単なのかと思ってしまったが普通に簡単めなだけだった(なぜかMが12個しかないようなコードを書き始めてた)。鍵が2^N通りしかないのでそっちで考える(同じ鍵が複数あったら最安だけを使う)。O(N*(2^N)^2)でDPできるのでまあちょっと重めだけど、いつも5000^2とか100msかからんし問題ない。INFとして2^30を使うと和がオーバーフローすることに気づいてちょっと煩雑になってしまった。

F - Pure

ループを見つければよさそう(最小で2頂点からなるループだね)。問題は誘導グラフになってないときだけど、邪魔な辺があったらより小さいループが構成できてるよね。これをO(N)回繰り返せば条件を満たすものに必ず辿り着く!計算量も2乗程度なので余裕。ということで実装。閉路検出はよくわかってなくて苦手意識ある。探索中と探索済みのフラグを持ち、閉路が見つからなければ-1。閉路を具体的に求めるのもきつい。祖先に出会ったら祖先に戻るまで他のノードを探索せず頂点をvectorにpushしていく。余分な辺の発見は、std::setに現在のループを構成する頂点たちを入れといて(setじゃなくてvectorでいいって気づいたけど直すの手間なのでそのまま)、出てる辺が次の頂点でなくてかつループに含まれてるときそこで短絡してしまう(つなげなおす処理がけっこう複雑になってしまった)。それを高々N回繰り返せばいいはずだ。

しかしTLE。原因は、ループを発見してもなおループを発見しようとDFSしてたこと。直して提出するがまたTLE。1回のDFSの中で何回もループ発見することがありえる。直して提出するがまたTLE。ループの長さがNより大きくなったらthrowするようにして処理回数もN回に制限して提出、WA。うーん、解法が正しいならこうはならないはず。解法が間違ってるのかあ(あるいはまだバグがあるのかもしれないけど)。ギリギリまで考えてもわからず、とりあえずWAになってる無出力ケースで-1を出すようにしたのを最後に提出してみたが、まあWAだよね。うーん、どこに穴があるのか。そもそも、コードが汚いのがよくない。よほど理解がしっかりしてるときでないと汚く書いて時間短縮はないよなあ。そういうときは大抵きれいに書けるし。

(追記)解法はあってて、単純バグだった。結果的に閉路を検出して出力するだけのコードになっていたが、それで2個しかWAにならないんかい。バグが多いのは、このへんの処理の理解が浅いってことだからしゃーない。