全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する」という制約から推移律を破るような循環する入力は与えられないと思ったけど勘違いだろうか。あるいは単純に計算量が見積もれていないだけだろうか。N≦50 だから４乗でも通るはずだけど。TLE の原因がわからない。Ruby で最初に提出された #44259309 (kuma_rb さん) の着眼点がすごい。負けなかった人が一人だけいたならその人が最強だと。トーナメントではそういう話を聞いたことがあるけどね(「優勝者とは唯一負けなかった者のことである」)。■C 問題「Approximate Equalization 2」。これは B 問題より簡単だった。平均として考えられる２つの整数(切り捨てと切り上げ)を考えて、A 数列のすべての要素について下げるなら下げる量、上げるなら上げる量を数える。下げる量と上げる量の大きい方が答え。上げるのと下げるののうち操作回数が余った方は２つの平均値のあいだを移動するのに使われている。■D 問題は答えを求める手順がわからなくて飛ばした。もし答えが絶対にわからないときの答え方が用意されていたら、まんまと「わかりません」と答えて WA をもらっていたところだった。■E 問題「Duplicate」。そもそも長さ１に収束するというのがけっこうなレアケース。S="22" でも永遠に短くならない。先頭の文字はどうでもいい。２番目以降の文字が操作後の長さを決める。１なら現状維持(ということは操作により末尾の１文字分減る)。２以上なら伸びる。しかし２から９までの数が２から９までの数を増やして伸びることはない(そうしたら収束しない)。２から９までの数が末尾に至って消滅するまでに何個の１を生成するかを数える問題。右側にある文字数と同じ回数だけ、決まった長さ(１から８)だけ伸びる。右側にある文字数が知りたいので末尾から(ほとんど１の)長さであり操作回数を数える。■D 問題「Odd or Even」。コンテスト終了まで考えていた F 問題 Flip Machines が解けなかったので終了後に D 問題に戻ってきた。N 回のクエリで数列全体の偶奇(の連鎖)が決まるのはわかる。たとえば A[1..K] の偶奇がわかって A[1..K-1,K+1] の偶奇がわかると A[K] を基準にして A[K+1] の偶奇が同じか異なっているか決めることができる。同様にして A[K+2] 以降も決める。A[1] から A[K-1] の偶奇についてもうまいことやって決める。ここからが問題だった。クエリ回数は上限の N 回まで使い切っている。A[K] の偶奇を基準にして同じか異なっているかはすべて判明しているが、A[K] の偶奇を決めることができるのかどうか。たぶんここで K が奇数だということが効いてくるのかな。最初のクエリを思い出そう。A[1..K] の偶奇がわかっている。そして A[K] を基準にした仮の偶奇について、１から K までの範囲の偶奇はどうなっているだろうか。一致しているだろうか異なっているだろうか。もう解けた。■コンテスト成績証。自分のすべての提出。D 問題も時間内に解きたかったけど、終了後に１時間かけているので惜しいところはなかった。それというのも人間ジャッジがときどきレスポンスの偶奇を間違えるからなのですね。解答のデバッグと並行していつの間にかジャッジのデバッグをさせられていたのでは時間もかかる。D 抜きでも青パフォが出たのは E 問題様様です。■F 問題について。N≦40 と制約はかなり控えめ。各マシンについてありうる未来はかなり限定されていると思った。操作しなければ２枚のカードについて {表表}。１回の操作で {表裏,裏表}、２回の操作で {表表,裏裏}、３回の操作で {表裏,裏表} これは１回の操作と同じ未来。それでどうする？
直方体同士は体積が正の共通部分を持たない」 だったら N 個分書き込んでも総和は 100 万以下じゃん！ 隣のマスを見たら隣接直方体がわかるやん！ 提出 #44116267 (AC / 553 Byte / 729 ms)。■延長１日を含めてこれもう実質７完でいいんじゃね？ やったぜ！(めでたい)■■■G 問題。現在見ている頂点を３つ組の真ん中の頂点だと考えて直線トリオを数える DP ができるらしい(最後に３つ組の全選び方から引く)。提出 #44139844 (AC / 303 Byte / 634 ms)。そうすると直線ペアの数を数える必要がなくなって、サイズと直線トリオの数だけを数えればよくなったけど、期待に反してわずかに遅くなった。400 ms、500 ms 台に入ると思ったのになぜ？ 実は答えを合わせるのにすこし苦労して、現在見ている頂点を３つ組の真ん中に決め打つということは、他の２頂点を選んでくるのは子方向の部分木だけに限らず親方向からも選んでこられる(16 行目)。その点がこれまでの２つの解答と異なっていた(これまでは現在見ている頂点が LCA になるような３つ組を考えていたので問題が子孫方向の部分木に閉じていた)。■E 問題。たぶんだけど、サンプルにわかりやすーい図解が付随していたら当日の AC がもっと多かったと思う。問題文を読んでも全然具体的イメージが構築できなくて苦労したもんね。まず直方体の対角線って何だ、とか。それは長方形の対角線とは(必ず)違うと考えていいのか、と。不等号(X1<X2, Y1<Y2, Z1<Z2)に意味を持たせすぎないでもっと文章で説明してくれていいのよ。辺が軸に平行だということも、え、それってどういう、という疑問からなかなか先に進めなかった。脳内直方体は歪んでいた(それは直方体ではなくない？ 菱餅？ そんなつっこみも出てきやしなかった)。■■■F 問題。自分の提出は BIT を使ったせいで余分な log がついて時間がかかっていた。よく考えて整理した結果、２本の累積和から M 個を取ったあとで綱引きをするようにした。要するに尺取り。提出 #44215202 (AC / 619 Byte / 389 ms)。最速級まではいかないけど BIT 版より倍は早くなった。じっくり整理したので規則的で理解しやすいと思う。S2 に前加工を施すと k1x の補正が必要なくなるし、無意味に缶切りを取得する前に試行を中断できるけど、それは TODO。
心臓の鼓動が平常より烈しいこと。また、その鼓動」「
動悸がする」「
動悸を打つ」などと書かれている。つまり動悸という言葉の中にすでに鼓動の早さ強さが含まれている。今日「動悸が早くなった」という用例を本で見かけた。珍しくはない使われ方だけどちょっとひっかかる。「鼓動が早くなった」とか、ちょっと古めかしい定型かもしれないけど「心臓が早鐘を打った」とかで良くない？ でも、すでに動悸がある状態がさらに程度を増したというように読み取ることができなくはないかな、と思いもする。そのつもりで書かれただろうとは思わないけど。辞書に書かれているのは前例であり、現在の用例も前例のひとつになりうる。動悸という言葉が使いやすい形と意味を持っていないバグが是正されていく過程にも思える。どっちつかずの微妙なきもちにさせられる言葉。あるいは個人的な見当外れのこだわり。「HTTP プロトコル」の仲間に見えるんだよなあ。Horyuji Temple が仲間に加わるとむしろありの例なんだよなあ。
すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ」というのは要するに輪っかのことで、しかも輪っかを横切るショートカット辺が存在しないもののこと。N の２乗が通る制約ではあるけども、すべての頂点を始点にして輪っかを検出して、輪っかのパスを辿ってショートカット辺が存在しないことを確かめて許されるのかどうか。■提出 #43905266 (AC / 967 Byte / 77 ms)。再帰関数のパラメータとしてパスを表す配列と、再訪確認のためにパスをメンバとするハッシュ表と、調べたけどダメだったことをメモするハッシュ表を渡している。もっとうまいやりようがありそうなものだ。■輪っかの検出ロジックは、終点を決めて、終点の隣接頂点の１つを始点にして終点への到達可否を調べる。そのときに始点や中継点において、終点に到達したパスの中に２つ以上の隣接頂点(←始点や中継点にとっての)が含まれていないことを確認している。２つ以上の隣接頂点が関わる輪っかはショートカット辺がある輪っかなので。これを愚直に繰り返すと TLE になったので、ダメだった結果をメモしている。輪っかにならなかったケースとショートカット辺があったケース。メモの利用は中途半端で、輪っかの終点を切り替えるごとにリセットしてしまっている。輪っかなんだから(輪っかを検出するための便宜上の)終点をどこに取ったとしてもショートカット辺があるせいでダメだったという結果は共有できるはずなんだけどしていない。あと必要だったのは終点を含まないところで輪っかができてしまうケースの除外。それはいま関心がある部分ではないので後の処理を待ってほしい。再帰関数で同一頂点への再入を検知してリターンしないとスタックを使い尽くしてしまった。■これって強連結成分を定型的に列挙してショートカット辺をちょちょいと調べて終わりだったりしたのでは？ 自分は何か輪っかの検出で苦労して、輪っかの検出とショートカット辺の確認を同時にやろうとしてさらに苦しくなっている雰囲気。DFS ２回の SCC 分解がそらで書けるほど身についてないから仕方ないんだけど。■日記を書くために自分の解法を書いていたらこれがなんで AC なのかわからなくなってきた。それでひとつの発見があった。最初に「要するに輪っかのことで、しかも輪っかを横切るショートカット辺が存在しないもののこと」と書いたけど、ショートカット辺はただのショートカット辺ではなくて長さ１のショートカット辺だった。誘導部分グラフに含まれる辺と含まれない辺を考えれば当然のことだけど。そうするとひとつの疑問がわいて、どんなループでも、許されない長さ１のショートカット辺を本式の、ループを構成する辺として採用することで答えにすることができるのかどうか。できそうな気がする。それで実装が簡単になるかと思って別解を書き始めたけど、べつにそんなことはなかった。■提出 #43935918 (AC / 1048 Byte / 69 ms)。長くはなったけどややこしさは減って、シンプルに閉路検出＆コンパクト化で答えが得られるようになった。■この問題を選んだきっかけはこの前の ABC311-C「Find it!」で閉路検出を書いたからで(#43848448)、その目論見が外れてやけにややこしい解法に当初はなったけど、別解ができてみると狙いが外れていなかったことがわかる。グラフの形がちょっと複雑になって、閉路のコンパクト化という処理を追加したものがこの Pure という問題だった。
⊼ は結合法則を満たさない」。だから右側からの累積和を使って左側から数え上げていくことはできない。できない？ 昨日は左側からの累積和をどうにかしてうまく数えられないかと四苦八苦していたが、成果なし。一日経ってあらためて 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 が返る。