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

    • [ABC376] Hands on Ring (Hard)

      [Q] Hands on Ring (Hard) 丁寧に場合分けをすれば確実にACできるはず！と思うものの、50分では間に合いませんでした/// 残念。 考察 1. 最小手数になりうる選択肢は、時計回りと反時計回りの2通りしかない。 a. B問題の(Easy)で実装した、LRをまたがずに移動する周り。（緑線） b. aと逆回りでLRどちらも移動する。（赤線） になる。 2. ターン毎にありえそうな状況をmap[{L, R}] = 最小手数 として管理すれば、3000ターン

      syamashi

      • [ABC368] G - Add and Multiply Queries

        [Q] G - Add and Multiply Queries 日立ヴァンタラプログラミングコンテスト2024。 Fで大量にWAを出して落ち込んでいる最中、EかGのどちらに進むか悩む。Eに行ってしまう。 Gがカスタマイズを要するセグ木に見えてひよったからだ。そうして大敗を喫する。 実際はBITとsetで事足りるのに。。 考察 1. クエリの回答が1e18までしか来ない。 2. つまり、配列Bに1,1,1,1,1…という箇所がたくさんあるはず。その箇所のAを累積和をとって

        syamashi

        • sort済みでない配列にlower_bound(upper_bound)をすると何が得られる？

          #include <bits/stdc++.h>using namespace std;int main() { vector<ll> V = {1, 9, 1, 9, 1, 9, 1, 9}; // 1 3 5 7 のどこかのindexがひっかかるはず。 auto it = lower_bound(V.begin(), V.end(), 2); cout << it - V.begin();} Q. 出力は何

          syamashi
        • 固定された記事

        Hello world

        syamashi

        マガジン

        • atcoder
          283本
        • 42tokyo
          33本

        記事

          [ARC182] B - |{floor(A_i/2^k)}|

          [Q] B - |{floor(A_i/2^k)}| 90分戦って5回WA出しながらなんとか通した、へとへと。 考察 サンプルをbitで出力して観察すると、ルールがわかる。 入力例3つ目 8 20 の出力をbitにしてみる1111 11001110010000011110 11000011010100011101 01011111110000101100 11010001101101011011 11101011101000111010 00011101100101011

          syamashi

          [ARC182] B - |{floor(A_i/2^k)}|

          syamashi

          [ABC363] F - Palindromic Expression

          [Q] F - Palindromic Expression 気づけばなんてことはなかった！ 考察 0. 素因数分解しちゃだめ！もっとシンプル。 1. A * B * 回文式 * B' * A' が回答の型になることを考える。 2. Nが回文なら回文式だけ出力して終わり。そうでない場合Aを求める。 3. Aの上限は√Nまで。O(√N)で全然間に合う。 4. AとA'が定まったらN->N/A/A'して、Nが小さくなる。 5. 新しいNが回文なら答え。そうでないならBを求める。

          syamashi

          [ABC363] F - Palindromic Expression

          syamashi

          [CodeQUEEN 2024 予選 (ABC 358)]F - Easiest Maze

          [Q] F - Easiest Maze 間に合いませんでした。40分くらい残して初全完がかかっていたのですが残念。 難しいけど、マイルール決めてお絵描きすればいいので、時間をかけて丁寧にやれば絶対できる問題だったなと思う。 考察 1. Noは2パターン a. 最小マスは直下でNマス。K < Nの場合No b. 最大を考える。ルートを変えることで消費マスが2増えるので、N + 2n消費できる。(K - N) % 2 == 1の場合No。 それ以外はYesなので、だいたいYe

          syamashi

          [CodeQUEEN 2024 予選 (ABC 358)]F - Easiest Maze

          syamashi

          [CodeQUEEN 2024 予選 ABC358] G - AtCoder Tour

          [Q] G - AtCoder Tour コンテスト終了時点でFastestCodeでした！ BFSでO(HM)の解法です。難しいことはしてません。 考察 1. KがHMより大きい場合、最大値のマスでひたすら待機をすることになりそう。 2. 毎ターン最大値max_Aを獲得できれば理想解を得られる。これを前提と考えると、 3. A -= max_Aとすれば、マスを損失値として管理できる。 4. BFSで、そのマスに到達するまでの最小損失と最小ターン数をメモする。 5. 解答

          syamashi

          [CodeQUEEN 2024 予選 ABC358] G - AtCoder Tour

          syamashi

          [ABC353] G - Merchant Takahashi

          [Q] G - Merchant Takahashi 2年に1回くらい見かけるConvex Hull Trick。拾えてうれしい。 考察 0. DP[index][今いる町] = 最大益 のDP[N][N]テーブルを使えば、答えはDP[N-1][0 ~ N-1]の最大値で求まる。 ところがO(N^2)でTLEしてしまう。どうにか高速化する必要がある。 初期値を考える。 まず町0にいるとしてDP[0] = 0でよい。町1 ~ Nまで無理やり移動すると、 DP[1] = D

          syamashi

          [ABC353] G - Merchant Takahashi

          syamashi

          [ABC353] E - Yet Another Sigma Problem

          [Q] E - Yet Another Sigma Problem 考察 0. Sが最大3e5文字の文字列が来るんだけど、なんと|S|の総和も3e5。 0. 1文字ずつ考えたとして、O(|S|log|S|)が間に合う。 1. とりあえず受け取った文字列を昇順にsortする 2. S="abcd"があった場合。 ・1文字の"a"がどれだけ合致しているかを考える。 it = lower_bound("b")をとれば、[S, it)の数だけaが合致している。 ・2文字の"ab"

          syamashi

          [ABC353] E - Yet Another Sigma Problem

          syamashi

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

          体験談なだけで、科学的な記事ではありません。 2024/0808追記 キシリトール自体に、虫歯予防効果がないかもしれません。 キシリトールガムが虫歯対策に有効な理由は、ガムをかむことによる唾液促進効果であって、キシリトールはその邪魔をしないだけ説が最新です。 お砂糖うんぬんではなくガムを噛むのがいいかもしれません。追記終 虫歯対策になる砂糖を試したくて、フラクトオリゴ糖を始めました。 フラクトオリゴ糖について、明治HPで虫歯にならない簡潔な理由が示されています。ただ、今回

          syamashi

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

          syamashi

          [ABC350] F - Transpose

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

          syamashi

          [ABC350] F - Transpose

          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

          [ABC214] F - Substrings

          syamashi

          [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