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にならないんかい。バグが多いのは、このへんの処理の理解が浅いってことだからしゃーない。

yukicoder contest 225

すごくいい問題っていうのとは違うけど、実装が適度に難しくて気持ちいい。本当に久しぶりの20位以内。

No.892 タピオカ

ΣAの偶奇。簡単な問題で使わない情報があるの好き。

No.893 お客様を誘導せよ

問題文を読むのに時間がかかって後回しにしたが、順番に取っていくだけ。vectorを使いreverseするとpop_back()で対応できる。計算量はO(N*max(P))。解いてるときは深く考えなかったが、Nもmax(P)も10^5(合計人数は10^5以下のまま)だったらどうするんだろ。空でないvectorのインデックスたちをループ毎に作り直せばいいか(遅いようでオーダーは変わらないやつ)。

No.894 二種類のバス

切り上げを足して引くだけだが、AとBの最小公倍数が64bit整数に収まらない場合があるのでその判定が必要。できれば整数でやりたかったが、色々考えてdoubleで計算して2*T以上かで判断した。雑に判定できればいいので浮動小数点数が楽。

(writer解を見て)なるほどなあ、片方のバスのうち何回同時だったかを数えればいいのか。

No.895 MESE

難しそうに見えて、考えていくとけっこうスルスルと解ける。ビットの被りがないのでわりと単純な状況。大小関係の条件は要するに最上位ビットの位置。xの最上位ビットはbit0と決まっているし、そこからyの最上位ビットまではxが占める。yの位置を全探索できそうだ。あとは残りのビットだがこれはどう配置しても条件を満たすのでコンビネーションを2回やるだけ(整数の組が何個あるかわかる)。zは残りのビットに均等にばらけるので、例えば5個中3個をzが占めるなら 整数の組の個数*11111b*(3/5) となる。

No.896 友達以上恋人未満

問題文読むのに10分以上かかった。3.5秒で2^24は微妙なところで、定数倍が軽ければlogが付いても大丈夫かも。長さMODの配列を持てば各レーティングのうなぎが何匹いるかわかる。問題は倍数であることだが、logが付いていいなら1の倍数から順に愚直で間に合う(結果をその場に上書きすることでMLE回避できる)。レーティング0に注意。あとはA,Bを生成しながら答えを出力してxorとっていくだけ。計算量はO(N+MOD*log(MOD))。解説見るとloglogにまで落とせるらしい。さすがに、俺がC++で定数倍にかなり気を使って2122msなので、自分の解法が想定解ならずいぶんギリギリだと思ってた。