itsuki

会社の外でも通用する技術が欲しい組込み系ソフト屋です。数学と電気をのんびり学び直してい…

itsuki

会社の外でも通用する技術が欲しい組込み系ソフト屋です。数学と電気をのんびり学び直しています。格好つけているだけでギターは弾けません。鳥派です。
  • 固定された記事

自己紹介 p.0

初めまして、itsukiと申します。会社の外でも通用する技術が欲しい組込み系開発者です。よろしくお願いします。 それまで数学と名の付くものから極力逃げてきましたが、競技プログラミング（以下、競プロ）というネトゲ（個人の見解です）に出会ってしまい、遊び尽くすために数学を学び直しています。 noteの目的・競プロの問題に関する考察メモ ・アウトプットの練習 ・文章を書く練習 競プロの問題を解いた後に、自分の考察の流れをメモします。後日 振り返るための、個人的な備忘録になる予

itsuki

    • ABC046-D 備忘録 p.49

      itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れ全部グーを出したらどれだけ負けるか考える 相手がパーを出す数を、仮に p と置く 自分がパーを出せる最大数（仮に pmax と置く）は、手数 N ÷ 2 を切り捨てた値になる 相手がパーを出すときに自分もパーを出すことで、相手がパーを出すときは極力あいこにする それでもまだパーを出せるなら、相手がグーのときにパーを出して勝つ pmax - p が答え #include

      itsuki

      • ABC181-C 備忘録 p.48

        itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れ一次関数…！！！とても苦手 N <= 100 なので、for文を3重にしても大丈夫そう N 個の点の中の相異なる 3点が同一直線上にあるということは、点A, 点B を通るグラフと、点A, 点C を通るグラフの傾きが同じということ 全探索する！ 参考： #include <stdio.h>int main(){ int n, x[100]={0}, y[100]={0

        itsuki

        • ABC014-C 備忘録 p.47

          itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れimos 法か？ 適当な配列（例えば table[10^6] ）を用意して、取得のたびに table[a_i]++; table[b_i+1]--; していく 入力例1 の場合、すべてのアンケート情報をまとめると下記のようになる 　table[0] = 1 　table[1] = 0 　table[2] = 2 　table[3] = -1 　table[4] =

          itsuki
        • 固定された記事

        自己紹介 p.0

        itsuki

          ABC065-C 備忘録 p.46

          itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れ順列っぽい？ [1] 猿の数と犬の数の差が 2 以上あると どこかで 猿猿 もしくは 犬犬 になってしまうので、その場合は 0 [2] 猿の数と犬の数の差が 1 ならば、多い方を最初と最後に置くと、猿犬猿…犬猿 もしくは 犬猿犬…猿犬 になるので、 N! * M! [3] 猿の数と犬の数が等しければ、猿犬猿…犬 もしくは 犬猿犬…猿 になるので、( N! * M! ) +

          itsuki

          ABC065-C 備忘録 p.46

          itsuki

          AGC023-A 備忘録 p.45

          itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れかの有名な Zero-Sum Ranges に挑戦！累積和と知っている以上、すんなり AC 可能（予定） 累積和 -> ソート -> nC2 とさらっと書いて、サンプルも通ったので意気揚々と投げたところ WA… その後も WA を重ね、他の方々の解説やソースを見るも、さっぱり AC できず驚異の 21WA そしてついに AC！原因は、ソートするときの compare 関数オ

          itsuki

          AGC023-A 備忘録 p.45

          itsuki

          ABC199 参戦記録 p.44

          itsukiです。 AtCoder Beginner Contest 199 に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。ついにレート色が茶色になりました。 回答時間合計：71分08秒 パフォーマンス：714 考察の流れA - Square Inequality 最近 少し考えさせる A問題が多かった？ので、本当にそのまま書けばいいだろうか とちょっと戸惑う 素直にそのまま書く #include <stdio.h>#defin

          itsuki

          ABC199 参戦記録 p.44

          itsuki

          ABC197 参戦記録 p.43

          itsukiです。 AtCoder Beginner Contest 197 に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。 回答時間合計：87分17秒 パフォーマンス：740 考察の流れA - Rotate 文字列で受け取って、2文字目、3文字目、1文字目の順に出力する 初めて1分以内にACした…！（58秒） #include <stdio.h>int main(){ char s[4]={0}; scanf("%s"

          itsuki

          ABC197 参戦記録 p.43

          itsuki

          ABC196 参戦記録 p.42

          itsukiです。 AtCoder Beginner Contest 196 に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。 回答時間合計：82分10秒（3ペナ15分を含む） パフォーマンス：503 考察の流れA - Difference Max 最近よく見る(?)、それぞれに範囲が与えられた x, y を使って計算する問題 ABC178-B が頭をよぎったので、各範囲の境界を丁寧に調べる プラスマイナスに関わらず、( x 最大

          itsuki

          ABC196 参戦記録 p.42

          itsuki

          AHC001 参戦記録 p.41

          itsukiです。 AtCoder Heuristic Contest 001 に参戦した様子です。解説記事ではありません。 ヒューリスティックコンテスト（マラソン型コンテスト）に初めて参加しました。2021-03-06(土) 12:00 ~ 2021-03-14(日) 20:00 の間、自分が思いつく限りを試せたので満足です。 「Rust 言語で書かれたツール（入力ジェネレータ等）を提供します。」とのことだったので、当初は Rust 環境を整備したりしましたが、kenk

          itsuki

          AHC001 参戦記録 p.41

          itsuki

          CF #704 (Div. 2) 参戦記録 p.40

          itsukiです。 Codeforces # 704 (Div. 2) に参戦した様子です。解説記事ではありません。 結果は A の1完でした。B は 2回提出しましたが、Time limit exceeded から抜け出せませんでした。 回答時間合計：25分25秒 スコア：460 考察の流れA. Three swimmers 3人が泳いでいて、それぞれ a 分毎, b 分毎, c 分毎に左側に戻ってくる p 分以降 最初に左側に戻ってくる人を待つとき、何分待てばいいか

          itsuki

          CF #704 (Div. 2) 参戦記録 p.40

          itsuki

          SOMPO HD プログラミングコンテスト2021 (ABC192) 参戦記録 p.39

          itsukiです。 SOMPO HD プログラミングコンテスト2021 (AtCoder Beginner Contest 192) に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。 回答時間合計：63分42秒 パフォーマンス：294 考察の流れA - Star「次にご褒美をもらうためには、あと何枚？」なので、100 - (今までに集めたコインの枚数%100) で良さそう #include <stdio.h>int main(){

          itsuki

          SOMPO HD プログラミングコンテスト2021 (ABC192) 参戦記録 p.39

          itsuki

          ABC188 参戦記録 p.38

          itsukiです。 AtCoder Beginner Contest 188 に参戦した様子です。解説記事ではありません。 結果は A, B, C の 3完でした。 回答時間合計：26分45秒 パフォーマンス：662 考察の流れA - Three-Point Shot 「負けている側 + 3」の方が、「勝っている側」よりも大きい場合に Yes もうちょっと格好良く書けないかな？と一瞬迷ったけど、とりあえず解くことに集中… #include <stdio.h>#defi

          itsuki

          ABC188 参戦記録 p.38

          itsuki

          CF #691 (Div. 2) 参戦記録 p.37

          itsukiです。 Codeforces # 691 (Div. 2) に参戦した様子です。解説記事ではありません。 結果は A, B の 2完でした。初めてコンテスト中に 2問解けました！ 回答時間合計：72分30秒 スコア：1387 考察の流れA. Red-Blue Shuffle n <= 1000 だから、順列の全探索は無理そう 確率の値ではなく「どっちが勝つ確率が高いか」を求めればいい 1枚のカードに 2つの数字が書かれているので、各カードに書かれた数値の大

          itsuki

          CF #691 (Div. 2) 参戦記録 p.37

          itsuki

          ABC173-C 備忘録 p.36

          itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れ0行目を塗る or 塗らない、・・・、H行目を塗る or 塗らない 0列目を塗る or 塗らない、・・・、W列目を塗る or 塗らない 上記それぞれについて考えるので、bit全探索の入れ子？ （過去に書いた bit全探索のソースを引っ張り出してくる） 書いているうちに for文が 4重になってしまう 1 <= H, W <= 6 なので間に合うだろうけど、混乱する 特定の行

          itsuki

          ABC173-C 備忘録 p.36

          itsuki

          ABC137-C 備忘録 p.35

          itsukiです。 AtCoderの過去問を解いた様子です。解説記事ではありません。 考察の流れバケットに入れる？ でも s_i の長さは10文字固定だから、バケットに入れなくてもよさそう 各文字列を取得時にソートして、さらにすべての文字列を辞書順に並べる 同じ文字列の個数をカウントし、nCr する #include <stdio.h>#include <stdlib.h>#include <string.h>typedef long long ll;ll _nCr(

          itsuki

          ABC137-C 備忘録 p.35

          itsuki