CodinGameのSPRING CHALLENGE 2021に参加しました。 twitterが盛り上がっていて楽しかったです。 結果 世界66位日本12位でした。 TLの知見ツイートにかなり助けられました。 学校別では世界11位日本2位でした。 11人参加していたんですが、10人がゴールド以…

ペンキの色 atcoder.jp JOI 難易度7 解法は一瞬で思いついたけど、実装にかなり時間がかかった。 座圧してbfsをした。 強い人はUnionfindを使っていた。こっちの方が楽そう。座圧用の配列に各値を+1した値も入れたが、必要なかった。 Grouping atcoder.jp ED…

今日から再開する Unfair Nim atcoder.jp 黄diff A[0]^A[1]==A[2]^...^A[N-1]となればいい。 2進法の下の位から、桁dpで移動する石の数を考えていく。 A[0]は上の位から借りているか、A[1]で繰り上がりが起きているか、の情報をdpに持たせる。 釘 (Nails) at…

困った。書くやる気がでない

Battle with E869120! atcoder.jp unrated 好き。(H-1,W)か(H,W-1)に最初に置いた人の負け。全体のマスから(1,1),(H-1,W),(H,W-1),(H,W)を除いたマスの数が奇数なら先攻、偶数なら後攻を選ぶと、(H-1,W)か(H,W-1)に置くことをを相手に押し付けることができる…

認証レベル atcoder.jp JOI 難易度8 各事務所で、「need[x]:x個の部屋を見学するために必要なレベル」を求めることができれば解ける。次に見学可能な(まだ見学していない)部屋の内、最小のレベルの部屋に見学することを繰り返すbfsをすれば損をすることはな…

解読 (Deciphering) atcoder.jp JOI 難易度8 以下のように定義する。 dp[i]:i番目の文字で終わる原文からi-1番目の文字まででできる原文を引いた総数 cnt[i][a]:i番目の文字までを考慮したとき、文字aで終わる原文の総数 dp[i]=sum(cnt[i-1][a](文字aとi番目…

日記 研究室の申し込みをした。2/14の分のブログを書いた。競プロは全くしなかった。明日は精進したい。

楽しすぎる家庭菜園 atcoder.jp unrated 最大全域木(造語？) 南極 atcoder.jp unrated ダイクストラで解いた。マス(h,w)から(nh,nw)に移動する時、A(nh,nw)!=0 and A(h,w)!=A(nh,nw)の場合はコストがC(A(nh,nw))かかるとした。それ以外はコスト0。 通学路 at…

虫取り atcoder.jp unrated HLD＋遅延セグ木。遅延セグ木のbuildを忘れていて無限にWAがでた。 高速道路 (Highway) atcoder.jp JOI 難易度10 HLD+区間和でできそう。上りと下りで時間が違うのが面倒そう。都市xから都市yへのパスは上り(x→lca(x,y))と下り(lc…

筆塗り atcoder.jp PAST HLDの整備をした。HLD+遅延セグ木で解ける。 虫取り atcoder.jp unrated HLD+遅延セグ木でできそう。永遠にバグが直らない。遅延セグ木の理解が浅いのが原因そう。明日やる。

課題やらないとと思ってたら1日が終わった……明日こそHLDの整備をする。

マスゲーム atcoder.jp unrated gridのbfsをライブラリ化した． 38 parrots codeforces.com チーム練D queueを意識せずにセグ木に全部乗せていく。区間のminとgcdが一致すればY。 Fence codeforces.com チーム練L 考えると線と円弧になりそう。凸包を作り，…

GCD or MIN atcoder.jp 黄diff 残る整数は，A[0]...A[N-1]から1個以上取ってgcdを行った形で表せて、Aの最小値以下のもの。A[0]...A[N-1]のそれぞれの約数(残る整数の候補)を求めて、それらが↑の形で表せるかを判定することで解くのを思いついた。判定は、例…

チップ・ストーリー ～白銀編～ atcoder.jp unrated Pの最大値*Qの最大値がN以下になればいい。Pの最大値*Qの最大値を決め打ちして、その中でmin(Pの最大値,Qの最大値)を全探索した。O(N√N)だと思う。解説では、Pの最大値を全探索していた。この方法だとO(N)…

Attack to a Tree atcoder.jp 橙diff 木の2乗DPということは事前に知っている状態で解いた。 dp[i][j][k]:頂点iの部分木でj回切断を行った時のiと連結しているAの和の最小値(k=0の場合は全てのAが正)とした。遷移させた後に初期化が必要。 遷移元と遷移先が…

パンケーキ (Pancake) atcoder.jp JOI 難易度7 N枚の良いパンケーキタワーを全て求めて、それらを始点としてBFSをすればいい。 TLが厳しくてTLEを連発した。 int id(string s){ int t=1; int ret=0; while(s!=""){ ret+=t*(s.back()-'A'); s.pop_back(); t*=…

脳内AC1問＋解説の理解2問。眠いので寝る。 第一希望の研究室が意外に人気で現実は厳しいなとなった。

L番目のK番目の数 (LthKthNumber) atcoder.jp JOI 難易度8 K番目がmid以下になる数列がL以上存在することと、答えはmid以下であることは同値。にぶたんでこれを満たす最大のmidを求める。 イベント巡り (Event Hopping) atcoder.jp JOI 難易度8 解説を見た。…

棒の出荷 atcoder.jp PAST M 最小値の最大化なのでにぶたん。 「全ての棒の長さをmid以上L以下にすることができるか」という判定問題になる。 ある切れ込みからの棒を考えるとき，その終端になることができる切れ込みは1つの区間になるのでimosを使える。 T…

report - 報告 (Report) atcoder.jp JOI 難易度10 最近学んだオイラーツアーを使う問題を調べたらでてきたので解いた。強連結成分分解をして森にする逆向きにしてオイラーツアー(頂点属性)オイラーツアーを少し変えた・根を見つける・森に対応 D - 歩くサン…

CodinGameのFALL CHALLENGE 2020に参加しました。 参加している日本人が多くて、twitterが盛り上がっていて楽しかったです。 結果 世界50位日本12位でした。強い(断言)。 LEGEND入りが目標だったので達成できて嬉しいです。 前回のコンテスト後、3つのゲーム…