noteレッドコーダーへの道のりは遠い。Colors問題N個の整数aiが与えられる。この整数に赤、緑、青のいずれかの色を塗る。このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。三角形が正の面積を持つ条件は、「三辺のどれか一辺が他の二辺の和より長い」と言える。S/2」であればよい。(R>=S/2かつG>=S/2かつB>=S/2)で求められる。塗りかたは3色のいずれかなので、全塗りかたは3^N。対称性からGとBの計算はRと同じなので、「R>=S/2」と「(R>=S/2かつB>=S/2)」はそれぞれ求めたものを3倍にすればよい。「R>=S/2かつG>=S/2かつB>=S/2」はそのようなのは作れないので0通り。「R>=S/2」は、dp[i][j]:=i番目までで赤に塗った整数の合計がjとなるような通り数、を求めて、dp[N][S/2以上]の合計を求めればよい。(更新式は、GまたはBを選んだ場合「dp[i+1][j]+=2*dp[i][j]」、Rを選んだ場合「dp[i+1][j+v[i]]+=dp[i][j]」で遷移すればよい)「(R>=S/2かつB>=S/2)」は、それぞれが等号の場合しか成り立たないので、Sが2で割り切れるときのみ考慮する。これもdp[N][S/2]の通り数で求められる。Wizard問題N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。マスの外側に移動させられたゴーレムは消滅する。Q回の呪文が与えられるので、最終的にマスに残っているゴーレムの数を答えよ。2*10^5文字は英大文字のみ解法あるマスxにあるゴーレムが左側から消滅する場合、マスx-1にあるゴーレムも(通過するはずなので)必ず左側から消滅する。(右側も同様)なので、消滅するか否かを二分探索で位置を求めればよい。本番中は、両端から消滅ゴーレムは連続するのは気づいたけど、呪文を逆順にして消滅する範囲がどこまでか?を見つける様な方法でアプローチしてしまった。Lのケースでは、1つ目のマスのゴーレムが落ちる様な計算をしてしまうが、そのゴーレムは呪文1で2つ目のマスに移動していてゴーレムがないので、消滅するゴーレムはない。Lなど、いろいろ嘘だった。CrosswordPuzzler概要1週間マラソンはきつい。最終順位は、20位(58人参加)で、結構良かった。問題W*Hのグリッドと辞書(単語の集合)が与えられるので、グリッド上に単語を敷き詰めたい。このとき、グリッドに敷き詰めたときに、縦方向か横方向に2文字以上が並んでいる場合、必ず辞書にある単語になるようにしなければならないし、2回以上同じ単語がでてくるようにはしてはいけない。fib(i)」とするとき、スコアができるだけ高くなるようなグリッド敷き詰めを返せ。単語は、真ん中付近(サイズが小さかったら微妙にずらしたものも候補に入れた)評価関数は「単語スコア合計+文字を置いていないマスの数-使ったマス数」お気持ちは、重なりが多いほどよさそうと思ったので、できるだけマスを使わずにたくさん置いた方がいい、という感じ単純なスコアにしてしまうと、終盤までスコアに差が出ずに、ビーム幅を必要としそうだったので、できるだけ序盤でも差がでるようにしたかった辞書は、長さ順にkグループに分け、順番にビームサーチで最適化するようにした単語数が減るので、最適解が得られない可能性があるが、計算量が減らせて、辞書サイズが多くてもまわせた振り返り1週間マラソンで、土日が腰痛でダメで何も手を付けられなかったのがかなり痛かった。方針決めこれまでのマラソンの反省として、「最適解の形がどんな形か?」のイメージをミスるとお話しにならないと思ったので、ざっくりでも最適解の形を考えた。長い単語をできるだけ使う単語がクロスしている方が、少ないマスで表現できるので、よさそうは間違いなさそうで、クロスを多く作るような形を目指すことに。(最初の時点での理想イメージとしては、以下のような図でいくつか歯抜けになるようなものなんじゃないか?を考えていた)最初は、焼きなましが適用できないか?と考えていたけど、単語を消したときの処理が面倒そう、と思ってビームサーチ方面で考えることにした。(この時点で、最適解はぐちゃぐちゃ絡み合ったイメージを持っていたので、greedyな解は無理では?と思って除外してしまっていた)面倒そうというのは、辞書が{aaa,ccc,bacb}の場合、-a---a--bacb--c---c-と置いて、bacbを消した場合、acを残してもacが辞書にないのでinvalid、acも消してもaa,ccがinvalidになるので、invalidを許すか、invalidを許さない場合は連鎖的に単語を削除していくイメージ。invalidは最後まで残すと解消が無理そうだし、invalidを許さない場合、単語の連鎖が多くなりそう、と思ってあきらめた。(終了後、onigiri(utmath)さんとの感想戦で「消せないなら消さない」というのもあるよね、というアイデアは考慮できていなかった)テスター、ビジュアライザ今回、testerがエラー出力を握りつぶしていたり、visualizerが付いていなかったので、デバッグが非常につらく、途中からc++で書き直したりしてた。2019visualizerはなかったので、テキスト出力で見てたけど、縦長になってしまったり、クロスしている文字がどこなのか見にくく、ちゃんと整形して表示するものだけでも作るべきだった。(結局、終わってからビジュアライザを作ったらそんなに時間かからずできたので、作るべきだったかも・・・)ビームサーチの調整ビームサーチをやろうと思ったら、結構生成される近傍が大きくなってしまって探索空間が大きそうというのにハマる。妥協案として、真ん中付近に一番長い単語を置いて、そこからできるだけ長い単語をクロスするように設置していく(クロスできないならできるだけ長い単語を適当に置く)方法を試す。結局、これ以外の方法などは時間がなくて試せなかった。単純に上記の探索だと無駄な探索も多くて時間がかなりかかっていたので、ある程度時間内に終わるよう調整を考えた。一つ目は、長さが小さい単語は使う必要があまりないor後で設置すればよさそうかもと思い、辞書を長さごとにグループ分けして、計算量を減らすことを考えた。二つ目は、サイズが大きすぎるときのパラメータ(ビーム幅や辞書の分割数など)を調整してた。やりたくなかったので、適当に時間に間に合いそうな値にして提出して、結局最後までそのままだった。盤面や辞書の生成ルール的に、「大きいケース」と「小さいケース」に偏りがあると思って、見ていた。計算してみると、だいたい、マスのサイズが1000以下になるのが63%ぐらい、1000より多くなるのが37%ぐらいで、半分以上がマスのサイズが1000以下の小さいケースのようだった。辞書サイズも小さいので、できるだけ小さいケースは十分な探索をできるように調整したかったけど、最終提出には入れられなかった。searchを試す焼きなましで配置や追加削除を試す(+様々な工夫)市松模様っぽく単語を配置しつつ、できるだけ単語を串刺しにする感じを焼きなましするなどvisualizerやはり簡単でも作るべきだなと思った(テキスト出力では印象が違う・・・)wleiteさんのvisualizerが見やすかったhttps://twitter.com/wleite/status/1098404095759654913ビジュアライザ終わった後で、ビジュアライザを作った。最終状態の出力ではなく、焼きなましやビームサーチなどの途中状態も見れるようにしたいファイルに書き出す方法だと膨大な量になってしまったり、読み込み面倒なので、できるだけC++で完結させたいmacで手頃で使えるのにしたいというのがあった。QtやGTKなどはやや大がかりすぎるような気がして、OpenSiv3Dは新しめのコンパイラを必要とすることから、一番手頃そうなSDL2を試してみた。(「ゲームプログラミングC++」という本でも使われていたのを見たので)悪くなさそうなので、他の手段も調べつつ、いろいろ使ってみたい。第3回RCO日本橋ハーフマラソン予選に参加してみた。atcoder.jp結果は、A問題が102位、B問題が45位の総合67位でした。ツーリストXの旅行計画N個の都市を1度だけずつ順番に巡って最初の年に戻ってくるようなルートを考える。都市間の移動距離をの分散ができるだけ小さくなるようなルートを見つけよ。ファーマーXの収穫計画N*Nの区画の庭があり、i行j列目の区画にA_ijの品質の野菜がある。各区画からは1度だけ野菜を収穫できる。次の操作をX回実行できるとき、収穫する野菜の品質の合計値をできるだけ大きくなるように操作の計画を立てよ。手入れ:選んだ区画の品質を1増やす。収穫済みなら何もしない収穫:選んだ区画とその周辺の条件を満たす野菜を収穫する選んだ区画の野菜が品質Kのとき、まだ収穫されていない隣接する品質がKの野菜をまとめて収穫できるただし、まとめて収穫する野菜の数がK個以上でないと収穫できない。数直線上のある整数点から自由に左右の整数点に移動し、どこかの整数点で終わるような行動をする。このとき、整数iについて、i-0.5の地点を通過したら、i番目の位置に石を1つ置く。目標となるi番目の石の数A_iが与えられたとき、上記の行動を行った後で、目標の石の数にするために石を追加または除去することができる。追加または除去する石の個数が最小となるように行動を行った時の、追加または除去する石の総数を答えよ。0でない偶数個】【0個】のようなゾーンにわかれる(ゾーンがない場合もある)。i番目がゾーンj(上記)だった場合の最小の追加または削除の回数として、更新すればよい。解法2(コンテスト中考えていた方向性の解法で、一応通ったのでメモしておく)行動を、ある整数iに注目すると、「左から入って右にぬける」「右から入って右にぬける」「左から入って左に抜ける」「右から入って左に抜ける」ような4パターンがあることがわかる。0~i番目のどこかで入り、i番目で右にぬけた場合の最小コストを更新すれば、求められる。(更新は、i-1までのdpの値から更新する場合とi-1までをすべて捨てて更新する場合を考える。A_i=0となる場合のコストに注意)同様に、逆方向からdpすれば左にぬけるようなパターンについても同様に最小コストが求めらえる。(これをdp2とする)あとは、ある地点iを境に左側を通った時の最小コストdp1[i][x]と右側を通った時の最小コストdp2[i][y]の組み合わせで最小となるなるものを見つければ、求められる。XXOR問題N個の非負整数A_iと、非負整数Kが与えられる。K)という関数fを定義する。この関数fの最大値を求めよ。関数fはビットごとに0にするか1にするかで関数の値を独立に求められるので、雰囲気、上から貪欲に求められそうに見える。これは普通に嘘で、貪欲が適用できる場合というのは「選択しなかった場合の最終スコアが、選択した場合の最終スコアを超えない」こと(それを証明できること)が必要。(今回の場合、Nが大きいケースなどで、下位ビットの方で大きい値が加算される可能性がある)なので、ちゃんと(全)探索を考える。bit目を考えているとする。K」ならば必ず0にしなければならない。次のbitを同様に探索すればよい。逆に0でも1でも選べる場合、0にしたらそれ以降のビットはどう選んでもKを超えないので、下位のすべてのbitでスコアが高くなる方のビットを貪欲に選んでよい。1にした場合は、次のbitを同様に探索すればよい。F'を持ちながら再帰すればよい。Strokes問題1~Nまで番号が付いたN皿の料理がある。高橋くんがi番の料理を食べたときはA_iだけ幸福度が増し、青木さんがi番目の料理を食べたときにはB_iだけ幸福度が増す。高橋くんから、交互に、2人とも「最終的に自分が得る幸福度の総和」-「最終的に相手が得る幸福度の総和」が最大化するように料理を選ぶ。「最終的に高橋くんが得る幸福度の総和」-「最終的に青木さんが得る幸福度の総和」はいくつになるか。求めたい答えを数式で書いて変形するアプローチを考える。B_iとすると、Yを消去することができる。和が最大になるようにXを選べばいいので、和でソートして交互に取っていけばよい。Grouping問題1からNまで番号がついたN人がいる。10^9+7で求めよ。問題がややイメージしにくいので、具体事例を考えてみる。0グループのようになっている。A,Bは表左の人数に関する条件、CDは表右のグループ数に関する条件を表しており、条件を満たすならこのグループ分けは1カウントに数え上げられる。数え上げなのでdpを考えてみると、「グループ内の人数」と「それまでの確定した人数」を状態にした以下のようなdpが考えられる。dp[i-1][j-i*x]ここでf(i,j,x)は「残っている人で、i人グループをx個作る場合のグループ分けの数」。)したがって、f()が十分に高速に求められれば間に合う。f(i,j,k)を求める。N人中すでに(j-i*x)人はグループになっているので、残りの(N-j+i*x)人からi人グループをx個作ることになる。x!」を割ってあげた以下の式になる。}MOD階乗、MOD累乗、MOD逆元でこれを求めてあげればよい。WikipediaA,B,C,Dの条件がない場合は「ベル数」と呼ばれる。two問題N個のボールがあり、i番目のボールには正の整数A_iが書かれている。このとき、2つのボールを取り出してペアを作り、その数字の和が2ベキ(2^t)になっている場合、そのペアを取り除くことができる。大きい数字の方から注目すると、自身よりも小さい数字でペアを作ることになる場合、2ベキになる数字は一意に決まる(自身より大きい一番小さい2ベキになる)。ある数字xについて、その数字以下のペアになれる数字yが存在する場合、「xを除いた集合」で「xとyを除いた集合」よりもペアを多く作れないならxとyでペアを作っておいたほうがよいが、ペア数は同数か少なくなるしかないので、結局ペアを作っておいたほうが良い。したがって、greedyに、大きい方の数字からペアを作れたら取り除く、を繰り返していけば求められる。c++の場合はmultisetで検索、削除などを簡単に実装できる。endl;解法2上記の解法の考察がやや自分の感覚では自身なかったので、もうちょっと無駄なことを本番では考えてた。これをノードとみなす。大きい数字のペアをその数字より小さい数字で作る場合は一意に決まることから、大きい数字のノードから小さい数字へのノードに辺を貼ると、これは森になっている。ある木について考えると、ペアをできるだけ作ることを考えると、葉ノード側からできるだけペアを作るのがいいので、葉ノード側から処理してペアを作る。最後に、2ベキな数字で残っているボールがある場合、同じ数字でペアが作れるので、それを加えれば答えが求められる。ついでに実装の仕方がダメダメだった。本番は、2ベキなボールは同じ値でしかペアになれない(嘘)、と思い違いして最初にコーナーケース的処理を入れてしてしまっていて通せなかった。正の整数Nが与えられる。vとなるものが何通りあるか求めよ。答えは1,000,000,007のあまりを答えよ。上記の^はビットごとの排他的論理和を表す。10^18解法まだイマイチ理解できていないところが残っているけど、とりあえずまとめ。制約が非常に大きく、xorがビットごとの計算でもあるので、ビットの桁DPを考える。(下から桁DP)問題がやや扱いにくいので、言い換えを考える。a+b)が何通りあるか?」という話でであるが、aとbが入れ替わったものを重複しないように数え上げる必要がある。重複する部分は、各bitがa側とb側で入れ替わったとしても最終的な結果には変わらない部分のことで、「a側が1、b側が0」の場合と「a側が0、b側が1」の場合、2重カウントしてしまう。a+b)が何通りあるか?ただし、各ビットについて、(a側のビット,b側のビット)=(0,0)(1,0)(1,1)のものだけ考える」という問題に言い換える。func(S,X):=「a+b<=S」「a^b<=X」のとき、各ビットが(0,0)(1,0)(1,1)のものだけ考えた場合の、答えの通り数」と考えると、aとbの一番右側のビットについて、上記の3パターンで場合分けをする。