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)。
