⊼ は結合法則を満たさない」。だから右側からの累積和を使って左側から数え上げていくことはできない。できない？ 昨日は左側からの累積和をどうにかしてうまく数えられないかと四苦八苦していたが、成果なし。一日経ってあらためて NAND について解釈してみた。右側から０を作用させるとき、左の値によらず１になる。右側から１を作用させるとき、左の値が反転する。右側から０を作用させたときに無条件に値が決まるから結合法則が成り立たなくなったりするんだろうか。ありがたくない性質。だけど f(i,j) を考えるとき、i と j のあいだに 0 があるなら i の値によらず f の値が決まるということでもある。i から j に向かって値を作用させていくとき、０の位置で f 値が１に固定されるわけなので、以降は共通。■提出 #43667957 (AC / 450 Byte / 528 ms)。コメントに書いたけど、0 の位置をまず調べて、その隣接する位置を i<j とするとき、「f(,i)=1 として f(,k) (i<=k<j) の和」「それの累積和」を考えた。できないと思ったけど結局右側からの累積和で解いている。現在の位置より右にある最初の０以降を範囲の右端とする f の値は累積和を引いてわかる。最初の０までにある１の連続を右端とする f の値は 01010... か 10101... のどちらかなのでこれもすぐにわかる。■昨日は考えずにテキトーに累積和というのか４つの値を記録する DP というのかをがちゃがちゃしていたのがまずかったな。いや違う。考えてはいた。袋小路だっただけで。Ruby によるすべての提出を見ると、自分のは長いし遅いし、かなり回りくどいことをしているみたい。えっっっ？■F 問題「Make 10 Again」は正解方針が引けなかったな。「確率とか期待値の問題って方針を決めるところに難しさがある。正解方針が引ければ答えが合うけど、答えにたどりつけない方針を引いてしまいがち。当てもんをやっている」。D 問題「Peaceful Teams」を踏まえて和が 10 になる組み合わせを全部列挙していいのかと思ったけど、包除がうまく扱えなかった。和が 10 になるまでの DP もやったけど合わない。たぶんだけど「～が存在する」確率を尋ねてはいけないのではないかと思う。解けないから。作問者は反省してほしい。■D 問題までも書いておこうね。自分のすべての提出。AC までに使った時間が A=１分半、B=７分半、C=３分、D=29分。以下ふりかえり。■A 問題「Order Something Else」。候補は２つ。定価もしくは余計なものを買って割引価格。■B 問題「Strictly Superior」。価格とスペックの比較。価格で負けていなくて機能で勝っているか、機能で負けていなくて価格で買っているか。100 ビットのビット演算でやったけど、機能の比較が間違いやすそうですごく緊張した。
f1==f1&f2 とか f2==f2&f1 とか、いかにも取り違えそう。幸いペナルティは免れた。■C 問題「Reversible」。順逆を区別しない文字列の同一性判定。辞書順で先か後かどちらかを順逆の代表にすると決めて Hash に突っ込むだけ。■D 問題「Peaceful Teams」。これが時間内に解けた最後の問題。制約が 10 以下と小さいけど、さすがに T(=10) の N(=10) 乗は許されない。どうやってチームを作ろうか。最初は仕切りを使って T チームの人数配分を決めた後で N 人の順列を当てはめようとした。たとえば N=４人、T=３チームのとき、チームへの人数配分が 2-1-1 の場合を考えると、そこに配置する人の並びが 12-3-4、12-4-3、13-2-4、13-4-2 などになる。だけど重複がありますね。２人チームに人１と人２を割り当てる場合と人２と人１を割り当てる場合を区別してはいけない。まだある。２つある１人チームに人３と人４を割り当てる場合と人４と人３を割り当てる場合を区別してはいけない。同一人数のチームの並びと、同一チーム内での人の並びを区別しないようにサイズの階乗で割り算する必要がある。そうやって個々のケースに対応するなら場合の数を考える意味がない。相性問題への対処もわからない。もう手作業で個別具体的にチームを組んでいいんじゃないか。最終的に採用した方針がこう。T 個の空のチームを予め用意する。人１から順番に参加するチームを総当たりで試させる。そのときに相性を考慮する。N 人全員が行き先を決めたときに T チームすべてに人がいたならカウント１アップ。１つ１つ数えて間に合う制約なんです。相性チェックも総当たりで突き合わせて全然問題ない。処理の流れさえ決まればやることは愚直でいい。再帰関数を使った深さ優先探索で。これが T(=10) の N(=10) 乗でない理由は、部屋というのを構成メンバーで区別しているから。16 行目の「break if is.empty?」がポイント。空きチームが５個あるときに、５個ともに入ってみる必要はないよね。■■■E 問題。kotatsugame さんの動画を見ていました。「j を動かしながら今０のやつと１のやつの個数を求めておけばいいですね。」 あっはい(その通りですね)。(動画中断)。提出 #43692228 (AC / 144 Byte / 138 ms)。ちょー簡単だった！ 脳みそがお留守だったと言うほかない。
ruby27 -rprime -e "p (2**61-1).prime?" は全然返ってこないが 3.1 では数瞬で true が返る。左右に隣接しているか判定してください」という問題だったのに「
左右に」を読み落として上下に隣接している場合も Yes と答えてしまった。■B 問題「Rotate」。ABC305-C「Snuke the Cookie Picker」もそうだけど、図形的な操作を人間はひと目で認識できるけど、それをコードに落とし込むのは案外難しいという問題。がんばってやる。ペナルティの原因は１行目と最終行では移動の向きが左右逆だということがコードに反映されていなかった。自分の解答は Array#rotate とか Array#transpose を使うものになってるけど、i とか j とか i-1 とか i+1 とかが入り乱れると絶対に３か所は間違えるので、できるだけ添字を操作しない書き方をするようにしている。DP なんかでも添字を操作しないでいいように Enumerator#with_index とか Array#zip を使う。提出前に修正できたけど今日だって四隅付近で参照する要素を何度も間違えたし。■C 問題「Medicine」。答えは a+1 日目のどれかもしくは１日目。以上。■D 問題「Add One Edge」。入力されるグラフはちょうど２つの連結成分に分かれている。以上。■E 問題「Family and Insurance」。入力は木。この形式の入力を初めて見たのはこのとき>「制約の 1≤pv<v の解釈に一瞬詰まったけど、pv の上限が v であることで、逆向きにスキャンするだけで子から親へ順序よく処理できる親切設計だとわかった」。最近では ABC295-G「Minimum Reachable City」。有効な保険を親から子に伝播させていくか、子が親から引き継ぐかでちょっと迷ったけど、入力の形式から子が親を参照する方が素直に実装できる。その際に番号の昇順に処理することで親の処理が先で子の処理が後になることを保証できる。１代先まで有効な保険は２代に渡って有効な保険だという数字のずれに注意。もうひとつ。サンプルの１が親切だったのだけど、同じ人が複数の保険に加入していることがある。期間の短い保険で上書きしないように注意。■F 問題「Box in Box」。６ペナとバグり散らかした。方針はわりとすぐに決まって、まず入力される３つ組はソートする。縦横高さに３つ組以上の意味はないし、対角線を縦横高さにする問題でもない。３数を A≦B≦C として A の昇順に処理を進めるならあとは B1<B2、C1<C2 となる (B1,C1)、(B2,C2) を見つける問題になる。B を添字とするセグメント木に C の最小値を記録していけば見つけられる。複数の実装ミスを順番に潰していくことで WA×20→WA×11→WA×6→WA×5→WA×2 という経過をたどった。まずそんなにバグらせるなと、そしてバグ修正は律儀に１つずつやらなくてもいいんだと、言いたい。提出のたびに気持ちは G 問題へ移っていたのだけど、WA が出るたびに泣く泣くバグ修正のため F 問題に引き戻された。最初の提出にかけたのは 19 分でそのときに全体の形はできあがっていたのに、その後デバッグに 30 分かけている。G 問題を考えるどころではなく５完と６完の瀬戸際だった。■今日は冴えない日だったな。コンテスト成績表。自分のすべての提出(※要ログイン)。
Si と Sj をこの順に連結した文字列が回文となるようなものが存在するか判定してください。」という問題文の「
Si と Sj をこの順に連結」という文面から勝手に i<j であるかのような雰囲気を感じ取って勘違いしたのだろう。提出 #42900133 (AC)■C 問題「Ideal Sheet」。制約は大きくないから愚直に実装するだけ。その実装がたいへんだった。ビット列でやるとちょっとは楽になるんだけど、本当にちょっとだけ。これもペナルティをくらった。最初は動かせる範囲を総当たりする４重ループを書いていたのだけど、たとえばシート A がシート X の１行目をカバーしないとき、シート B は必ずシート X の１行目をカバーしないといけない。ということはカバーする範囲を１ずつ動かす総当たりではなく、シート X の四隅をカバーする総当たりでいいのではないかというケチな考えが忍び込んできた。これの罠はシート A と B の一方がシート X を完全にカバーするときで、そこまで想定していながら問題があると気付かずに提出して WA を出してしまった。原因に心当たりがあったのですぐに修正できたのが救い。AC まで 36 分(+ペナ５分)。■D 問題「Mismatched Parentheses」。対の括弧に囲まれた部分を省いて出力すればいい。括弧の中の文字列をスタックで管理するとして、括弧の外の文字列を特別扱いしなければいけない。同じようにスタックで扱えるかと考えてみたけどどうも良くなさそう。AC まで６分半。■E 問題「Distinct Adjacent」。前回の ABC306-D ほどあからさまではないけどこれも２値を記録する DP。人１が選んだ数字とそれ以外の数字をそれぞれ選ぶ場合の数を記録していく。人 N の時点で人１が選ばなかった数字を選ぶ場合の数が答え。AC まで９分。■ところで、E 問題に関して Ruby で一番最初の提出であり AC であるこちらの提出 #42909715 には(目に見える)ループがない。N が数えられないくらい大きな数だった場合は自分の DP 解ではダメでこちらをまねしなければいけない。よく見ると mod(=998244353) の他に mod-1(=998244352) が計算に使われている。mod-1 乗ならともかく mod-1 の累乗にどんな使い道があるのか自分は知らない。■F 問題「Virus 2」(黄 diff) は時間内に解けなかったので精進。長めの時間制限４秒が不安をあおる。ダイクストラ法で感染者からの距離を管理して新規感染者を見つけていきたい。どんな下手を打つと TLE になるだろうか。新規感染者が発生した部屋は次の日には感染者からの距離が０になるわけで、最短距離の更新が広範囲に何度も起こる場合に TLE になりそう。できるだけキューを膨らませないようにケチりはしたけど特別なことはせずに 2863 ms で AC になった。01BFS のように一日一日ステップを刻みながらダイクストラ法を進めるのが頭の中がこんがらかって難しかった。つまり、ダイクストラ法を基本にしつつ日を刻み、１日を２つのステップに分けるのだけど、各ステップでやるべきことすべきでないことを見極めるのが難しかった。無駄を許すと TLE になりそうだったのもあるし、迂闊なことをすると２つのステップが連携できなくて機能しなくなるので。■■■C 問題。ケチな考えを追い出して多少の無駄があっても見通しがいいことを第一に書き直してみた>提出 #42960011 (AC / 515 Byte / 78 ms)。515 バイトはタイプするのに長すぎるということはないね。■■■E 問題の mod-1 について。「グラフ彩色 (ja.wikipedia.org)」のページに
(M-1)^N+(M-1)(-1)^N という式が書いてある。mod-1 は単にマイナス１のことだった(それはそう)。