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

syamashi

    • フラクトオリゴ糖は虫歯にならないのか？最善はキシリトールか？

      体験談なだけで、科学的な記事ではありません。 虫歯対策になる砂糖を試したくて、フラクトオリゴ糖を始めました。 フラクトオリゴ糖について、明治HPで虫歯にならない簡潔な理由が示されています。ただ、今回フラクトオリゴ生活をした結果、虫歯になる理由があると私は思いました。 実体験 フラクトオリゴ糖生活を2kg試しました。 これが一番安いと思います。 2290円/1kg 食後のココアや、間食のおやつでフラクトオリゴ糖を摂取しました。 確かに口の中が粘つくようなことはありませ

      syamashi

      • [ABC350] F - Transpose

        [Q] F - Transpose 本番出れていないんですが、裏イベントの 第一回マスターズ選手権 -決勝- で遊んでいました。とても良い日で、ごはんも美味しかった。 ABCに出ていた場合、パフォ1600弱で負けです。 考察 1. 直感では()の深いところから処理していくと思ったが、間違い。 どうしても()の文字列をどこかに保存することになり、S^2のデータを扱ってしまうことになる。これは無理。 2. 貪欲的にO(S)で処理が求まるしかなさそう。実際そう。 3. 文字がどの

        syamashi

        • [ABC214] F - Substrings

          [Q] F - Substrings 考察 解説ACした。dp何もわからない…。 0. とりあえず「1個前をとらない」という条件をなくして考えてみることに手がかりがある。簡略化して考える手間を惜しまないほうが、俺にはちょうどいいかもしれない。 1. dp[i]を、index_i番目の文字を採用した場合何通りになるか、で管理する。 2. 答えはdp[0 ~ N-1]の和、のようになるのだがちょっと違う。 結果的にdp[K ~ K+N-1]の和が答えになる。K個の下準備を施した

          syamashi
        • 固定された記事

        Hello world

        syamashi

        マガジン

        • atcoder
          275本
        • 42tokyo
          33本

        記事

          [ABC348] F - Oddly Similar

          [Q] F - Oddly Similar 考察 O(2000^3)をどうbitsetにしようか、という思考を最初から最後まで考えていた。どうまとめればいいかわからなかった。 解説ACを具体的に処理する。 1. まずj列を固定して考える 2. i(0 <= i < N) 行を探索する。 用意するbitsetは2つで、 tmp: maxA * maxN の二次元配列データ。j列目だけを見た時に、どの行とどの行が似ているかを、Aごとに管理。 is_odd: maxN * ma

          syamashi

          [ABC348] F - Oddly Similar

          syamashi

          [ABC348] E - Minimize Sum of Distances

          [Q] E - Minimize Sum of Distances 考察 1. とりあえず0を根とした場合の、f(0)のスコアを求める。 2. 0の子供1がいて、1に移動した場合のスコアは、なんらかの差分計算で求められそう。何の差分をとればいい？ 3. 子供1に近づいた場合、子供1以下のCの総和だけスコアが下がることが分かる。また、逆に子供1に属さない頂点のCの総和だけスコアが上がってしまう。 4. ということは、 子供1以下のCの総和 > 全体Cの総和 / 2 なら、子供

          syamashi

          [ABC348] E - Minimize Sum of Distances

          syamashi

          [ABC348] D - Medicines on Grid

          [Q] D - Medicines on Grid 普通にBFSを考える 考察 1. DP[i][j] = マス(i, j)に到達したときの最大エネルギーとして管理するとよさそう。 2. 薬を入力するときに、DP[i][j]に薬の値をいれてみる。 3. 最大値の更新があったときに進む、だけだとうまくいかない。 入力で受けた薬マスに入らない判定になってしまうので、到達したかどうかの判定seen[i][j]を用意すればよさそう。 4. マスに進む条件を次の2つにしてAC。 a

          syamashi

          [ABC348] D - Medicines on Grid

          syamashi

          [MC Digital プログラミングコンテスト2024] AHC031

          暫定57位->システス58位でした。 https://atcoder.jp/contests/ahc031/submissions?f.User=merhorn ペナルティが2種類あって 1. 予約面積に足りない場合はarea_cost * 100のペナルティ 2. パーティションを消す/設置する場合は、距離のline_cost * 1がペナルティ 明らかに1.が重たいので、最初の目標はarea_costを0にすることにします。 1日目 とりあえず簡単に実装したいと思

          syamashi

          [MC Digital プログラミングコンテスト2024] AHC031

          syamashi

          [ARC173] B - Make Many Triangles

          [Q] Make Many Triangles 考察 1. N <= 300と少ない。O(N^2)くらい計算できる 2. 同一直線上にある点集合Xと、そうじゃない点集合Yがわかればうれしい。 3. Xの3点を結んだ3角形は直線になってしまうからいけない。どこか1つでもYの点を組み合わせれば3角形が作れることが分かる。 4. Xの最大数を求めたら、YはN - {Xの個数}で求まる。 5. 答えはmin(N / 3, Y)になる。 XがたくさんあればYの個数だけ三角形が作れるし

          syamashi

          [ARC173] B - Make Many Triangles

          syamashi

          [ARC173] A - Neq Number

          [Q] A. Neq Number BよりもAのほうが難しかったように思う。 考察 0. 数え上げる状況が複雑なので、わかることから詰めていきたい 1. まず何桁になりそうか考える。 1-9: 9通り01-99: 90通り ... 99 - {11, 22, 33, ..., 99} = 90通り。001-999: 819通り ... 0XX は 上の行で求めた90通り。 1XX は 9 * 9 = 81通り。10の位のXには1以外が入

          syamashi

          [ARC173] A - Neq Number

          syamashi

          [ABC343] F - Second Largest Query

          [Q] Second Largest Query 全然わからなかった…。これ1600人解けるのすごいね。 俺はACL使っていないのでテンプレートを調整してます。 考察 ・セグ木を魔改造すればよさそう ・どんな値を持てばいい？ -> {max, max_cnt, 2nd_max, 2nd_cnt}の4要素で管理すればいい ・2つを統合するときには、上位2つの値と個数を調べる。 実装 ///////////// セグ木class RangeMax{public: ll

          syamashi

          [ABC343] F - Second Largest Query

          syamashi

          [第二回日本最強プログラマー学生選手権] 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

          syamashi

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

          syamashi

          [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

          syamashi

          [ARC170] B - Arithmetic Progression Subsequence

          syamashi

          [ARC170] A - Yet Another AB Problem

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

          syamashi

          [ARC170] A - Yet Another AB Problem

          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パターンを網羅した

          syamashi

          [AGC065] Shuffle and mod K

          syamashi

          [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,

          syamashi

          [ABC331] F - Palindrome Query

          syamashi