syamashi

atcoder(highest:1844)/42Tokyo2月1期(pass)

syamashi

atcoder(highest:1844)/42Tokyo2月1期(pass)

マガジン

  • atcoder

    解説とは名ばかり。解けた人が読めばわかる怪文。

  • 42tokyo

最近の記事

  • 固定された記事

Hello world

ft_printf("Hello World"); 42Tokyo1期生 syamashi です。わずかな才能たよりに、情熱もって学習している畜生。 ◆プログラミング歴 2019 11月 atcoderで産声あげる(c++) https://atcoder.jp/users/merhorn 2020 2月 piscine参加(c言語)(Lv9.10突破/多分上位20%ほど) 2020 4月 atcoder 緑🐢 2020 6月 1stCircle KickOff 2020

    • [第二回日本最強プログラマー学生選手権] F - Max Matrix を間違えた

      [Q] F. Max Matrix ・考察 行列があって、行にあるすべての値を最大値に変えていくのか、と勘違い。正しくは、掛け算九九表の値を毎回変えて、行と列のmaxをとる、ということ。 こういうこと。 10 000 10 020 0 10 020 5 30 020 5これではない。10 010 020 2010... ・まちがった実装。これはこれで問題としてありそう。 https://atcoder.jp/contests/jsc2021/submis

      • [ARC170] B - Arithmetic Progression Subsequence

        [Q] B - Arithmetic Progression Subsequence 考察 0. A<=10と特徴的。何かAに絞って数え上げられないか考える。 O(NlogN*10)くらいでいけそうだと思う。 1. index_iを0~N-1まで見るとして。数列の末端をindex_iに固定して考える。 2. 等差数列のパターンを出してみると、どの数も4~5通りしかないことに気づく。 // 等差数列の組み合わせを調べる // 1だとして、moves[1] = {11

        • [ARC170] A - Yet Another AB Problem

          [Q] A - Yet Another AB Problem 考察 1. どうしても作れないケースを考える。 サンプル12ABBA1. Sの先頭をBにしたいけど、先頭より前でAに変えるような場所がないのでできない。2. Tの末尾をAにしたいけど、末尾より後でBに変えるような場所がないのでできない。サンプル26BBABAABBBAAAこれもできない。1. S[2]をBにしたいけど、S[0]もS[1]もAにできない。2. S[3]をAにしたいけど、S[4]もS[5]もBにでき

        • 固定された記事

        Hello world

        マガジン

        マガジンをすべて見る すべて見る
        • atcoder
          syamashi
        • 42tokyo
          syamashi

        記事

        記事をすべて見る すべて見る

          [AGC065] Shuffle and mod K

          [Q] Shuffle and mod K 考察 1. permutationで全パターン試す。最善スコアがどのような出力になるかを観察する sample K=1033:3 1 9 8 626:2 1 9 840:2 1 0 6 5 230:0 5 1 0 1 030:0 1 0 5 1 070:7 6 5 2 11. 数がばらけている場合、降順のかたまりが1or2つできてる2. 同じ値が複数ある場合、降順のかたまりがいくつかできている。 2. 次の3パターンを網羅した

          [AGC065] Shuffle and mod K

          [ABC331] F - Palindrome Query

          [Q] F - Palindrome Query 考察 0. 回文を高速に判定する技あるかな?何も思いつかない。トリッキーな工夫の余地がないように見える。 ものすごく単純に「文字列Sの切り出しと、逆さ文字列Tの切り出しが同一か比較する」を回答する。この方法を軸に高速化できないか考える。 int main() { ll N, Q; string S, T; cin >> N >> Q >> S; T = S; reverse(all(T)); ll q, x,

          [ABC331] F - Palindrome Query

          [ABC330] F - Minimize Bounding Square

          [Q] F - Minimize Bounding Square のこり70分。正方形の辺の値で二分探索。 なんとなく中央値に寄せるのが最適?と思い、{xの中央値,yの中央値}を中心とした正方形で試すが、違うらしい。 のこり50分。xとyをそれぞれ独立に考えればいいと気づく。 このとき、スタート地点となる正方形の左辺と上辺を三分探索して、最も移動距離の小さいスタート地点を求めればよかった。 のこり35分。いったと思いきや、8ケースでTLE。 三分探索する箇所をO(N)で

          [ABC330] F - Minimize Bounding Square

          [ABC330] E - Mex and Update

          [Q] E - Mex and Update 考察 1, mexを求めるときは大体set。 2. setに初期値{0,1,2,3,…}を入れる。 3. 値を使用したらsetからerase()。 4. 値を復元したらsetにinsert()。 5. 答えは常にset.begin() 実装 int main() { cincout(); ll N, Q; cin >> N >> Q; vector<ll> A(N); map<ll, ll> mp; rep(i,

          [ABC330] E - Mex and Update

          [ABC159] F - Knapsack for All Segments

          [Q] F - Knapsack for All Segments 考察 1. DP[N][S]とエスパー。 2. indexを進めるごとに、どれだけパターンが増えるかを考える 3. 取りたいindexの、1個前の値を含んだ範囲と、今のindexを接続できる。 1 2 3 4 を考える。4をとるとき、(1,2,3)+4と(2,3)+4と(3)+4と+4の4通りの範囲の取り方が、新しいパターンになる。連続した範囲で選ぶ必要があるから、1個前のindexをとる取り方を、DPで

          [ABC159] F - Knapsack for All Segments

          [ABC327] F - Apples

          [Q} F - Apples 考察 1. y軸を時間、x軸を座標の位置として、2次元グラフでリンゴを書いてみる。 T...o...o.o.o..o.....o..........o.......o...oo...o..oo......o....oo..o..o.o..o.o.o..o X 2. D*Wの長方形を当てはめてみて、最もリンゴを囲める数はいくつ?が解答になる。 3. 時間でsortして、しゃくとり法で時間を進めていく。 4. 遅延セグ木にりんごのデータを入れて

          [ABC327] F - Apples

          [ABC327] E - Maximize Rating

          [Q] E - Maximize Rating 考察 1. N, M = 5000は二次元DPだと思う。 2. DP[i] = i個とったときのベストスコアとして管理。 答えはDP[1] ~ DP[N]までのベストスコアが解答になる。 3. index i~Nまで探索する。 indexごとに、1~N個とった場合のスコアを計算する。 4. 遷移は、nDP[i] = DP[i - 1] * 0.9 + p[i]で、最大値を更新する必要がある。 5. 確定で取らなきゃいけないとき

          [ABC327] E - Maximize Rating

          [ABC327] D - Good Tuple Problem

          [Q] D - Good Tuple Problem 考察 1. 二部グラフが作れるかどうかを聞かれているので、判定をしたい。 2. 普通にグラフを張る。 3. 頂点0からdfsをスタート。スタートの色は0で固定する。 4. 自分が0なら、1手先の色は1に。次は0に。を進めていく。矛盾があればNo 5. スタートする頂点をNまで確認。スタートの色が定まっているならスルー。矛盾があればNo 6. 矛盾がなければYes 実装 int main() { cincout();

          [ABC327] D - Good Tuple Problem

          【PGBattle2023】ましゅまろ 難易度5 : ダンス

          [Q] https://products.sint.co.jp/hubfs/resource/topsic/pgb2023/1_4.pdf 考察 1. 区間DPで考える。 2. DP[0][N]が答え。 3. 区間の幅を2,4,6,8,…と固定し、徐々に増やして探索。 4. 固定幅の中で、FMのペアを全探索。開始地点を固定する。 5. FM区間と、その外側の区間でDPの積とcombinationの積をとる。 幅8のときFMBBBBBB // DP[0][8] += DP[

          【PGBattle2023】ましゅまろ 難易度5 : ダンス

          [ABC326] E - Revenge of "The Salary of AtCoder Inc."

          [Q] https://atcoder.jp/contests/abc326/tasks/abc326_e 考察 1. indexごとに考える。そのindexを踏む期待値はどれだけあるか。 ex[0]: 1/N // 1回目で1/Nを引くex[1]: 1/N + 1/NN // 1回目で1/N + A[0]から1/Nex[2]: 1/N + A[1]/N + A[0]/N // 1回目で1/Nと、A[1]から1/Nと、A[0]から1/Nex[3]: 1/N + A[

          [ABC326] E - Revenge of "The Salary of AtCoder Inc."

          [ABC326] F - Robot Rotation

          [Q] https://atcoder.jp/contests/abc326/tasks/abc326_f 考察 1. N=80だけど、y軸移動に関するのは偶数ターン(0-indexed)の動きだけ。40ターン/40ターンに分けられる。y軸移動とx軸移動を独立させて考える。 2. 半分全列挙で、2^20 * 2^20は間に合う。 3. とりあえず目的地にたどり着けるかどうか判定する。 4. たどり着けると分かったときに、経路を復元したい。 5. 半分進んだ時点で、値がいくつ

          [ABC326] F - Robot Rotation

          [ABC326] D - ABC Puzzle

          [Q] https://atcoder.jp/contests/abc326/tasks/abc326_d 考察 1. 実装重そう。とりあえず全探索を考える。 2. 25マスに4通り"ABC."が入るので4^25通りの探索。これはTLE。 3. 枝刈り条件がたくさんあるので、削っていけばdfsで間に合う気がする ・自分のマスにAをおくとき、行と列にすでにAがあればおかない ・行を置ききったあと、行がABCを網羅していなければダメ ・列を置ききったあと、列がABCを網羅してい

          [ABC326] D - ABC Puzzle