ABC116

こどふぉがあって参加者が少なかったらしい。

A - Right Triangle

どれか2つを掛けて2で割ればいい。斜辺が2の二等辺三角形みたいなのを一瞬考えたが、入力は整数なので関係ない。どの2つかを図で確認したが、サンプル1で3*4/2=6を確認してもよかった。最初の2つを使えばいい。残りのサンプルは読まずに、サンプルが合ったので提出。

B - Collatz Problem

わりと見た瞬間解法がわかるのだが、やはりこういう問題は慣れないので細部を詰めるのに時間がかかる。都合のいい制約になっていることは推測できるが、それをちゃんと確認しないといけない。m>nが直観に反していて、サンプルが合わなかったときに時間を食った。

C - Grand Garden

できるだけ広く取っていけばいいという予想はすぐにできる。Nとhが小さいので何も工夫せずに通りそうだ。しかし証明ができない。実装も地味にめんどい。その両方を同時に解決する何かがあるんじゃないかとしばらく考えたが、できなかった。時間が過ぎていくので実装する。無限ループっぽいのは、削り切ったときにループを抜けてなかった(ループを抜ける方法がないコードだった)。そしてサンプルが合ったので提出。結局証明せずにACを取ってしまった。

D - Various Sushi

種類数で二分探索を思いついたが、できない。逆においしさでとか色々考えたができない。かなり考えても解けないので、けっこうな状況だと気づく。1個ずつ貪欲に取っていくのが成立してるんじゃないかと予想を立てる。C問題と同じような感じで未証明実装しようとするが、priority_queueを使っても種類数の変化に対応できないことに実装して初めて気づく。むっず!貪欲からの連想で、最初においしさだけで貪欲に取り、その後入れ替えていくのは?これは正しい解法っぽい!使っていない種類のものは、1個しか取る意味がない(既に選んだものよりおいしさが小さいものしかないから)。つまり、使ってない種類それぞれの一番おいしいものをおいしい順に並べておけばいい。順に、現在の種類数*2+1を2ずつ増やしていったものを足しておく。それによって満足ポイントへの寄与が順番通りにならなくなるが、おいしい順に並べるのが最善なのでそれでいい。もう片方の入れ替え対象は、おいしさが小さい順だけど、種類数を減らすことがないように注意が必要だった。単独で残ってる種類や、おいしさが同じで運よく残っただけのものがあっても、自分よりおいしいものと入れ替えることはないのだから大丈夫そう。実装。ここで、1個入れ替えて満足ポイントが減っても、2個入れ替えて増えることがありそうだと気づく。ヤバそうだが、順に求めていって最大値を更新していくだけだと気づく。さらに実装。多少のバグは出したが、この複雑な処理を書き切ったのはすごい。

DDCC2019本戦

良い環境で挑むことができ素晴らしいコンテスト体験だった(結果が出たからそう思うだけかもしれないけど)。

A - レース (Race)

読むのにかなり時間がかかる問題。意味がわかれば簡単で、氷をできるだけ長くするだけ。長いのを長くしたほうが効用がでかい。雪が連続する制約なのは氷が結合しないようにしてくれてるのだ。両端もわかりやすくなってる、ことには気づかずコードを書いて、考えに詰まったとき制約の意図に気づく。読んだけど忘れてるんよ。問題文を何度も読んで経験値を溜め意図がわかったところで書き始めるから。計算量は気にせず、ソートで。サンプルで気づいたコーナーケースも汚く対応。

B - 大吉数列 (Array of Fortune)

転倒数みたいな?K以上大きいやつが左に何個あるか(これを表す数式がなかなか読めなくてなあ)。組の個数が最大になるケースを考えてみる。数を大きい順に並べて、5 4 3 2 1。K=2として、1の上に小さく3 4 5と書く。2の上には4 5と書く。3の上に5。3+2+1の三角形。それより大きければ実現できないとわかる。それ以下なら必ずできると予想し、実際できそうだ。どっちかから見ていけば貪欲が行けそうと思い、大きい順に挿入していけばいいと気づく。最終的な組の数だけでなく、各A_jに対する組の数まで指定できるのか!?そんな都合のいいことあるかと不安になるが、できるようだ。あとはオーダーを下げるだけだが(未だに解けてないのだが)、他の問題を考えることを優先し、部分点をさっさと取る。

D - DISCO!

これは、思い出せないけど最近見たやつだ(このブログを「累積和」で検索すると、k-DMCだった)。典型だから点数下がったのか?(直前に900点→700点と変更された)他の問題も一応読むが、この問題が狙い目と見て深く考える。2^32は、uint32_tで計算するだけなので楽。ただ、記憶にある累積和は段数が少なかったが、これは5文字もある。とはいえ強い人は瞬殺なんだろうなあ(順位表を見ると早い時間にDが解かれている)。しばらく考えて、向きを決める(詳しくは忘れたが、たぶん後述する「まとめて見れるやつ」が前に来るか後に来るかで前のほうが引き算要らなくて楽)。Dの個数の累積和を持ち、Iがある場所についてDの累積和を足してく累積和を持ち、以下同様。Oの累積和で、その区間で終わるDISCOの個数がわかるようになる。あとはそこから、その区間で始まらないDISCOの個数を引くだけ。区間のOの個数*区間より前のDISCの数でいいか?それはさすがにない。区間のCの数*区間より前のDISの数も引かないと。そういうのをやってもサンプルが合わない。かなり試行錯誤した(ちゃんと考えろ)。正解と比べて多いのも少ないのもあるので根本的におかしい。

時間制限が13秒というのを見てギョッとする。あー、ひょっとして累積和は(文字数5をkとして)k個じゃなくてk*k個要るのか?正確にはk*(k+1)/2個ね。区間のOの個数*区間より前のDISCの数、これはいい。区間のCの数じゃなくてOから見たCの延べ個数だ!それをループでk-1回引き算してサンプルがなんと通ったので提出。普通にWA。何が違う。いつの間にか符号付き乗算されてたんじゃないかとは疑った(違った)。いや確かに違う。Cの延べ個数の時点で区間より前にあるCもカウントしてる。区間より前のDISの数とかは大丈夫。そもそもこの問題、区間が全体であれば簡単。[0, r)という区間でも同様というか、累積和にそのまま答えが入ってるから簡単。問題は区間のCやSやIの数。ただ、よく見ると1文字短い問題に帰着されている(区間のCOの数とか)。なので、全パターンの累積和さえ持っていれば最悪再帰でできるんじゃないかと思った。結局そのように書いた。ググってラムダ式再帰。混乱してバグに苦しみつつ(実際はワンチャン通れと色々試行錯誤してる)なんとかAC。再帰はすごいね。なんで解けるのかよくわからなかったが、とにかく小さい問題に帰着できて一番小さい問題が単なる累積和で解けるとわかっているから、解けることもわかるのだ。わからないのにわかる。

KEYENCE Programming Contest 2019

A - Beginning

ソートして1479になるか。簡単でも複雑だと時間かかるね。

B - KEYENCE String

これ実装が難しい。

C - Exam and Wizard

状況は単純。大きいのから小さいのに移すだけ。何かを経由して移す意味はないので、ピッタリのやつはそのまま、小さいやつは必ず変更される、問題は大きいやつだ。AとBはその差だけが重要なので、A-=Bとしておく。変更する個数を最小化したいので大きい順に取っていく。

ここまで順調に解けている。昨日と同じだなと思う。現状の順位は昨日より低いだろうけど。

D - Double Landscape

A,Bはソートしていい。つまり、大きい順に並んでるケースだとしても答えは同じ。Aを順に見ていく。K=N*Mとして、A[0]はKでなければならない。A[1]がK-1なら、K-1はその行のどこかにある。B[1]がK-1ならそこで確定。そうでないなら、その列より左にある。A[1]がK-3なら、K-3はその行だが、K-1とK-2はより上の行。A[1]がK-1なら確定だし、K-4とかだったらより左の列とわかる。こんな感じで、各数毎にありえる範囲が決まり、範囲の小さい順に見ていくことができれば、単に掛け算していくだけで解ける。ただ、1次元の場合はそれでいいとして、条件がA,Bの2つあるのでつらい。そもそも状況が複雑すぎて、昨日と同じで書き切れる気がしない。何か上手いまとめ方があるのかもしれないが。

ちょっと視点を変える。必要条件をたくさん集めればいつの間にか必要十分条件になっていたりしないだろうか。各数について範囲を考えると、大きい数から順に見ていけば関係するA,Bの位置は(広義)単調増加だ!まあ、確定しちゃうこともあるので、それでいいかは別だが、必要条件的ではある(あとで気づいたが、答えはそれ以下だとわかる)。隣の行との差も1以上M以下でないといけない。と思ったらサンプルがおかしいのでよく見ると、べつにM以下でなくてもいい(端っこだけ小さい数だけになってるとか普通にある)。その条件を外すとサンプルが通った。残り時間もないし提出してみる。WA。しかし、その結果を受けてコードを見直すと、どうも正しいコードであるように思えてくる。WAという結果を見たあとなのに、WAじゃないという空気が漂っている。そう思って見ると、変数名を直し忘れているのが2か所も。直して提出するとACだった。これは解けたと言えるのか(言えなさそう)。

E - Connecting Cities

要するに木を構築すればいい。順に最小値を更新していけば全てのノードについて最小コストの相手がO(N)で求まるし、自分より番号が若いノードを親として貪欲に張ればいいだけでは?実装して気づいたが、0番がルートと決まってるわけじゃなかった。酷い。酷いけど、この短時間で考えるなら普通にあることだ。コンテスト中に30分くらいで解くには、そういう勘違いをしないくらいの圧倒的な実力が必要なのだ。さて、最小全域木じゃんと今ごろ気づく。なんかコストの低い順に貪欲でよかったりしないかなと少し考えていたが、それってまさにクラスカル法じゃん。ただ、その方針で考えても、どうにも解けない。

AISing Programming Contest 2019

A - Bulletin Board

よく読めば問題の趣旨は推測できる。しかし、本当にそう書いてあるという確信はもっとよく読まないと得られない。例えば、自分がこの問題文を、厳密性を損なわず書くのは難しい。現実問題として、小考で投げてAC。

B - Contests

一見して、ABCのBとは違う。しかし、よく読むと問題のクラスを3つに分けて1個ずつ使うってことだから、カウントして最小値。最初、maxと書いてサンプルが合わなかった。熱っぽかったので、こういうブレはある。ただ、頭はちゃんと動いていて、淡々とそれなりの速度で解くことはできていた(ので少し安心した)。

C - Alternating Path

サンプルで問題の意味を確認。次に図を描く。長い黒白黒白黒白という並びを作ってみると、そこに現れたマス同士は白黒ステップで行き来できることに気づく。行き来できるやつ同値類でまとめられるじゃん!市松模様の範囲がわかればいい。そこで、市松模様をベタヌリに変えるためにi+jが奇数のところを白黒反転させる。そしてライブラリの塗りつぶしを貼る。塗りつぶした面積ではなく、白黒それぞれの個数が必要だったと気づき処理を加えて、オーバフローにも気をつけて書く。AC。早期に人権を得たのであとはDEを楽しむだけ。

D - Nearest Card Game

死にました。

高橋くんはまず最大のカードを取り、大きい順に取っていくが、初めて青木くんが取ったカードに当たったときのことを考える。この位置がわかれば、青木くんはその時点で、その位置で終わる連続した区間を取っているし、高橋くんはその位置の次から全部と、青木くんが取った区間の最初の位置の前から1つ飛ばしのカードを取っていくだけなので、累積和(普通のと奇数番目だけの累積和)で求まる。位置は二分探索で求まりそうだ。区間としてValid(脳内でこの言葉を使っていたがここで使うのが妥当かはわからないし発音も間違っている)か判定して、Validであればそれしかないとしていいよな。ただ、Validなのは点なので、二分探索するにはiが大きくなるほど成り立つような片側の条件にすればいい?条件がどっち向きなのかが複雑。x >= a[n - 2]のケースは分岐で処理。サンプルが通らず、高橋くんと青木くんがk個ずつ連続する区間を取ったとき、青木くんの区間がValidでなくてもいいことに気づく。高橋くんが押し寄せてるから最後だけ反対側に行くしかない。そのとき条件はorでいいのか?そもそも、xがうんと小さいときとかどうなんだ。そうじゃなくても、xの左側だけたくさん取ってるケースもあるがそれは。xに一番近いカードをいきなり高橋くんに取られた場合は?そういったケースを一つ一つ処理するのは人間には不可能に思える。視点を変えればまとめて解決できるかもしれないが、思いつかない。非常に苦手な展開だ。orやandや否定を全部試すが通らない。もう思考したくないしできないししていない。高橋くんが先に取るから2個前を考える必要がある?青木くんの区間は2通りのうち片方が行けるならOK?色々がアイデアが採用されてたまに否定されてなぜ正しいと思ったかわからなくなったりいやそっちが間違いだと思ったり。解ける問題だとはかなり早い段階で思っているので、それ以上の楽しみがない。進めない。何も見えないから苦しい。自分はなぜこんな苦しい思いをしているのかわからない。