A. Déjà Vu / Дежавю (500点) 入力 出力 入出力例 注記 B. Flip the Bits / Меняем биты (1000点) 入力 出力 入出力例 注記 C. Balance the Bits / Сбалансируйте биты (1750点) 入力 出力 入出力例 注記 D. 3-Coloring / 3-раскраска (2000点) 相互入出力 …

微減...。問題文和訳はこちら A. GCD Sum (500点) B. Box Fitting / Коробка (1000点) C. Planar Reflections / Отражения от плоскостей (1750点) D. Bananas in a Microwave / Бананы в микроволновке (2500点): 未提出 E. Two Houses / Два дома (2500点)…

A. GCD Sum (500点) 入力 出力 入出力例 注記 B. Box Fitting / Коробка (1000点) 入力 出力 入出力例 注記 C. Planar Reflections / Отражения от плоскостей (1750点) 入力 出力 入出力例 注記 D. Bananas in a Microwave / Бананы в микроволновке (2500…

AtCoder Regular Contest 116でレート微増しました A - Odd vs Even (300点) B - Products of Min-Max (400点) C - Multiple Sequences (500点) 0個目を考える 計算する(数学的帰納法) D - I Wanna Win The Game (600点) E - Spread of Information (800点、…

AtCoder Beginner Contest 197（Sponsored by Panasonic）に参加。微増しましたがHighest更新ではありませんでした。 A - Rotate (100点) B - Visibility (200点) C - ORXOR (300点) D - Opposite (400点) E - Traveler (500点) F - Construct a Palindrome …

青に復帰しました。問題文和訳はこちら A. Strange Table / Странная таблица B. Partial Replacement / Частичная замена C. Double-ended Strings / Двусторонние строки D. Epic Transformation / Эпическая трансформация 一番多いのが過半数の場合 そう…

A. Strange Table / Странная таблица 入力 出力 入出力例 B. Partial Replacement / Частичная замена 入力 出力 入出力例 C. Double-ended Strings / Двусторонние строки 入力 出力 入出力例 D. Epic Transformation / Эпическая трансформация 入力 出力…

A. Prison Break / Побег (500点) 入力 出力 入出力例 注記 B. Restore Modulo / Восстановление модуля (1250点) 入力 出力 入出力例 C. Basic Diplomacy / Базовая дипломатия (1500点) 入力 出力 入出力例 D. Playlist / Плейлист (2000点) 入力 出力 入…

AtCoder Beginner Contest 196に参加。レートが1700以上に回復しました。 A - Difference Max (100点) B - Round Down (200点) C - Doubled (300点) D - Hanjo (400点) E - Filters (500点) $ t_i = 1 $ のとき $ t_i = 2 $ のとき $ t_i = 3 $ のとき F - S…

A. Domino on Windowsill / Домино на подоконнике 入力 出力 入出力例 注記 B. Binary Removals / Двоичные удаления 入力 出力 入出力例 注記 C. Minimum Grid Path / Минимальный путь на поле 入力 出力 入出力例 注記 D. The Number of Pairs / Количес…

A. Meximization / Мексимизация (500点) 入力 出力 入出力例 注記 B. M-arrays / M-массивы (750点) 入力 出力 入出力例 注記 C1. k-LCM (easy version) / k-НОК (простая версия) (750点) C2. k-LCM (hard version) / k-НОК (сложная версия) (500点) 入力…

2問しか解けなかった... A - Not coprime (300点) B - Special Subsets (400点) C - Sequence Scores (600点): 未提出 D - Moving Pieces on Line (600点): 未提出 E - Paper Cutting 2 (700点): 未提出 F - Permutation Division (900点): 未提出 結果、感…

A. Alexey and Train / Леша и поезд (500点) 入力 出力 入出力例 注記 B. Napoleon Cake / Торт Наполеон (1000点) 入力 出力 入出力例 C. Going Home / Поеду домой (1750点) 入力 出力 入出力例 注記 D. Two chandeliers / Две люстры (1750点) 入力 出力…

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）でレートを冷やしてしましました... A - Health M Death (100点) B - Many Oranges (200点) C - Comma (300点) D - Shipping Center (400点) E - Lucky 7 Battle (500点) F - Digits P…

A. Split it! / Раздели! (500点) 入力 出力 入出力例 注記 B. Max and Mex / Max и Mex (1000点) 入力 出力 入出力例 注記 C. Diamond Miner / Добытчик алмазов (1500点) 入力 出力 入出力例 注記 D. Let's Go Hiking / Идем в поход! (2000点) 入力 出力 …

競技プログラミングでは を用いた数え上げ問題が頻出します。このとき途中で割り算を用いますが、計算途中のオーバフローを避けるためモジュラ逆数というものを使いますが、このモジュラ逆数はFermat*1の小定理やEuler*2の定理といったものを利用して計算さ…

Carmichael*1函数はCarmichaelの定理に出てくる函数ですが、逆にこれ以外では出てこないと思います。しかし、定義が少し煩雑であるのと、この函数が返す値がEuler*2のトーシェント函数の与える値の約数になっていることについての証明をしたいので1つの記事…

A. Anti-knapsack / Антирюкзак (750点) 入力 出力 入出力例 B. Planet Lapituletti / Планета Лапитулетти (1250点) 入力 出力 入出力例 注記 C. K-beautiful Strings / K-красивые строки (1750点) 入力 出力 入出力例 注記 D. GCD of an Array / НОД масс…

AtCoder Beginner Contest 194に参加し、レートが1727まで上がりました。 A - I Scream (100点) B - Job Assignment (200点) $ O(N \log N) $ 解 $ O(N) $ 解 決め打ちによる解法 それまでの最小値を記憶しておく解法 C - Squared Error (300点) D - Journey…

Euler*1のトーシェント函数*2とは主に と表記される、整数論における函数です。次のように定義されます。 $$ \varphi(n) = \#\{k \mid 1 \leq k \leq n,\ \gcd(n,\,k) = 1\} $$ 日本語で書くと から までの整数のうち、 と互いに素な整数の個数となります。 …

A. ABC String / Строка ABC 入力 出力 入出力例 注記 B. Berland Crossword / Берляндский кроссворд 入力 出力 入出力例 注記 C. 1D Sokoban / 1D Сокобан 入力 出力 入出力例 注記 D. Dogeforces 入力 出力 入出力例 注記 E. A-Z Graph / A-Z граф 入力 …

ABC193のE問題は連立合同式についての問題でした。これは中国式剰余定理によって解を求めるものです。他にも拡張Eulerの定理についての証明においても中国式剰余定理は登場します。 名前と背景 定理の主張 証明(互いに素、二元のとき) 解の存在 解の一意性 …

A. K-th Largest Value / K-е наибольшее (500点) 入力 出力 入出力例 注記 B. Minimal Cost / Минимальная стоимость (750点) 入力 出力 入出力例 注記 C. Pekora and Trampoline / Pekora и батуты (1000点) 入力 出力 入出力例 注記 D. Zookeeper and The…

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)に参加しました。2回目の黄色パフォで、久しぶりにレートが暖まり、Highest附近にまで恢復しました。 A - Discount (100点) B - Play Snuke (200点) C - Unexpressed (300点) D - Poker …

A. Three swimmers / Три пловца (500点) 入力 出力 入出力例 注記 B. Card Deck / Колода карт (1000点) 入力 出力 入出力例 注記 C. Maximum width / Максимальная ширина (1500点) 入力 出力 入出力例 注記 D. Genius's Gambit / Ход гения (2250点) 入力…

ARC113のB問題は としたとき の列が4(の約数)の周期で循環すること、 の列が2(の約数)の周期で循環することを利用する問題でした。これらについては実際に実験して求めた人やFermatの小定理やEulerの定理によって説明しようとした人などがいました。しかしこ…

6問編成ARCで初めてDまで通ったのに... A - A*B*C (300点) 自分が通した解法 想定解 B - A^B^C (400点) C - String Invasion (500点) D - Sky Reflector (600点) $N = 1$のとき $M = 1$のとき 上のどちらでもないとき $A_i \gt B_j$となるような $(i,\,j)$ …

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)に参加しましたが、レートが冷えてしまいました... 悲しいね。 A - Star (100点) B - uNrEaDaBlE sTrInG (200点) C - Kaprekar Number (300点) D - Base n (400点) 自分が通した解法 解…

インタラクティブ問題があったため、当日は参加していませんが、環境を整えた後、問題を何問か通しました。 問題文和訳はこちら A. Shifting Stacks / Сдвигая стопки (500点、実行時間制限: 1 sec) B. Eastern Exhibition / Восточная выставка (1000点、実…

A. Shifting Stacks / Сдвигая стопки (500点) 入力 出力 入出力例 注記 B. Eastern Exhibition / Восточная выставка (1000点) 入力 出力 入出力例 注記 C1. Guessing the Greatest (easy version) / Найти наибольшее (простая версия) (750点) C2. Guessi…