AGC037

今日は体調が悪かった。エアコン付けても寒いし暑い。体温は最高で37.5あって今日のAGC出られないかなと思ってた。直前まで様子を見てたけど、36.9まで下がって気分も悪くないので出ることにした。コンテスト中に何度か測ったけどずっと37.2くらいだった。今は36.9。自分では、いつもとそれほど変わらないパフォーマンスが出せている感覚だった。レーティングを気にせず、やりたくないAを途中でやめてBCへ行き面白そうなCをやれたので、まさに最近の自分が目指していた楽しむこと優先の立ち回りができていたと思う(素晴らしい)。ただ、今まで水色パフォ以上しか取ったことなかったのに、灰パフォを取ってしまった。それを知って特にショックを受けなかったのは、熱があったからだろうか。まあそれはいいけど、今夜や明日あたり、tokuminiさんやdasaponさんの結果と比較してわかる自分の無能さに落ち込むんだろうなあとは思う(今から気が重い)。最近思考が遅いのは悩んでるけど仕方ないのかねえ。

体調がうんと悪くなったら撤退することになるので覚悟していたが、最後までコンテストに参加できてよかった。展開上、NoSub撤退になる心配が出ていたが、それも気にせずやりたい問題をやった。結果的にはC問題を提出できた。0完だけど、まあNoSub撤退よりは気分がいい(これも世間体を気にしたゴミみたいな感情だけど)(参加したのに成績表に載らないのはかなしいというのもある)。

A - Dividing a String

ここ「すべてのiについて」って書いてほしいなあ。「あるiについて」かもって思うじゃん。問題文を読むのに2分以上かかった。いくつかの例をいじってみるが、a aaa aみたいな分け方まである(これはaa a aaでも行けるとあとで気づいた)。隣り合う文字が同じときが問題なわけで、両側の文字が同じ境目を管理する?どうせKは|S|*2/3くらいにはなるだろうし。しばらくして、DPを思いつく。高々3文字っぽいし、最初のi文字で区切れて最後がk文字の最小を持つ。ただ、S_iが4文字あれば十分な証明すらできない(あまり時間をかけたくないので)。まあ2文字でいい気がするけど。妥協して証明なしの5文字でやるとして、DPの更新がかなりめんどくさい。さすがにそれはAGCじゃないよね?何か簡潔な解法があるはず(ないならやりたくない)。いつの間にか25分も経っていた。見限るのがちょっと遅い。BとCへ。

B - RGB Balls

RGBではなく012で考える。各1について02を探す。左右両側か、片側だけか。両側の場合両方効くが、片側の場合は遠いほうだけ影響する。いや最小を一つ求めるのでさえ大変なのに、(最小を求める必要があるかは知らんけど)その通り数だなんて最初から無理だと思ってた。10分くらいで切り上げてCへ。

C - Numbers on a Circle

BとCを1秒ずつ見た感じでこっちのが面白そうだと思い、まずCをやる。逆から考えたらどうかと思いついたが、そこから進展せず、10分ほどでBへ。

Bから戻ってきた。逆から考えて、減らせるときは減らす以外にその要素を変化させる方法がないことに気づいた。以降、Cをメインにやった(詰まったときにAやBを考えていた)。面倒なのでソースに書いた考察メモを転記する。

//逆操作を考えると隣2つの和を引いてもA以上でなければならない Aは1以上なので和より大きくないといけない
//引ける候補は多くとも1つおき
// 1 10^9 1 みたいなときは10^9/2回くらい必要になる
//a b c d となっていてbが減らせるとき、b>a+cなのでaやcはbが変化しないかぎり減らせない
//つまり、bが変化しなければならないなら現在のa,cで減らせるかぎり続ける必要がある Aに等しくなるか減らせなくなるまで 最小もくそもなくそうするしかない
//Aより大きくても、隣より小さくなればチャンスはある 隣が減らせるようにならないのにAに等しくならなかったらもうbは変化できないので-1
//減らせるやつをリストアップする a b c d e
//cより大きい間はbを減らし続ける必要があり、結局bは(Aに等しくなった場合を除き)cより小さくなる
//新たに減らせるようになるのは、減らしたやつの隣のみ これをO(N)回繰り返す時間はない
//減らしたa b cだけに注目するとb>a+cがb

最初は、最大でN/2個の更新ポイントを(隣り合ってないので)一気にやっていくことを考えていたが、よく考えるとBは常に更新しているのでそうなってない。ただ、減らせるものは減らす必要があるのでこれでも解けていると思った。提出するもWAとREが出る。REが一つでもあるとコンテスト中は実行時間が表示されないので困ると思った(更新回数は各要素についてO(log(B))で済むと結論は出していたものの)。REの原因は、Bを更新しながらだからN個を超える更新候補が出ることだと見当が付いた。やはりキューにすべきだったかーと思いキューに書き換えて提出。REはACになった模様。しかしけっこうな数のWAがそのまま残っている。絶対に正しいようにしか見えず(こうなったときってほんとバグが見つからない)、逆立ちしてソースを見たりしたいと思ったけどできないので、きれいに書きなおして最後記念提出して終わった。

(追記)関係ない悪夢をみていた気がするが、寝起きにふと気づいて出力のint r; をll r; にしたら通った。これは、-Wconversionとか付けてる場合じゃないなあ。出力が32bitに収まらないのは途中で気づいていたが、まだ解けてはいなかったのでそれどころじゃなくて最終的に忘れるやつ。ここまで「正しい」コードだと、コードの見た目ではバグを発見できないなあ。見た目に頼りすぎ。どうしたら防げるミスかわからない。

ABC137

どうなるんだと思ったけど、結局は実力通りの順位になる辺り新ABCはすごいね(まあ相当運はよかったと思う)。開始前30分前36.8、終了5分前36.9。ちょっと体調が悪かった(途中はもっと上がってたはずで、体温が上がったときにいつもと違って体がきつかった)。途中で邪魔が入ったりもしたが、そこで気分を壊すこともなく20秒のロスは本当に20秒のロスだけで済んでいた。「あとちょっとで黄色になれる」みたいなときにこんな落ち着いた立ち回りはできないわけで、黄色を経験できてよかったと思う(またなりたいけどな)。今回はいい動きができた。

A - +-x

問題を開くのに1分かかった。久しぶりだな。でも、それで意気消沈ということもなく淡々と解き進めていた。

max({ a + b, a - b, a * b })という書き方を覚えて定着してきた。

B - One Clue

K=1のときはそこだけで、Kが1増える毎に前後に伸びる。for (int i = -k + 1; i < k; i++)って書いたけど、i <= k - 1と書いたほうがきれいだったかな。" \n"[i == k - 1]が定型文なので引きずられて普段通りi < kと書いた感はある。

C - Green Bin

これ最近のCと比べるとかなり難しいね。30分前にトイレ行ったのにまたウンコしたくなって、トイレに立った瞬間解けた。各文字列はソートしちゃっていい。その後s全体をソートして同じ文字列が何個あるか数えればいい。それで解けてるけど、実装方針はけっこう迷う。10文字だから10byte必要、でも英小文字だけだから64bit整数に入るかも?結局は、char c[11]で受け取ってソートしてからarrayの配列に入れた。std::arrayは比較できるのでs全体のソートも簡単。あとは数えて(ここの実装けっこう大変なんだけどさすがに何回もやってるしできる)t * (t - 1) / 2 を足していくだけ。問題文のi < jとかに惑わされて、ぐしゃっとひとまとめにしていいのか一瞬迷った。

(短時間でACしてるtokuminiさんのソースを読んで)map思いつかない。いや個人的にmapは好みじゃないんだけど、最近は思いつけるようにはなってきたと、思ってたんだけどなあ。

D - Summer Vacation

「また何かでソートして貪欲かあ」と思いながら読み進める。M-1日後の日にできるバイトはA[i]=1のやつだけなんで、その中で一番報酬が大きいのを選んで損しない。つまり、Aでソートして、同じAの中で最大を選んでいけばいいと思った。が、これは勘違いで、1日後に報酬が得られるバイトはいつでもできるので、いつやればいいか判断できない!これはまずい流れだ。もう少し考えて、セグ木でM-j日目以降の最大報酬を求めれば行けそうだと思った。が、M-j日目がソート済み配列のどこにあたるかは二分探索とかになるし、解けるとはいってもかなり厄介。ここで、Dをやるのをやめた。こういうゴチャゴチャしたのは苦手だし楽しくない。EとFを見て面白そうなFへ。

シンプルな実装が存在するはずだ。Dでセグ木使うわけないというメタ読みもあるし、セグ木が本当に必要になるケースは少ないという経験則もある。今の自分にとっては複雑だが、そんなに複雑な問題には見えない。……priority_queueだ。落ち着いて実装。残り時間が少ない中、さっきまでと違う方針を落ち着いて書けたのはよかった。

E - Coins Respawn

自己辺もあるし相当めんどくさそう。最後に時間でコインの支払いが生じるとか無理でしょ。やっぱりFへ。

Fから戻ってきたが、ここで唐突に気づく。これベルマンフォードじゃん!制約も間に合いそう。唯一のひねりはT*Pの支払いだが、よく考えると各辺のコインがC[i]からC[i]-Pに変わっただけだ。正直言うと、ベルマンフォードがAtCoderで再び出題されるとは思っていなかった。ABC061のときにググって出てきたコードで理解しないままなんとかACとったのを思い出す。そのときのコードをコピペする。まだ競プロ歴が浅いときのコードなのでやや不安だがけっこうしっかり書いてある。そんなことよりそのコードを今回の問題にちゃんと適用する力が必要だ。幸い、少しの試行錯誤でサンプルが通った。頂点0から頂点N-1に行くコードだったし。関係ない場所のループを検出しちゃうのは当時WAを食らって大丈夫なはず(そういうループも検出する必要がある問題だったら困ってた)。提出してAC。これは運でしかない。解けたのでDへ。
(なお嘘解法だった)

F - Polynomial Construction

とりあえず、f(0)=b[0] とか x^(p-1)=1 (x!=0) とか書き出す。x*(x*(x+b[p-1])+b[p-2])+b[0] とかも書いてみるが、関係なさそう。単に行列として書いてみるときれいに書けるが、うーんさすがにO(N^2)では無理だよね。i^jの表を作ってそれをながめながら考えるが、無理。詰まったのでEを見てみる。

唯一面白そうなFに注力する方針だが、さすがに無理そうだという気持ちになってくる。解けると思って解き始めたが、身の程知らずだった。単なる力不足で仕方ないけど、その力不足が悔しい。Eへ。

ABC136

堅実な5完で200位以内。よし。Fは難しかったが、Eまでは数学系の面白い問題が多くて得意セットだった。終了後36.9。久しぶりにレーティング上がったー!珍しく0時前にブログも書き終えて、けっこう内容的にすっきりしていた。

A - Transfer

よく考えれば解き方はわかる。要するにどれだけ水を移せるかわかればよく、それはmax(C, A-B)だ。それを出力してもダメで、容器2に残る量を答えるんだった。複雑すぎて、解けたころには道のりを忘れている。

B - Uneven Numbers

じっくり考えた。1桁なのは1から9(0は含まない)、3桁なのは100から999。しかし、愚直より簡単になる気がしないので愚直へ。幸い、ここまでの時間で桁数の簡単な判定方法がわかっている(各iについて10^iを超えるならインクリメントしていく)。

C - Build Stairs

またこの典型か。左から考えていくと、低くして(それより右の人は)損しない。最初深読みして「マスの高さを 1 高くする」と言い換えてしまった。そのままでいい。

D - Gathering Children

RLの境目が1つ以上存在し、そこへ向かって落ちていく。左右対称なので、R側だけやればいい実装に変更。境目に向かって落ちていき、それが偶数個なら境目の前後へ均等に溜まり、奇数個なら「10^100が偶数なので」(←ここ面白い)Rがあった側が1個多くなる。reverseしてLも同様。最後の要素がRでないことも利用できたし、いい実装だった。

E - Max GCD

絶対に解けそうにない問題に見えるが、「0をたくさん作ればいいんじゃね」と思って考え進めたところで+1と-1がセットなことを思い出す。意外と制約がきつい。たとえば全体の和の偶奇は保存される。ていうか、何で割ったあまりも保存されるやん!?全体の和は正なので、最大値が存在しないこともありえない(とりあえず安心しとく)。全体の和は10^9にも達しないので約数を全列挙できる。あとは各約数についてK回以内で実現できるか。ここがむずい。いや、そこまで難しいわけでもないけど、考察の山場が何回も来るのが、十分な実力があるか試されているかのようだ。増やす側と減らす側に分けないといけない。なんとなく減らしたいのとかあるけど厳密にはわからない。まず、(約数をqとして)qで割ったあまりの和はqの倍数になる。逆から考えたり色々やったけど、結局思いついてた貪欲っぽいのでよかったんだよね。これけっこうきついというか面白い。あまりの和をqずつ減らしていくのを(あまりの和/q)回やると0になる。回数が決まってるなら、貪欲に回数が少なくなる(あまりが大きい)ほうから取っていけばいい。全ての約数に対してO(NlogN)の時間をかけることも可能。最大値を求めるのだが、約数を大きい順に列挙してもいいが単に条件を満たすやつのmaxを取ってもいい。min(a[i]%q, q-a[i]%q)とか書いてたのがそのままになっててサンプル合わなかったりした(道のりが長いからなあ)(考察が完了する前に実装すると生じる問題だが実装は考えの整理に有効なので悩ましい)。そこ以外はわりといい実装だった。

F - Enclosed Points

まず座標圧縮できる。x座標でソートすると各ペアの間に含まれる点はわかる。条件を分解する?いや、xでもyでも含まれてない個数がわからないのでダメ。長方形のパターン数はO(N^4)には収まるんよね。どの長方形も、2個から4個の決まった点に支えられてる。長方形が決まればカウントできそうだが、その長方形があるかも大変そうだし、そもそもO(N^2)も許されないからなあ。ずっと、個数がO(2^N)の和とかどうすりゃいいんだよってなってた。

夏アニメ土台部分

タイトルが苦しい。なんかたくさん見てるけど、「文句なしに1位」みたいなのが全然ない。それでも1位と最下位はわりとすぐ決まった。他はもう、どう並べてもよさそうで決めるのに苦労した。そもそもアニメには色々な要素があるのに一直線に並べる順位付けはどうなのというところではあるが、やはりこういうの好きなのでね。

手品先輩

気楽に見れるので。本渡楓のイメージがここたまのこころちゃんなので、こういうキャラで声を当てられるようになる気がしない。最初キービジュアルに男がいるの見えてなくて動揺したが慣れれば大丈夫。かわいいし、体の作画がわりと好み。あとタイトルがいいよね。

まちカドまぞく

初回のアバンがやけにゆっくりだなと思ってた。そしてOP。なんだこの雰囲気のある曲は。これはただごとじゃないと思って画面を凝視していたら桜井!これは1話の本編を見たあとで知りたかったなあ。まあ、大塚舞とかJ.C.STAFFとか、伏線となる情報はそれまでにもあったんだけど。1話は作画クオリティがすさまじかった。2話まで見ると、なんか物理少女の人が性格悪いように見えてきた。小原好美のほうは声に合ったキャラに見える。まあ内容についてはこれから。

女子高生の無駄づかい

これはキルミーベイベー度が高い。ここに来てまさかこんな声が聴けるとは!これが赤﨑千夏だ。あしが短い感じの作画もよい。戸松さんのおさげもかわいい、目もかわいい。3話微妙だったのでこれから内容がどうなるかというところ。ヤバい先生が、「荒ぶる季節の乙女どもよ。」の先生とまざる。

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

悠木碧かと思ったら河野ひより。今期たくさん出てるけどみんな違うタイプだ。デスマのポチは思い出せないけどそれっぽいな。内容はつらいのでずっとぷよぷよやりながら見てる。わりと密度がある感じなのはよい。ある程度の作画レベルを前提としたデザインに見えるので少し心配もある。あとスカートの長さがバラバラなのはいいね(ちょろい)。あー岡田麿里ねって感じだけど、こういうコケそうな話がどう転がるか楽しみではある。最終回とかどうするんだろうね。

異世界チート魔術師

今期めっちゃ出てる高橋李依。声質で、エミリアめぐみんめぐみんタイプの声が聴きたいと思っていたが、ここで。普通の女子高生でもこの声いけるじゃん。元の世界の知識を魔術に応用できるのが強い。ゼロ魔の戦闘機みたいで燃える(火だけに)。凛さん学校の制服とてもよいのだけど、もう着なくなっちゃうのかな。みんなが親切なのもよい。

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

1話はつまんなかったけど、その後はまあ面白い。神らの性格はともかく結果として大迷惑になってもほっとくしかない酷い世界なのは置いといてだ。3話最後のアイズのアドバイスぷよぷよの話として真剣に聞いていた(モンスターはCPU、あと動きが単純になるとか)。なんか赤﨑が仲間になる。リリの話は苦手。お酒を飲まされたら終わりだと思ってたら飲まされちゃって、どうすんのかと思ってたら普通に気持ちで何とかしてて呆れた(酔ったリリが完全にシャロだったの草)。酒場に洲崎西を配置するの好き。

ダンベル何キロ持てる?

黄色くてふわふわな髪がかわいい。先生は、「街雄さん」が「マリオさん」に聞こえる。食事や体をしっかり描いてるのが強い。ぽっと置いたようなタイトルから、この丸みのある内容にしてくるのは、さすが動画工房というところか。

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

1話の人だけが変態なのかと思ったら全員かい!まあこういうかわいい女の子がたくさん出てくるアニメは好き(そういうのばっかだろと思うかもしれないが、「かわいい」でまとまってるのかなり少ない)。で、こういうのに出てくる妹が好き。さて、2人目がSだったので、もうお前らでくっついて百合エンドでいいんじゃねという感じだ。

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

この河野ひよりもよい。けっこう声が豪華。浮いてるイチゴもなかなかいい。EDの最後の微妙な顔が癖になる。博多と思わせてそうでもない世界にいつの間にか引きずりこまれていた。

ソウナンですか?

遭難したまま話が進むやつだ。こういう狭いアニメもよい。登場人物の数で言えばキルミー並。色々できるのかっこいいよなー。「学校で学んだことは、この島では役に立たない」って台詞がすごく嫌だった。

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

すんませんみなみけのハルカみたいなイメージで聞いてたらかやのんだった。こういう声は逆に新鮮だ。最初、お母さんだけが異世界に行くのを想像していたが、子供も一緒だしそもそも異世界じゃなかった。親子で冒険するのは、話作るのキツそうだけどそれはまあいい。異世界じゃないじゃん!いやまあSAOとかもそうだけどさあ。でもこっちは、いわゆる「ゲームの世界に入りたい!」っていうゲームではないでしょ。お母さんはなんか知ってるみたいだし、かなりの緊張感がある。異世界のワクワク感もない。とりあえずワイズとポータがかわいいのでよし。