2018/3 solved(1)
3/1
CF #411(Div.1) Virtual
ABCの3完。Cの解釈に時間掛けすぎたけど、木という条件を利用することでクリークがそれ以上大きくならないというふうに考えることができ、色は貪欲に決まる。Dも途中までは考察できてたので、Dは解説見ずに通したい。
3/2
3/3
3/4
[2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)] Virtual
dayamaと2人で組んだ。3完。そのうち2つは虚無だし、もうちょっと頑張りたかった...
3/5
3/6
Pythonのitertools.combinationsを使うと綺麗に書ける(submission)。
D個のグループに分けて累積和をとっておく。クエリごとにDが変わるとしたら、Dの大小で場合を分けると(小さい方は累積和、大きい方は愚直にシミュレーション)、時間と空間の計算量の条件を満たせると思う。
3/7
3/8
漸化式の形から、普通にメモ化再帰しても呼ばれる箇所が個しかないので、普通にメモ化再帰でよい。
3/9
パターンが少ないので、それを全探索する。外周にフィットさせるパターンを除けば、片方の種類の向きは1個しか置けないので、その位置を探索して、もう片方の向きを各列ごとにおけるか判定する(submission)。
CF #469(Div.1)に参加
No.662 スロットマシーン ABの2完。AもBもWAを出しまくったし、そのせいでCが間に合わないし色々ひどい...。青くなったし、はやく戻そう。
本当に問題文の理解にめちゃくちゃ時間がかかった。要するに、「subsetとして選んだ頂点のupdate-timeを+1しても条件をみたすようなnon-emptyな最小のsubsetを見つければいい」ので、+1すると時間がかぶってしまうような依存関係が有る時にゆうこうへんを張ると、SCCしてDAGになった後の連結成分で葉の部分で要素数が最小のところを選べばよいことになる(submission)。(またSCCか...)
3/10
とりあえず各リールにどの絵柄が何回現れるか数えておけば、それが実際に出現して揃うパターンはその位置の三つ組に対して5通りあることが問題文で言われているので、実際に何回そろうかは3つの列の出現回数の積の5倍になる。回数が分かれば、期待値はもらえるお金をかけ合わせて、全通りで割るだけ(submission)。
列を左から順番に決めて復元していきたいけど、循環しているので、今回は最初と最後を決め打ちにすることにした。すると、1つめのセルの状態から、2つ目のセルに0,1をそれぞれ選んでよいか、が決まるので、それをメモ化再帰しながら数え上げる。再帰の末端は、最後2つの要素が条件を満たしているかをチェックしている(submission)。
典型的なdp。dp[i][j] := 時間iにいて、j回売りをした時に持てるお金のmaxをすると、iで買って、売るタイミングをで遷移させると、
で解ける(submission)。
ベルヌーイ数でググるとまさに求めたいものが見つかる1つのベルヌーイ数を求めるのになので、全体では
になる。しかし、どうやらもっと制約がきつい問題が既出で、ラグランジュ補間を使って求められるらしい(submission)。
頂点から中心に向かって線を引くと、n個の二等分三角形ができる。その二等辺三角形から、くぼんでいる部分を引けば良い。引くべき三角形の面積は、三点が分かるのでそれによって求めることが出来る(submission)。
3/11
CF #470(Div.2)に参加
ABCDの4完。今日は調子良かった。Eも通したかったけど、さすがにこれは残り時間で考察しきれない気がする...
置換ルールをよく見ると、BはCに、CはBに変換できるので全てのCはBと見なして良い。まず、Bの個数の偶奇は変えられないので、気をつける必要が有る。次に、末尾のAはいじりようがないので、mod3で揃っている必要があるが、揃ってない時には無理やりAをBBに変換して揃えにいかなければならないので、デフォルトの状態でBの個数が完成形よりも少なくないといけない。この辺に注意して場合分けを頑張る(submission)。
スコアが得られる文字列の長さが8以下なので、普通にdfsしてなぞる全パターンを列挙出来る。そこからスコアパターンを何回なぞれるかカウントしておき、それが終わったらdpをする。文字列の長さごとに、考慮すべきのがT個以下なのは明らかなので、それでdpすれば良い(submission)。
これが想定なのか分からないけど、頂点に流量制約をつけてフローが2流せるかを毎回愚直にやった(submission)。
3/12
3/13
bitDPをする。こういう確率のdpは後ろから遷移するようにすると見通しが良い。ただ、最初の考察では、今何番目かと生き残っている猫の集合しか考えていなかったが、今どの猫が戦っているのかも考える必要がある(もしやられた時に次の猫を適切に選べるようにするためにこのパラメータが必要になる)(submission)。
3/14
二分探索(submission)。
Kが共通なのを利用すると、小さい方からK個だけ持つpriority_queueと、それより大きい部分を持つpriority_queueを持つことで、クエリを高速に処理することが出来る。クエリごとにKが可変だとしたら、座圧+BITで出現を管理して、それを二分探索する、とかが考えられる(submission)。
3/15
最初Euler tour + Segtreeでなんとかしようと思ったけど、どうしても逆行列が必要になりそうで、無かったら詰みだなあと思ってた。HL分解を使うと、クエリを個のパスに分解出来て、それぞれに対して行列を乗せたSegtreeで積を高速に計算することで、全体で
になる(submission)。
この問題を解くためには、LCAで十分、u-vパスを根からのパスからの足し算と引き算に分解すれば良い(submission)。
想定会は木上でのimos法だったけど、HL分解の練習として解いた。パスの処理は区間add/区間sumのセグ木があればよいので、パスをそのようなセグ木で管理する(submission)。
HL分解の練習。部分木に対するAddを効率的に処理するために、vidの振り方をbfsでなくdfsで振るようにした。こうすると、部分木に通しで番号が振られるので部分木のサイズが分かっていると1つの区間への操作とすることが出来る。あとは、前の問題と同様にパスの重みは子側の頂点に乗せる重みとして考えて、パス上の和を取れば良い(submission)。
頂点を拡張してBFS(submission)。
2018/2 solved(2)
2/15
CF #416(Div.2) Virtual
ABCDの4完。Bはちゃんと愚直ソートを殺すケースが入っていた(ひっかかった)。
2/16
それぞれの文字列a,bに対して、strictlyに辞書順で小さいaのpermutationがいくつあるかを数える。数える方法は、先頭何文字を一致させるかを1つずつずらしながら試していく。文字目まで同じで、
文字目でstrictlyに小さい文字を選ぶとするとそれがたかだか25通りあって、その組み合わせは階乗を利用した組み合わせの計算で判明する。たかだか25通りの計算部分は、共通部分が多いので、それを先に計算しておいて個別に計算する時に割ることで速く計算できる(submission)。
問題をよく読んで(continuous)...
罠に全部はまってしまった(同じ要素の扱い)(大小関係)(オーバーフロー)。最初めんどくさすぎでしょと思ってたけど、まずmapで何がいくつ現れるかを数えておくと、昇順に処理することが出来て楽(submission)。
70以下の素数が19個しかないので、bitDPできる。二項係数の1個飛ばしの和はの形になるので、各数字が何個現れるかを保存しておけば高速に配れる。37以上の素数については別個にして計算したけど、別にそれなくても通せるみたい(submission)。
全探索。
大きさが異なれば1つにまとめられるので、同じ大きさのものが現れる頻度を数えれば良くて、頻度の最大値が答えになる(でできる)。
そのターンで倒せることが分かったら残りHPに構わず殴って良い。シミュレーションの方針はあんまり良くなくて、初めに回復回数を決め打ちして、あと殴り合って勝てるかを判定したほうが確実だったと思う。
まず、各文字列ペアを全て試して文字の異なる部分を探す()。もし、ここで見つからなければ
個の文字列は全て同じということになるので、適当にどこかswapして出力すれば良い。そうでない時には、その発見したペアのそのindexにおいて、どちらかはそのindexでswapが起きているということに注目して、その2つの文字列についてそのindexとその他のindexをswapした
通りの文字列が答えの候補となる。あとはこれらの候補に対して、妥当であるかのチェックは
で行うことが出来る(submission)。
実装自体は難しくないんだけど、long longの範囲に収まらないのには気づけなかった...(submission)。
2/17
後ろから決めていける。
2/18
Rの個数を全探索する。その時に変更する必要がある個数は簡単に計算できる。
終わりから始めに向かって貪欲に三角形の辺を大きくすることで、最短回数を実現できる。
まずは、dp[i][j]でi回目に終わった次点で合計でj点を得る組み合わせを計算する。問題では1回のターンで得られる得点は-k~k点になっているが0~2kにしても差し支えないので、実装上はそうしている。このdpの計算は、累積和を利用してで計算できる。これが計算できれば、あとは相手がi点取る場合というのを全部試す。この時に勝つためには何点以上が決まるので、先に計算したdpの結果に対して累積和を持っておくことで高速に計算できる(submission)。
2/19
diplomaを受け取れる人数をにすると、cetrifiacateは
人、この和が全体の半分以下になるようにする。
まず、ゲームをシミュレーションして分かるを確定させた後、それに影響しないところを出てこない数で埋める。数字に被りがあればダメ。
2/20
条件の理解にめちゃくちゃ時間がかかった。でも、累積和で数え上げといて、あとは各ソファに対して判定をするが、横向きか縦向きかで累積和の扱いの対応を変えると処理が楽(submission)。
1回のリスト走査で、各数が条件を満たすかどうか判定する。最も厳しい条件になるのは、その数を足す直前なので、各数の個数をカウントする時に、その直前に条件を満たすかチェックするだけで良い。あとは、最終的な個数も条件を満たすかをチェックしてあげればok(submission)。
全体でかかる時間の和が、availableな区間に入っているかをチェックする。
x,yが2以上なので、以下の範囲にたかだか5000個ぐらいしかunlucky yearはないので、それを列挙してから間をチェックする。Pythonのsetはsortedになってないので注意(1敗)(submission)。
Aliceとしては、Bobの動ける部分木を狭くすることを考えれば、Bobの方にただ近づいていく戦略が最適である。Bobの戦略を考えてみると、とりあえずAliceとぶつからないところまでは祖先を辿って行き、ギリギリまで行った所でその部分木に対して最も遠いところに逃げれば良い。(submission)。
2/21
こういうタイプのdpすごい苦手...2つの点を独立に動かすみたいなやつ。遷移が頭のなかでごちゃごちゃになる(submission)。
2/22
個全部に対して素因数分解やってたら間に合わない。
の倍数になるかどうか知りたいので、
を素因数分解してそれに関係ある素因数の個数だけ分かれば良い。素因数分解したあとは、数列の各値に対して各素因数で何回割れるかを数えれば良い。そこまでできれば、あとは尺取りで数え上げる(submission)。
何本の辺をおけるかを二分探索する。最低限はおける(木になるので全ての辺が橋)。そして、
本以上置くことは出来ない(
本を橋にするのは不可能)。
本おけるかをチェックするには、まず過半数が橋として使われ、残る辺の個数が決まる。
個の頂点を連結成分ごとに分配することになるわけだが、残る辺を消化するために、できるだけこの頂点は偏って分配した方が良い。よって、1頂点ずつ分配して、残りを集めるという分配が良い。そして、残った頂点数で構成できる完全グラフの本数と残っている辺の個数を比較して、実現可能かチェックする。気づけば簡単で、本当に二分探索するだけなので実装も簡単(submission)。
悲しいけど見覚えがある。mincostflowをはった(負のコストが発生するけどDAGなのでうまく動作する)(submission)。
CF #415(Div.1) Virtual
Aしか解けなかった...Bは完全に方針ミス。この方針のどこがダメか、気づいたのは10分前だった。
区間に対して、最低限1つを見つけに行こうとするアプローチと、それが左半分にあるか右半分にあるかをチェックすることで毎回区間を半分にできるというところまでは方針として悪くなかったけれど、そのチェックの際に区間のどの値をクエリとして投げるかと考えた時に、自分の方針では区間の端を選んでいたけれど、これではダメ(区間の外の状況に左右されてしまうので)。なので、区間の中心の値を利用する。区間に対して、
として、
をクエリとして投げると、返ってくる値によって左半分or右半分のどちらかに絞り込むことが出来る。このように
の値を利用すれば、区間の外に依存することがなくなるので、正常に区間内を調べることが出来る。2つ見つける方針は、まず、区間全体に対して上記のことを行って答えを1つ見つける(
)。見つけたあとは、
より左の区間と右の区間に対してそれぞれ同様のことを行い、見つけられるかをチェックすればよい。上限は60回なので、十分である(submission)。
2/23
CF #414 Virtual
ABCの3完。構築ゲー全く思いつけない。橋とか色々考えたけど、クリークに注目するのがミソだったか...
クリークに気づくのが重要だったようだ(クリーク内は、全て同じlabelを付けることが出来るので)。逆に、そうでなければ違うlabelを付けるべきことに気づく(どこかで破綻する、辺がないはずのとこが差1以内になってしまったり...)。解説では、隣接リストに自身も含めたものでグループ分けをして(こうすると同じグループに属するものはクリークになっている)、そのグループ化したものを新しいグラフとして、そのグループに対してlabelを割り当てる。新しいグラフ出来たグラフで、次数が3以上の頂点がある場合はlabel付けは破綻する(自身がの時、隣接する頂点に付けられるのは
か
の2種類しかない)。すると、新しいグラフできるグラフは、各頂点について次数はたかだか2。すると、出来上がるグラフは一直線かサイクルのどちらかということになる。一直線なら簡単で、順番に1,2,3, ...とつければ良い。サイクルに対しては適切なlabel付け方法が存在しない(大きさ2のサイクルは、制約的に多重辺がないのでムリ。そうすると3以上になるわけだが、隣接しない頂点同士が1以内になってしまわないように気をつけながらlabel付けをしたとしても、どこかで必ず隣接する2箇所が2以上の差があるlabelを付けることになってしまうことになる)(submission)。
2/24
2/25
2017-2018 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2017) Virtual
チーム戦バーチャルをした。もしあの3人で組むなら明らかに幾何要員がいないことが分かった(あんま経験ないと思ってた自分が一番幾何できそうな感じがあった)。
2/26
University Codesprint 4に参加
6完した、100位以内に入れたので嬉しいけど、最終問は結構適当な解法を投げたのに通ってしまった...
2/27
CF #413 Virtual
ABCの3完。Dは方針間違ってなかったのに誤読して1時間くらい無駄にした...(Announcementを確認することを学んだ)
片方の幅を100000倍するには多くても17個あれば十分()なので、全部で34個あれば絶対にできる。後は、大きい方から取るのが得なので取る順番も決まり、
dp[i] = 片方の幅がiの時のもう片方の幅のmaxというdpをする(submission)。
