イバコの生存記録

いまは競プロ(AtCoder)記事がメインです。

105. 昨日解いた問題(2022.04.17)

問題一覧 D - Handstand (Diff: 1138) E - Train (Diff: 1135) D - Grid Components (Diff: 1445) E - Stronger Takahashi (Diff: 1423) 自分の解法など D - Handstand 24分。 連続で並ぶ 1 の数を増やす必要があるので、反転させる区間は全て 0 であるのが…

104. AtCoder参加記録(AtCoder Beginner Contest 248)

15回参加でレート 1035 です。 今回はパフォーマンス 1188 です。 ABCDを通して、FGExは未解答です。Eは通せず。 各問題の感想など。 A 2分6秒。 数列に分解して HashSet から除外して残ったものを出すようにしました。 B 2分2秒。 倍々ゲームなので早々に決…

103. 今日解いた問題(2022.04.15)

問題一覧 D - Lamp (Diff: 1103) E - Simple String Queries (Diff: 1443) 自分の解法など D - Lamp 12分。 累積和的な処理で解けないかな、と考えました。たとえば「#....#」となっている箇所は、「012340」という風に置き換えられます。これを、その場所に…

102. 今日解いた問題(2022.04.14)

本日より、問題を開いてから AC まで掛かったおおよその時間も記録しようと思います。 問題一覧 D - Harlequin (Diff: 1106) E - Colorful Blocks (Diff: 1442) E - Friendships (Diff: 1433) 自分の解法など D - Harlequin 8分。 各色のりんごの残りを 個と…

101. 今日解いた問題(2022.04.13)

問題一覧 D - Remainder Reminder (Diff: 1129) F - Programming Contest (Diff: 1423) D - Base n (Diff: 1425) 自分の解法など D - Remainder Reminder 入力例 1 で考えてみます。観察すると、 であることが分かります。よって、この範囲でそれぞれ が何通…

100. AtCoder参加記録(AtCoder Beginner Contest 247)

14回参加でレート 1014 です。ようやくレート補正期間が終わりました。 今回はパフォーマンス 1173 です。 ABCDを通して、EFGExは未解答です。初めて?のノーペナ。 各問題の感想など。 A としたあと 。 B 問題をパッと見てとりあえず Dictionary 使うっぽい…

99. AtCoder参加記録(AtCoder Regular Contest 138)

現状です。13回参加でレート 992 です(14回参加するまでレート補正期間中)。 ARCデビュー戦は惨敗でした。 今回はパフォーマンス 845 で、なかなかやらかしています(ワースト2)。 Aを通して、BはWAで、CDEFは未解答です。Aで3ペナです(ひどい)。 各問…

98. 今日解いた問題(2022.04.08)

今日も仕事が忙しかったので軽いものを2つ。ARC だからか、Diff にしてはやや難しい印象。どちらも発想問題でした。 問題一覧 A - Permutation Grid (Diff: 350) B - Shift and Reverse (Diff: 753) 自分の解法などA - Permutation Grid問題文を読むと、どう…

97. 今日解いた問題(2022.04.07)

仕事がかなり大変だったので、比較的解きやすい2問だけ…。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 A - Erase by Value (Diff: 265) B - Dividing Subsequence (Diff: 1317) 自分の解法など A - Erase by Val…

96. 今日解いた問題(2022.04.06)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 A - Bridge and Sheets (Diff: 247) B - Reserve or Reverse (Diff: 934) C - The Majority (Diff: 1560) 自分の解法など A - Br…

95. 今日解いた問題(2022.04.05)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 A - Floor, Ceil - Decomposition (Diff: 634) B - Sum of Three Terms (Diff: 1239) 自分の解法など A - Floor, Ceil - Decompo…

94. AtCoder参加記録(AtCoder Beginner Contest 246)

現状です。12回参加でレート 1012 です(14回参加するまでレート補正期間中)。 今回はパフォーマンス 1424 で、過去最高でした。 ABCEを通して、DFGExは未解答です。Eで1ペナです。 各問題の感想です。 A Aにしてはちょっと難しいです。 色々やり方はあると…

93. 昨日と今日解いた問題(2022.03.31)

昨日と今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 E - Mex Min (Diff: 1088) C - Align (Diff: 1095) D - Strange Lunchbox (Diff: 1085) E - Amusement Park (Diff:…

92. 今日解いた問題(2022.03.29)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 C - Linear Approximation (Diff: 1089) E - Get Everything (Diff: 1397) 2 問目が個人的に面白かったです。 自分の解法など …

91. 今日解いた問題(2022.03.28)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 F - Endless Walk (Diff: 1451) B - 細長いお菓子 (Diff: 1395 ※たぶんもっと低い) D - Christmas (Diff: 1088) 自分の解…

90. AtCoder参加記録(AtCoder Beginner Contest 245)

現状です。11回参加でレート 941 です(14回参加するまでレート補正期間中)。 今回はパフォーマンス 1144 でした。 ABCDを通して、EはWA、FGExは未解答です。Dで2ペナです。 各問題の感想です。 A 開始直後に問題一覧ページに飛ぶと何故か403エラーが出て、…

89. 今日解いた問題(2022.03.25)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 D - 8 Puzzle on Graph (Diff: 1376) D - An Invisible Hand (Diff: 1376) 自分の解法など D - 8 Puzzle on Graph 頂点数 、…

88. 昨日と今日解いた問題(2022.03.24)

昨日・今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 お酒が入ってるので変なこと書いてるかもしれません 問題一覧 085 - Multiplication 085(★4) (競プロ典型: ★4) 086 - Snuke's Fav…

87. 今日解いた問題(2022.03.22)

今日解いた問題についてまとめます。 自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。 問題一覧 E - Ranges on Tree (Diff: 1068) D - 高橋くんと木の直径 (Diff: 1378) D - Recording (Diff: 1383) 自分の解法など E - Ranges…

86. 今日解いた問題(2022.03.21)

今日解いた問題についてまとめます。自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。問題一覧 E - King Bombee (Diff: 1125) 082 - Counting Numbers(★3) (競プロ典型: ★3) 084 - There are two types of characters(★3) (…

85. AtCoder参加記録(AtCoder Beginner Contest 244)

現状です。10回参加でレート 909 です(14回参加するまでレート補正期間中)。 今回はパフォーマンス 932 でした。 ABCDを通して、EFGExは未解答です。悲しいミスにより、Cで1ペナです。 各問題の感想です。 A 久々にめちゃ簡単なA問題だったな、と思いまし…

84. ビット全探索について丁寧に見る

簡単な全探索を考える 唐突ですが、次のような問題を考えてみます。【問題 A】3 種類の硬貨 A, B, C が 1 枚ずつ存在します。A, B, C の価値はそれぞれ 2, 3, 5 です。これらの硬貨を組み合わせて、ぴったり支払える金額は何種類ありますか。ただし、1 枚も…

83. 最長増加部分列(LIS)の長さを算出するアルゴリズムを丁寧に見る

数列 の増加部分列(Increasing Subsequence)は、「全ての で を満たす部分列」と定義されます。この部分列は、元の数列から非連続で取ることができ、順番を変えてはいけません。 たとえば、「」という数列 の増加部分列の1つは、「」=「」です。 増加部分…

82. mod 逆元の算出方法とフェルマーの小定理について

昨日のABC F問題のように、既約分数(有理数)を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。 atcoder.jp この記事では 分数をなぜ整数として表現できるのか どうやってその値を算出するのか という辺りを丁寧にま…

81. AtCoder参加記録(AtCoder Beginner Contest 243)

前回は私用で出られなかったので2週間ぶりのABCです。 現状です。9回参加でレート 908 です。14回参加してないので若干低めのレートになっているようです(補正期間長い…)。 今回はパフォーマンス 1317 で、過去最高でした(水色パフォ)。 ABCDを通して、E…

80. 二分探索ライブラリの使い方を間違えてWAを生やしまくった話

ここ最近、以下の最長増加部分列(LIS)問題にやたらと手こずっていました。atcoder.jp LIS自体はアルゴリズムも理解して、この問題も解法が分かったのでササッと書いたのですが、何故かサンプルは通るものの他のテストケースの大半が落ちてしまいます。二分…

79. ライブラリにはランダムテストを追加したい話

一週間ほどプライベートの用件で競プロから離れていましたが、日常に戻ったので再開しています。 最近、ライブラリの不具合を疑う WA や RE に時々遭遇するようになりました。ただ、競プロではテストケースを見られないことも多いので、どのようなケースで落…

78. IComparable<T> を実装するなら IEquatable<T> も実装した方が良い

C# の話です。今日の仕事でよく分からないバグが発生し、調べていくとこれが原因だった…という経験談です。 不具合を調査していくと、独自に作成した「HogeKey」のようなクラスのインスタンスを HashSet に突っ込んでいた箇所で、何故か重複する要素が入って…

77. C# で MultiSet を実装する(大枠の話と列挙アルゴリズムについて)

ここで言う MultiSet とは C++ の multiset を模したデータ構造です。C# に標準で存在しないため、競技プログラミングなどで利用したい場合は自作する必要があります。 MultiSet が満たすべき性質 MultiSet は端的に言うと、順序を保ったまま高速に要素を追…

76. 2022年3月のマニフェスト

今月のやることリストです。今年の目標は以下の記事。 ibako-piyo.hatenablog.com 今月の学習テーマ 相変わらず仕事は繁忙期なため、仕事においてフリー学習はできないです。 プライベートでは、やはり競技プログラミングが楽しいので今月も引き続きこちらを…