DDCC2019予選

A - チップ・ストーリー　〜無色編〜

まあやるだけなのでfor文を書いて提出したが、B問題を読み始めようというときに「シフトで行けた！」と気づき、シフトを使えなかったことを悔いて20秒くらい過ぎた。

B - チップ・ストーリー　〜漆黒編〜

難しそうだ。そうはいってもBだからやるだけなのではとか思ったけど思いつかない。ABCじゃないね。とりあえず簡単そうなNが偶数のケースから。サンプルと手計算を合わせて傾向を見る。等差数列、になるわけない。2乗のオーダーだよボケてるな。2乗だけどN^2の定数倍ではない。図をよく見ると三角数だ。次に奇数。これは相当難しそう。サンプルに2つあるので、5まで手計算して傾向を見るがわからない。サンプルと図とにらめっこする。各マスの四隅が黒い正方形に含まれるかわかればよさそう。そして、中心からのマンハッタン距離（名前がチェビシェフ距離とどっちだかわからなかったので考えづらかった）が一定以下で判定できると気づいた。ということで方針転換。ここまでわかればやるだけなので頑張って書いた。最初に見えた方針を捨てることによる時間のロスが多い。なんともならないのかもしれないけど。

C - チップ・ストーリー　〜白銀編〜

難しそうだけどまあ400点なのでね。たとえばP_1がNだとQ_iは全部1でないといけない。ということで、最大値をN通り試す方針が浮かぶ。ただ、最大値がどう出現するかでかなりの場合分けというか難しい何かが生えそうで怖気づく。最大値じゃなくてもある数以下ならいいことにする？いや、PとQで影響しあうからなあ。しばらくして、端っこから決めていけばよさそうだと気づく。こんなには上手くいかないという感覚だったけど、これでできてしまうようだ。最大値が最初に出現する位置で場合分けする。一応計算量にも気を遣って、毎回全部は計算しないように。改めてソースを見ると計算量を10倍勘違いしてたな（気を遣う必要なかった）。今気づいたが、要らん処理を消して提出したつもりが、コピペの段階で更新せずに出してしまった。これで最低限の結果は残した（といつも安心しちゃうのがよくない）。

D - チップ・ストーリー　〜黄金編〜

定まるわけないじゃんと思うような問題設定。少しして、各桁の和というと3の倍数の判定があるなと。この問題の文脈でいうと9の倍数だ。B進法のとき、秘密の整数とa_Bがmod B-1で一致する。となると中国剰余定理。わからないので困る。これをきっかけに勉強できたらいいかなとか考え始める。Wikipediaを読んで「（素数p0,p1でやるとき）結局、解はp0*p1おきに現れるよな」と思い、この微かな希望を具現化する。30までにけっこうな数の素数があるので、素数だけで絞ってから10^12以下を全検できると思った（具体的な計算量は計算してない）。30未満の素数回だけループすれば解が見つかる保証があるはずなので、絞り込み（具体的には、最小の解といくつおきに解があるかの情報を更新していく）の計算量はかなり小さい。10^12に30とかかけてもオーバーフローにはまだ余裕があることを確認。入力を逆向きに受け取ってたりしてたが、直してサンプルが合ったので提出。AC！
全完。これは嬉しい。ブログを書く時間が余ったのが感激だ。

ABC113

解きづらかった。やたら重かったけど、最近ABCがかなり不遇なので心配だ（ていうかまだちょっと重いな22:30）。

A - Discount Fare

何が半額になるのか全然わからない。鉄道とバスで区別してるのか。Yは偶数という制約とも合致する。a,bを受け取ってa+bを返すテンプレを書いといたので/2を追加して提出。コーディングは最速パターンだが、読解に時間を取られる問題だったのが残念。

B - Palace

これに5分かかるのはまあ仕方がない。わかってみればやるだけなのだが、なかなか読めない。雑に読んでるとはいえ、プログラミングのためのカッチリした読解という側面は必須で、その点で読みにくかった。0.006はdoubleで甘えてしまった。この制約なら大丈夫だろう。

C - ID

これは力不足というか何というか。方針はすぐ見えたのだが、std::vectorを10^5個持つという「やりたくない」方針。経験上、それでTLEしないことはわかっているが、それなりに遅くなることもわかっている。そして、そんな気持ちの影響もあったのか、「市の番号の昇順に出力せよ」を「市の認識番号の昇順に出力せよ」に誤読。きれいに書けるのでAtCoderっぽいと思ってしまった。それで実装してサンプルが通らず誤読に気づく。この時点でテンションガン下がりである。
最初に見えたやりたくない方針にするか、実行速度にこだわるか、きれいに書ければどっちでもいいが、まあその辺りで心が揺れる。しばらくして、速度重視だと短時間できれいに書くのは無理だと判断。県毎にvectorを持ちYでソートして市番号で書き戻す。ソートを2種類すると実装が面倒になるので市番号ではstd::sortを使わなかった。実装に時間がかかって、自分はこんなパターンも知らないのかとがっかりした。知らないのでもうちょい考える必要がある。

D - Number of Amidakuji

やっとお楽しみの考察だ。AもBもCも本当に解きづらかった。これあみだくじを知らないと不利じゃないのとかいらん心配をしつつ。制約を見るとHもWも小さい。H*(W-1)の塗り方と考えて、市松模様、いや、タテは関係ないからヨコだけ隣り合わないようにすればいい。Kにたどり着くか関係なく通り数を求めるのもけっこうきつい。ただ、Wが小さいのでそこは全列挙すれば問題ないか。実際は1がKに行くようなやつだけ数える必要がある。あみだくじの知識が要求されるのかと心配になる。しばらくして、全体の通り数を求めるときのように1段ずつやっていけばいいのではと思い当たる。おお、これは面白い。幅は実質W-1だと思っていたが、W本あるので1がそこへ行く通り数はW個保持する必要がありややこしい。隣り合ってるかの判定は最初普通にやってたが、ビットで見てることを生かす方法を思いつき、危ない危ないと書き直す。!(~(k >> j) & 3)などというキモい表現になってウケる。実装には少し時間をかけてしまったが、ちゃんとしたコードが書けてよかった。

Tenka1 Programmer Contest

今回は順位表を見ながらやった。自分にとってはARCと同等のコンテストだけど、企業コンということで心理的ハードルが下がったところにつけこむ。見てもそこから下がる一方なので見たくないんだけど、なんとかして選択肢を増やしていきたい。実際に見る必要があることは少ないだろうけど、自分の動きを自由にしておく。
あと服。コンテスト前に36.7度と微妙な感じだった。寒くないように着ておいて、コンテスト中に体が熱くなってきたら脱ぐ、寒くなってきたら着るという、こう書くと当たり前みたいだけど、そういうのをきっちりやることで、持っている力がちゃんと出せた。面白い問題ばかりだったけど、それを面白いと感じることができた。

C - Align

まず、これの答えを自分が知らないことに驚く。いいところを突いてくる。第一感は、9,1,7,2,6,5みたいなの。だんだん振れ幅が小さくなっていくジグザグ。証明はできないし正しいかもわからないけど、とりあえずこれで書いてみる。違ってる可能性は高いけど、そんなに離れた答えにはならないと思うから書いて損にはならない。するとサンプルが通らない。親切だなと思ったが、今になって考えると、それも思い込みだったなと。さて400点なのだから確かにこんな簡単な答えではないはず。しかし、何も方針が思い浮かばない。順位表を見てもほとんど解かれてないし、めちゃくちゃ難しいのでは？
まあもう少し考えてみる。なぜサンプルが通らなかったのか、具体的に手計算する。すると、サンプル出力は中央値付近の値との差で稼いでいる。なるほど普通に間違ってた。これを1個ローテートするだけでもいいか？ジグザグの幅が大きい順に真ん中から左右に振り分けていくか。実装きつそうだな。しかも、証明ができてない。そもそも差の個数ってO(N^2)あるし隣り合わせにする制約もきついし見当がつかない。ちょっとCの得体が知れないので一旦Dへ行く。
戻ってきた。やはりそれ以外のやり方がより優れているとは思えない。真ん中から配置する実装重いのをやろうとしたが、思ったより重く、またループの1か所を除くイメージで中央値同士の差さえ避ければ全体の和は変わらないと思ったので、最初に書いたコードから1ローテートさせただけのものを提出した。もう時間が時間なのでね。なんとかAC。解説を聞くと、ちゃんと証明できる方法があった。端っこだけ寄与が少なくなるのは、これだけ考えて得た感覚とも一致する。まさかそんな原始的に思える方法が僕の意識の外にあるとは。

D - Crossing

すぐには意味がわからない。よく読むと、各部分集合のサイズはばらばらでいい。条件から空集合はありえないし、kは1以上となる。そのうえで条件を満たしていればいい。さて、1つ目の条件から、k個の部分集合のサイズの和は2Nになる。たとえばNが素数なら、サイズ2の部分集合がN個みたいなやつしかありえないようにも思える。なんかNが大きい数だとして、決まるところから決めてみよう。1,2,3、けっこう制約はきつそうだ。しかし4以上の配置は決まらない。そもそも構成ができない。N=4ができないならN=5でどうだ。星の絵を描き、どうもこれは無理そう。「どの2つの集合をとっても」という条件は、2つの選び方がO(N^2)と多いのでかなりきつい条件になっている。これはN>3では無理なんじゃないか？しかしそんな問題を出すだろうか。さすがにつまらなすぎる。もう少し考える。（もう当時の気持ちは忘れてしまったが）kがNなら絶対無理みたいな雰囲気の。で、証明できたと思った。証明できたなら、これは提出できる。「証明せずに提出したもの勝ち」ではなく「素早く証明できた人が先に提出できる問題」だ。んで提出してWA。
半分くらいWAだったので、構成できる大きいNがたくさんあることがわかる。これは大きなヒントだ。k(k-1)/2=Nならいける可能性があるじゃないか！そして、その場合は（部分集合同士を結ぶ）辺に1からNの番号を振れば構成できる。実装でやや迷うが、考えた通りで押してAC。解説を聞いて、kを先に決めてそこからどのようなNが作れるかという方向が、自分は思いつかなかったもの。きつい条件だと気づいたときの自分の気持ちからはずいぶん遠い場所だ。
証明してから提出するという方針であれを提出してしまったのがつらい。脳みそぐにゃぐにゃすぎて誰からも信用されない人間であることを見せつけられてしまった。

E - Equilateral

図を描いてみる。1つの点から出発して同じ距離を移動しながら戻ってくると考えると、全体の移動距離は2の倍数である必要がある。3点がグリッドに沿った長方形に乗っているとする。1点は角（かど）にある。長方形の周の長さが3の倍数である必要がある。それ以外にはないとして考察を進めた。解説を聞くと、3点をx座標順に並べた場合のy座標の変化で場合分けすると、それ以外ないとわかる。すごい。
角にある1点と残りの2点、どっちを基準に考えるか。1点から見ると残りの2点のパターンは多すぎて散らばりすぎてダメに思える。2点から見るのは（コインの数をNとして）O(N^2)かかるのでダメっぽ。なんかうまいこと重なるんじゃないかと色々考えたが。長方形を横に伸ばしたときの振る舞い。なんか2点が1とか2とか動く。縦にも伸ばさんといかんしまとめられる気がしない。
解説を聞くと、2点が45度の位置関係（雑な表現だな）にあるらしい。ああ、なぜそんな基本的なことに気づかなかった！長方形ぐるぐるのイメージから、更に踏み込んで具体的に考えるべきだったなあ。そういう距離が入ってるんだから円を描いてみろよとも思うが、それを思いつかずとも具体的な座標を計算することで45度に気づくほうが大事な気がする。やっても気づかない可能性が高いとは思うが。そして実装が自分の実力だときつそう。今からやってどれだけかかるだろう。ていうか計算量がO(max(H,W)^3)みたいな微妙なラインなので、いやそんな雰囲気は感じてたんだけど、見えないよなあ。ほんと作問者が天才すぎる。

AGC028

遅めに布団に入り、眠るタイミングを逃したら、体（というか頭）が思うように動かない悔しさが出てきてつらかった。起きても異様に気分が沈んでいてつらい。

A - Two Abbreviations

何を言っているのかさっぱりわからなかった。たぶん知ってれば読める。いつもの問題みたいに。なんでも知ってなきゃいけないんだなあと思った。読めたときには解けてるというか。それは言いすぎなんだけど。えっ、文字列地方へ旅行に行ったこともないんですか？みたいな人ばっか出てるのがAGC。
L/Nっていうのがね。L/Nは、Mみたいな雰囲気がある。Sの長さはNなのに。なんとなくあんな感じかなーってイメージは浮かぶけど、具体的な数値がはまらない。そこで、頑張ってN=4,M=6の例を書いた。しばらくして、LによらずSとTが重なる場所は固定だと気づく。これで解けた（基本的に最小公倍数が答えで、重なる場所で不一致があったら-1）が、実装を考えるのがそこそこ難しい。しゃくとりみたいなイメージ。まあ最近はそれもわりとすらすら書けるようになってたので、大きく詰まることもなくきれいに書ききることができた。
まさかこのときは1完早解き勝負になるとは思いもしないのだった。

BとC

Aを通したあとは、BとCを交互に考えていた。「いやこれ無理でしょ」と思ったら、別の問題を考える。その流れが効率いい感じがして気に入っている。両方解く前提ならそれがいいと思っているが、実際には片方しか解けない可能性が高いと思われ、微妙ではある。だが、コンテスト中に多くの問題に触れる価値は非常に高い。とにかく時間を捌くことを優先した。寒い日だったが、コンテスト中は体があったまり、それでいて前回のARCのように頭が熱すぎるということもなく、思い描いた試合運びができていた。しかし、「解けそう」というところまで行くことなく2時間が過ぎた。この、時間があっという間に過ぎる感覚は正直嫌いじゃない。でも、結果的に1完となるのは嫌いだ。
Bは、まずNが1小さい問題に帰着させることを考えたが、要素の追加で思ったより複雑に影響が出るのと、O(N^2)の雰囲気があったのでなかなか。色々な方向から見ようともした。各A_iについて何回足されるか、K回目の操作でどれだけ足されるか、N!通りのうちの一つで平均どれくらい足されるか、N!*N回の操作で云々。PCのキーボードのキーをブロックに見立てて考えていた。
Cは、A_xとB_yの差（の絶対値）のぶんだけ節約できるので、小さいのと大きいのをつなげたい。もう少し考えると、差の2乗とかじゃないので、大小関係だけが大事で、無理して一番小さいのと一番大きいのをつなぐ意味はない。閉路検出もちょっと思ったが、当然辺が多すぎる。何か（A-Bとか）でソートするやつだろうか。サイクルだからソートといってもなあ。とりあえずAでソートすることを考えても何も起こらない。サイクルはN!通りあるが（今考えるとサイクルだから(N-1)!通りだ）、それがどんな制約なのか想像できない。大小に分けて大と小をつなぐとして、大をいくつにするか個数が重要そうだから、何個までできるか二分探索する？O(N!)なわけないんだから、大きいのが何個なら可能とかわかるのでは？わからない。