AGC033

ぼんやりした回。D以降が解けない前提だと早解き回。あまり体温も上がらず。自分は3問遅解きした。ハマったりせず3完できたのが大きい。

A - Darker and Darker

逆に黒いマスから見れば、だんだん広がっていくやつ。解法は1分くらいでわかったが、実装に10分近くかかる。BFSはしっかりライブラリにしとかんとな（あまり使う機会もないし解く速度が要求されることも少ないからライブラリにしづらい）。今気づいたが実行時間制限1秒か。

B - LRUD Game

問題の性質を地道に書きだしていく。そして、縦と横のゲームがあり、高橋君はその片方に勝てばいいと気づいた。左右のゲームだとして、左に脱出するゲームなら簡単だ。しかし、左ばかり気にして右に逃げられたりするからややこしい。後ろから見ていくアイデアはあったが、まとめて最後の何個かを累積和で見るとか、最終手はわかるがその前は？とか色々あるのでまとまらない。解ける気がしない。後ろから見るのと順方向に見るのの本質的な違いもわからない。結局、色々やった挙句、青木君が勝つ範囲を後ろから更新していけることに気づいた。

C - Removing Coins

誤読してて問題を読むのに苦労したが、サンプルの様子を見てシュッとコインが吸い込まれるのを思い浮かべそのイメージで読んだらわかった。だんだんグラフが小さくなっていく。頂点に複数のコインがあっても関係ない。まず、減る頂点数に注目した。ただ、木の様子が指し手によって全然変わってくるので何もできそうにない。とりあえずもう少し性質を調べると、選んだ頂点を根として見たときの葉ノードが消えるんだ。つまり、葉ノードを選ばなかったときはどこを選んでも同じことになる。葉ノードを選ぶとそこを残せる。解き始めのころ「グラフ 木 重心 中心」でググっていたのだが、それと併せて「直径」が浮かぶ。この操作で木の直径は1か2小さくなる（0や3以上はないという意味）。葉以外を選べば直径の両端が消えるので2小さくなるし、直径の端であるような葉を選べばもう片方の端が消えるので1小さくなる。直径が1以下の葉しかないケースは簡単なので場合分けすればいい。直径一発で行けるこの問題ヤバいし、直径を思いついた自分もヤバい。ほんとにそんな保存される性質あるのと疑ったけど、確認すると確かにそうなっている。不思議。

D - Complexity

色々やったけどできなかった。残り10分のとき「あと10分で1000点が解けるわけない」と時間を無駄にしてしまうのが何とかならんかなあ。実行時間制限とメモリ制限を見て、4乗DPみたいのがあってそれは通さないということなんだろうなあと思ったが。それを定数倍高速化していけないかなとか。1次元の場合を解いて、それを含むようないい感じの2次元を。境界線の数とか。DPはあまり考えたくなかったが、それ以外が無理なのでわりとDPばかり考えてた。市松模様でもけっこう小さい「複雑さ」で済むので（1byteに収まって）省メモリできるけど、そもそも4乗DPもわからんしなあ。

WCSC1日目に行ってきた2

対局開始くらいに着くのをターゲットに出発。対局前のピリピリした空気のところに行くのも気が引けるので。乗り換えに成功し1本早い電車で着く。まず会費を払うが、開始前のクソ忙しそうなときに小谷先生が出てくる。対局はコンピュータがやるから大丈夫だって。去年会費を納めたつもりなのに4000（2年分）と書いてあって気に病んでいたが、そのことを言うと確認してくれて4000というのは間違いだった（そんなことある！？）。ちょうど対局開始くらいに中へ入ることになってちょうどよかった。去年は会場が寒かったので上着を着ていったが、今年は冷房が効いてないので不要だった（会場では脱いでいた）。

放送してるのでカツ丼さんと気軽に話せないなーと思った（あとで普通に話した）。Miacisさんに、ニューラルネットワークについてしこたま教えてもらった。なんか返せない恩という感じ。本当に世界は広く、なるほどと思える手法が無限に出てくる。CGPは、やねうら王と水匠に負けはしたが、勝った対局はいい内容で、傍から見ているぶんには当然の予選突破だった（本人は胃が痛そうにしていてヤバかった）。きふわらべのとこでは、今回やるはずでできなかった手法についてしつこく聞いてきた。現在の局面から指せる手順を、過去に指された棋譜から検索する（詳しくは略）。僕はきふわらべの手法をあまりいいと思ったことがなかったが、これは面白いと思った。さて、僕は最近選手権に参加してないけど、それで毎年遊びに行くのさすがにそろそろ申し訳なくなってきた。話してくれるのほんとありがたくて、感謝の気持ちが出てくるのは幸せな人だから感謝してる人はべつにえらくないよ（？）。

終了後、夕食を4人で。フードコート行ったけど久しぶりにコミュ力のなさを感じた（最近はだいぶ高いと思っていたけど穴がある）。こういう、おんぶにだっこできるメンバーなら問題ない（は？）（まあ、プログラミングできたほうがいいのでコミュ力は（どうでも）いいです）。Claireさんとは久しぶりで話したかったんでよかったー。あやめはいい名前だけど呼び方として慣れてないのではい。文章が適当になってきたな？

あ、今年は、行きの電車では3DSでぷよぷよを、帰りの電車ではノートPCでこのブログの下書きみたいのをしてた（軽いのでそのために持ってった）。3DSのすれちがい通信も2件あってよかった。

ABC125

そんな感じはしなかったけど終了後37.0（今は下がってる）。始まる前は、ABCなのに緊張するなあウンコしたくなるなあと思っていた（ウンコが直前に来るのが困る（結局はしてない））。もうちょっとスピード出したかったというのはあって悔しいが、ノンペナ全完はいいものだ。

A - Biscuit Generator

Aにしてはかなり難しそう。どうせ小さい数だろうし、全探索でゴリ押すことも考えたが、きっちり考察して書いた。まず、最後にBを掛ければいいことがわかる。次に、TがAのときを考えると、ちょうどビスケットができたところだ。つまり、T/A（あまりは切り捨て）で生産回数がわかる。

B - Resale

これはやるだけ。VとCが同時に得られないのが面倒だ（考察が済んでいるので面倒だとわかる）。Vだけ配列に入れておいてmax(V_i-C_i, 0)を足していく。

C - GCD on Blackboard

少し考えてわからなかったので、D問題と並列でやることにした。C問題でこの悩み方は既視感がある。頭が固いのだ。Dが簡単そうだったので、DをACしてから戻ってきた。

まず状況をしっかり認識する。0に書き換えることができないのは確認していたが、0に書き換えるとしてよい（自分以外の最大公約数と同じ数に書き換えれば0にしたのと同じになる）。gcdをとっていくとどんどん因数が減っていくのでネックになってる1つを除けばいい（0とgcdをとっても変わらないので除くのと同じ）（ただ、この考え方だと、残った因数たちの積の最大化が難しいと思った）。全体を半分に分けることを考える。それぞれの最大公約数の大きいほうが上限になる。ただ、何も起こらない（解けない）。そもそも、半分に分けて解けるなら、1個とN-1個に分けても解けそうなものだ。それで考えよう。A_1を書き換えるかどうかで場合分けする。書き換える場合は簡単（A_1を0にするだけ）。書き換えない場合、これ問題のサイズが1小さくなってるね！

A_2からA_NのN-1個の中から1個を書き換えるのだから、Nが1小さい問題に帰着できた。これは累積和的に左右からi個の整数の最大公約数を持っておけば問題が解ける。要するに切断の場所をN通り試せばいい（順番は関係ない問題なのに不思議な感じ）。解けた。この時点で開始17分くらいだった（文章にすると長いがけっこうスムーズに解けてる）。20分切りも見える。しかし、実装が大変だった。境界がちょっと注意を必要とする程度でそんなに難しいわけではないが、なぜかこれは書き慣れてない。実行時間の最適化ができない。しなくていいのだが、自分の場合それができないということは、処理内容に慣れてないということだ。実行時間ではなく、見慣れぬ景色が問題なのだ。コードも汚くなる。何をすればいいかはわかっているのに（後から考えてもわかっていたのに）、ものすごくしんどい思いをして実装を進めている。やはり累積和と同じでN+1要素のvectorを使うのが考えやすい。最初のi個の最大公約数を保持（最初の要素は0）。反対側は、最後の要素が0になるように。+1の必然性がよくわからないまま、正しさだけは保証する思考（保証といいつつこれは（見るからにそうだと思うが）よく漏れる）で提出。

あ、答えが0のとき10^9を出力するの忘れた！と今思ったけど、制約を見直すとN>=2だった。サンプル3がN=1だと思い込んでいた。やっぱり親切だ。

D - Flipping Signs

これは見るからに簡単そう。-1倍できるのは偶数個っぽいと思い考えると、実際そうだ（一回に2個を反転させる）。そして偶数個であれば好きな場所にできそう。端から決めていって、自由にできないのは最後の1個だけ。その最後はパリティチェックみたいになってるから偶数個であれば合うはず。これは配列を用意する必要がない。唯一負の数のまま残るものをmaxとっておいて全体の合計から2倍を引けばいい。0の扱いは少し迷ったが、負の数としてカウントするのがよさそう。0があれば自由になる（-1倍してもしなくてもいいので）。

雑に書いてサンプルで様子を見るのだが、サンプル2が通らない。合計は（紙で計算して）36。そこから3の2倍を引いて30に見えるがなぜそう出力していない？引くんじゃなくて負の数を絶対値とったぶん補正するんだから足すんだよ（中学生か！）。それでも合わない。あー、単に絶対値最小のものをあぶれさせるんだよ（気づいてなかったのか！？（コンテスト中の理解はこんなもんで、全くわかってないわけでもない））。カウントするのは0含めてもどっちでもいいが、とにかく全体の合計と絶対値の最小を求めて、カウントが奇数なら今度こそ2倍を引く。やはりサンプルが超親切だった。

TENKA1-2019

体調がやや不安だったが、特に問題なし。1完に終わったが、座ってるだけではなくDとEを考えることができた。しかし100分ではWAを投げるところまでも行かない。なんか今後2000未満ratedの6問コンテストができるらしいが、ratedでABCのABを解くとしたら嫌だなあ。企業コンでたまにあるけど、うっかりミスでペナ食らったら理不尽すぎる。もちろん、1完でレートが付くのも嫌なので嬉しい変更ではある。

最近コンテスト中にトイレ行くことが多い気がして、コンテスト前に水を飲まないようにしてみた。微妙な策だとは思っていたが。開始直前には緊張で少し出たくなる部分もあった。結局、開始1時間くらいでトイレは行った。我慢はできたが、解ける気がしないので気分転換のような感じで。ちゃんと出た。夕食も控えめにはしてた。

C - Stones

「黒い石のすぐ右に白い石があっ」てはならない。ということは、黒い石がなければOKだし、白い石がなくてもOK。図を描くと、二分探索が使えるための条件と同じだと気づいた（概念を最初から持っているのは強い）。少し考えて区間の黒の個数が累積和で出せればいいとなる。あとは実装だが、ここまで必要なのかなあと思いながら累積和を書きN+1回最小値を取る。思いついた方針に固執することでスピードを出すかよりすっきりした解法を考えるかで大して迷わず前者を選んだ。時間がかかったのはn - i - (a[n] - a[i])のところ。後半部分の白石の数を求めるので全てが逆になってこんがらがる。i個とn-i個に分けているという意識があるとよかった。少し見直して提出。ジャッジが始まるまでに時間がかかったがなんとかACしてた。

D - Three Colors

三角不等式、Rが最大として一般性を失わないか？いや、1色で半分以上取ったらダメで、そうでないならOKということか。合計が大きい順に取るのは、正三角形とかのケースを考えても難しそう。そもそも全体の和が高々9万なのでDPができる（気づくのが遅い）。最終的に、最大の色が半分未満ならOKなので、そのように3つに分ける通り数（575）をDPで求めて6倍すればいい？と、そのDPの更新を考えていたら、三角形の条件がないなら3^Nが答えなことに気づいた（気づくのが遅い）。半分未満の和は大きいようで小さくもなるので3色の中で最大とは言えない。色をそのように固定するやり方とは限らないが、制限が大きく考えづらい。そこで、和が半分以上になる通り数を求めて3^Nから引けばいいのではと思いつく。0になる色が出るケースとかはかなり面倒そうだができそうではある。ただ、DPができない。最初のi個で和がkになる通り数は求まってる。しかし、最初のi個の中からj個を使って和がkになる通り数は300^4になってさすがに無理。残りを2色に分ける通り数が使った個数に依存してるのがきつい。色々考えたがどうやってもDPできない。

E - Polynomial Divisors

DとEを読んで絶対こっちのが面白いと思ったが、20分くらい投入しても先が見えないし、解いてる人も少なくて及び腰になる。

全部の係数の最大公約数を素因数分解して、それは使える。あとは、x(x-1)(x-2)みたいに因数分解できたら3の倍数になる。(x^2+2)とかもxを3で割ったあまりが1,2のときは3の倍数になる。まあNが微妙に小さいし因数分解とかはせずO(N)の確認を何千回かするという程度なんだろう。xに0を入れると、a_0が残るんで候補の素数は簡単に絞れる。10^9以下だから大した個数じゃないしxに1からNまで入れて調べれば十分な気もするが。ただ、それで行けたとしてもa_0=0のケースがある。x^c（cは正の整数）でくくったとして、x(x-1)(x-2)のような影響はあるのでやはり難しい。そもそも、答えが10^9超えることなさそうじゃない？N以下の素数を候補として全部チェックすればいいのでは。チェック方法がわからないけど、x=10^9+7として割り切れるか調べるだけでよかったりしない？f(x)の計算は、a_Nからスタートして、x倍してa_(N-1)を足す、x倍してa_(N-2)を足す、というのを繰り返せばよい。f(x)が巨大な数になるというのも困るが、1つの素数についてだけチェックするなら、mod pで計算するだけ。残り30分しかないしDもEも解ける気しないし、これで実装して終わりにするかと残り時間を見たら残り10分で草ァ！ただのARCだった。100分でこのセットはきついよ。