2018/1 solved(1)
一昨年やってたのを復活させます。去年は「これあんまり意味ないかもなあ、もっとちゃんと解説書く問題を増やしたほうがいいでしょ」と思ったが、辞めた結果そもそも解説書く問題が減った(ダメ)。他人に読んでもらうことは特に意識せず書きます。
1/1
行きと帰りを同時に探索する。行きは普通に探索(突き当たったら右か左を選ぶ)。帰りは、行きと同時に探索するために後ろ向きに探索する。曲がる条件は、曲がる直線に目の前に壁があることなのでそれに注意しながらあとはBFSを頑張る(submission)。
に注目すると、短辺が15以下であることが確定する。この時、左上から順にガードを置いていくかどうかを決めていくことを考えると、縦方向に監視が効いているかどうかをビットマスクによって管理しながらDPで数え上げることが出来る。他に状態としてもつ必要があるのは、監視の効いていないセルがこれまで幾つか(0/1)、現在注目しているセルに左からの監視は効いているか(0/1)の4つの状態を考えながら数え上げることが出来る(submisson)。
連続して現れる文字は1つに縮約出来る。すると、○✗が交互に現れる文字列になるが、この時に1つ石を置くことでまた縮約が発生すると文字列の長さが1短くなっていくので最終的に1文字になる(その文字が勝ち)。よって、隣り合う部分を見て切り替わっている回数を見ると、このゲームの勝敗がわかる(submission)。
1/2
教授たちを区間の開始位置でソートしておけば、 dp[i][j] := i番目の教授まで決めた、1~jまでの区間はカバー済みの時に必要な教授の数 としてdpを計算していくことで求めることが出来る(submission)。
相手AIの出す手はこちらの手には依存しないので、こちら側が安定して点を取るにはランダムに頼るのが良さそう。負け以外の時は前回と同じ手を出し、負けたときだけ手を変えるようにした(submission)。
1/3
同じグループになるとしたら、その点を基準にして上下左右にそれぞれRだけ伸ばした、一辺の大きさが2Rの正方形の中に入っていると言い換えることが出来る(3R以上の距離があれば、この中に同時に入ることは絶対に無い)。よって、x座標でソートして平面走査、y座標の値をsetで管理しながらUnionFindで管理していく。小数のままだと誤差が発生するので整数の範囲で管理できるようにしてから処理するのがバグらせないために大事(submission)。
?を全てaで埋めた場合が辞書順で一番後ろになり得て、zで埋めた場合が辞書順で一番前になりえる(submission)。
dp[i][j][k] := i番目の建物まで高さ決定、j個の色が見えている、その中で一番高いものkの時の、コストの最小値を計算する。i,jの部分は15以下、kの部分もそれに準じる物しか発生しないので種類としては多くならない。mapで管理した(submission)。
1/4
4の倍数の数、そうではないが2で割り切れる数、奇数の3つにグループ分けして、それらの個数の関係に注目する(submission)。
渦巻状に順番に配置していけば必ず連結に出来る(submission)。
に対して、
の3つの値が作れるのでそれをmapで数え、最大を答える(submission)。
1/5
i番目の要素がswapされる必要があるかどうかという0/1配列を作ると、1が連続する区間ごとに最低でも必要なswapの回数が決まってくる(区間の長さを2で割って切り上げる)。それの和を取れば良い(submission)。
2人組を優先的に使う貪欲(submission)。
うるう年を含めて3年ぶんの日付パターンを用意しておけばチェックしきれる(submission)。
答えは、1,2,...,nの和が偶数の時は0、奇数の時は1に出来る。それは、和をsとすれば、s/2を超えないようにn個の数字を大きい方から貪欲に取っていくことで実現出来る(submission)。
奇数長の閉路があると、必ずどこかで破綻するので、奇数長の閉路があってはならないことが分かる。そうすると、構築できるグラフは二部グラフであり、二部グラフに生やす辺の個数を出来るだけ最大化したい、となると頂点数をできるだけ均等に分けると良いことになる。そうすると、辺数の上界が定まり、下界は連結である条件(以上)によって、不可能判定が出来るようになる。あとは、最初のn-1本で連結にして、残りを二部グラフに埋めていけばよい(submission)。
リストの先頭に0を足しておくと、全ての隣接箇所の差の絶対値が1になっているかで判定できる(submission)。
mapで数えて、keyとvalueを逆にしてソートし、答えを出す(submission)。
頂点ベースではなく、辺に注目して、その端点から生えている辺を全探索し、パスが有るかを判定する(submission)。
駅に辿りつくのにネックになるのは、max{t[i]+3*(n-i)}であることが分かるので、この値を区間addができるSegtreeで管理する(submission)。
1/6
XORの性質を考えれば、AB = C なら AC = B になる。
3個以上の山が1つでもあればBが調整できてしまうので、無条件にBが勝てそう。そうすると、1個の山と2個の山がいくつあるかが重要になる。2個の山が2つ以上あってもBが調整できてしまう。2個の山が1つ以下なら、1つずつ取っていくという状況に持ち込めてそこで初めてAに勝機がある(submission)。
1/7
グラフを構築して一筆書できるかチェックする。連結性のチェックをした後に、次数が奇数の頂点の個数を数えて、0か2なら一筆書できる(submission)。
1/8
1/9
mod tex:10^8+7に気づかず時間溶かしまくった。左回りと右回りが同じ距離の場合があるので、その時は2倍になる(上下も同様)。
最短で歩でたどり着けるグリッドは
個あるので、その歩数を歩ける兵士が何人いるかを見て、それ以上いたら
で抑える。
の制約から、これをチェックするのは125までで良く、それ以降は必ず被り無く歩くことが出来る。
1/10
数は結構大きくなってもいいということに注目すると、n!を用意してしまえばn!+iはiで割れることが分かる。
treapがあればできるという気がしたので、treap実装の練習をした(submission)。
1/11
1/12
パスカルの三角形のn段目は、nのビットの立っている個数の2乗のぶんだけ奇数の項が存在する。それは二項係数などを考えてみると分かる(https://www.math.hmc.edu/funfacts/ffiles/30001.4-5.shtml)。
1/13
まず、末尾にいくつまで9を付けることが許されるかをチェックする。その後は、19...9,29...9, ... , 99...9を作れる組み合わせがそれぞれ何通りあるかを計算すればよい(submission)。
第4回 ドワンゴからの挑戦状 予選に参加
ABCの3完。CのDPは自分が速く書けるタイプのやつだと思ってたのに1時間もかけたのは良くない。
1/14
どのタスクは処理したかをフラグにもつbitDPをする。遷移の仕方が自分では書いたこと無いタイプだった(submission)。
setで{区間の長さ,開始位置}を管理すると、次のターンで取り除く区間がlogで求めることが出来る。また、双方向リストのかたちで隣接関係を管理しておけば、区間を削除した後の左の区間と右の区間を連結させるのも簡単にできる。そのとき、それらの区間が同じ数字なら区間を合成することになるが、それも容易に出来る(submission)。
1/15
文字種類ごとに、その文字が現れるindexをsetで管理すると、削除のクエリに対して全体を通してで処理することが出来る。問題は、与えられるクエリの区間が初期状態のどの区間に該当するかだが、これはまだ残っている文字の位置をsegtreeで管理すれば、二分探索によって見つけることが出来る(submission)。
Codechef January Challenge 2018に参加
自明なとこまでしか解けなかった...要復習。
