cyan が AtCoder で cyan になるまで

目次

この記事に書いてあること

レートのグラフを見ればわかる通り、2021年の夏から2023年の頭までコンテストに出てませんでした。精進もほぼしておらず、実質休止期間です。

復帰して以降 について、

を書きます。ちなみに 言語は C++ を使っています。

なんで休止以前を省くかって言うと、あんま意味なさそうだからです。

この辺も別の記事でそのうち話せればと思いますが、2021年に入緑しているものの、大した知識はなかったです。

覚えている範囲だと、学んでいたのは BFS、DFS、二分探索、尺取法、imos法、ダイクストラ法 とかそんな感じだったと思います。学んでいたと言っても、触れたことがある程度だったと思います。

difficultyが年間50くらい厳しくなってるという話もあるらしく、休止前の話はレベル感を考えてもあまりアテにできないかなと思っております。緑になれたのも、ABC-C までの早解きがそこそこ得意だったからというだけですし。

そんなわけで、休止前の話はまた別の機会に。

環境の整備

コーディング環境

実は休止期間前までは AtCoder のコードテストしか使ってませんでした。復帰して1か月ぐらいでしたかね、なんとなく「プログラマとして飯食ってるのに手元に環境構築もできないのヤバくないか？」という不安もあり、ローカル環境の整備をしようということになりました。具体的にやったことは、

です。

構築に当たっては こちら に大変お世話になりました。コンピュータへの理解よわよわマンとしては1から10まで説明してくれるこの記事が非常にわかりやすくありがたかった記憶があります（それでもトラブってある程度手間取りましたが……）。

breakpoint を用いた debug は業プロでもよくやりますし、これできるようになったのが一番嬉しかったかもしれないですね。あとはシンタックスハイライトとか、インデントの設定できるとか、補完が効くとか、まあそんなぐらいです。

ブラウザ プラグイン

AtCoder Easy Test と ac-predictor を入れました。

前者に関しては atcoder-tools とか atcoder-cli & online-judge-tools を使ってもいいのでしょうけど、現状がそこそこ快適なのでなおざりにしております……

テンプレート整備

休止前は

#include <bits/stdc++.h>
using namespace std;

しか使っていませんでした。

今は

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
const int INF = 1001001001;
const ll LINF = 3001001001001001001;
const int MOD = 998244353;
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define all(a) (a).begin(), (a).end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template <typename T> istream &operator>>(istream &is, vector<T> &v) {for (T &in : v)is >> in;return is;}

を使ってます。ll と rep は特に使用頻度が高いです。

解いた問題

復帰後～入水までの間に解いた問題の内、difficulty が茶色以上のものを抽出しました。精進の指針の一端でも担えればと思います。

2023-03
● D. Tying Rope
● C. Max - Min Query
● D. FizzBuzz Sum Hard
● E. 2xN Grid
● D. Lucky PIN
● D. Three Days Ago
2023-04
● D. M<=ab
● C. Don’t be cycle
● C. Scc Puzzle
● C. Ladder Takahashi
● C. Super Ryuma
● C. Simple path
● C. Martial artist
● C. Index × A(Continuous ver.)
● C. Path Graph?
● C. Changing Jewels
● D. Find by Query
● C. Cross
● D. AABCC
● C. Scc Puzzle
● D. Divide by 2 or 3
2023-05
● D. FG operation
● E. Transitivity
● C. Chinese Restaurant
● D. Road to Millionaire
● C. Robot Takahashi
● D. Destroyer Takahashi
● D. Sum of Divisors
● C. Connect 6
● C. Inserting 'x'
● B. 迷子のCDケース
● B. Many 110
● C. Cards Query Problem
● C. Choose Elements
● C. Collision 2
● D. "redocta".swap(i,i+1)
● C. Rotation
● C. Connect Cities
● C. Slot Strategy
● D. Flipping and Bonus
● B. Kleene Inversion
● D. Insertion
● A. ><
● B. ヘイホー君と置き換え
● A. Dial Up
● C. XX to XXX
● D. Bitmask
● D. Scope
● E. Find Permutation
● D. Writing a Numeral
● C. Jumping Takahashi
● E. Kth Takoyaki Set
● C. Almost Equal
● D. Impartial Gift
● E. Isolation
● C. Almost Equal
● A. Make 10
● D. Cylinder
● D. Change Usernames
● D. Happy New Year 2023
● C. Rotate and Palindrome
● C. Dash
● D. Shift vs. CapsLock
● D. Cutting Woods
● A. AtCoder Group Contest
● B. New Place
2023-06
● B. DNA Sequence
● D. Prefix K-th Max
● E. Good Graph
● D. A Piece of Cake
● C. 1111gal password
● D. 250-like Number
● D. Trophy
● D. Wandering
● D. Root M Leaper
● D. Polynomial division
● D. Match or Not
● D. Sleep Log
● D. I hate Factorization
● B. Number Box
● D. Grid Coloring
● C. Adjacent Swaps
● C. Just K
● E. Sorting Queries
● D. Index Trio
● D. Poisonous Full-Course
● E. Best Performances
● D. Strange Balls
● C. おいしいたこ焼きの売り方
● D. Teleportation
● D. Collision
● D. Mismatched Parentheses
● E. Distinct Adjacent
● C. Ideal Sheet
2023-07
● D. Snuke Maze
● C. Standings
● E. MEX
● F. Vouchers
● E. Small d and k
● D. Jumping Takahashi 2
● C. 説明会
● A. Ekiden Race
● C. K Swap
● D. Weak Takahashi
● C. Filling 3x3 array
● D. LR insertion
● D. Union of Interval
● D. All Assign Point Add
● D. Neighbors
● E. Crested Ibis vs Monster
● D. Prediction and Restriction
● D. Iroha and Haiku (New ABC Edition)
● D. Add One Edge
● E. Family and Insurance
● D. Add One Edge
● D. Peaceful Teams
● E. NAND repeatedly
● D. Logical Expression
● D. Moves on Binary Tree
● D. Online games
● D. Takahashi's Solitaire
● C. 高橋くんと魔法の箱
● D. Even Relation
● E. Bomber
● B. あみだくじ
● D. Multiply and Rotate
● A. C-Filter
● C. 高橋君の給料
● A. 掲示板
● D. Xor Sum 4
● C. Find it!
● D. Grid Ice Floor
● E. Defect-free Squares
● C. Find it!
● E. Defect-free Squares
● D. Pond
● D. Hachi
● C. 高橋くんのバグ探し
● D. Happy Birthday! 2
● C. Graph Isomorphism
● D. Friends
● D. Sum of difference
● C. Switches
● C. Invisible Hand
● D. Count Bracket Sequences
● D. Coprime 2
2023-08
● F. Cans and Openers
● D. Money in Hand
● D. 2-variable Function
● C. Product and GCD
● C. Stones
● D. I Hate Non-integer Number
● D. Nowhere P
● C. Approximate Equalization 2
● D. Odd or Even
● D. Snuke Prime
● C. Many Requirements
● D. Index × A(Not Continuous ver.)
● D. Yet Another Recursive Function
● D. Do use hexagon grid
● D. ±1 Operation 2
● D. Takahashi Tour
● D. Water Bottle
● D. Rectangles
● D. Freefall
● D. Range Count Query
● D. Count Interval
● D. Longest X
● D. Play Train
● D. Querying Multiset
● D. Number of Shortest paths
● D. RGB Triplets
● D. LOWER
● D. Gathering Children
● C. Dice Sum
● C. Counting Squares
● C. Ladder Takahashi
● C. IPFL
● E. Red Scarf
● C. Matrix Reducing
● E. Karuta
● E. Akari
● C. Snuke Festival
● C. オセロ
● C. Many Formulas
● C. Strange Bank
● C. Linear Approximation
● D. String Equivalence
● D. Lamp
● E. Mex Min
● D. Strange Lunchbox
● E. Get Everything
● E. Subtree K-th Max
● D. Card Eater
● C. 数列ゲーム
● E. Amusement Park
● A. 塗り絵
● B. 解像度が低い。
● A. 動く歩道
● B. 謎のたこ焼きおじさん
● C. 民族大移動
● D. 乱数生成
● C. 柱柱柱柱柱
● C. 飛行機乗り
● D. 画像処理高橋君
● D. Integer Cards
● C. GCD on Blackboard
● D. Wall
● D. バスと避けられない運命
● D. 高橋くんと木の直径
● C. 列
● C. Daydream
● C. Back and Forth
● D. Enough Array
● E. Prerequisites
● C. スフィンクスのなぞなぞ
● C. Boxes and Candies
● C. Digits in Multiplication
● C. Dubious Document 2
● C. Bridge
● D. Walk and Teleport
● D. Transit Tree Path
● D. Coloring Dominoes
● D. joisino's travel
● D. Binomial Coefficients
● C. K-th Substring
● D. Equals
● D. 派閥
● D. Make Them Even
● D. Grid Repainting
● D. Remainder Reminder
● D. An Invisible Hand
● C. One-stroke Path
● C. Special Trains
● D. 2017-like Number
● C. Tsundoku
● C. Remembering the Days
● D. President
● E. Avoid Eye Contact
● D. KAIBUNsyo
● E. MST + 1
● C. Ideal Sheet
● D. Unique Username
● E. Erasing Vertices 2
● D. Summer Vacation
● C. Candles
● D. Robot Arms 2
● D. Circumferences
● D. Partition
● C. Pyramid
● D. Distinct Trio
2023-09
● E. Sequence Decomposing
● C. Blue Spring
● E. Sandwiches
● D. General Weighted Max Matching
● F. Octopus
● B. おとぎの国の高橋君
● D. Minimum Width
● C. False Hope
● E. Bus Stops
● E. Least Elements
● D. Digits Parade
● D. Pair of Balls
● C. Shapes
● E. Destruction
● D. Between Two Arrays
● D. Restricted Permutation
● D. Dance
● D. Journey
● D. AND and SUM
● D. Relative Position
● C. Slot Strategy 2 (Easy)
● E. Somen Nagashi
● E. Arithmetic Number
● E. Graph Destruction
● E. Fraction Floor Sum
● E. Ranges on Tree
● D. 射撃王
● E. Σ[k=0..10^100]floor(X／10^k)
● E. Distance Sequence
● E. Nearest Black Vertex
● C. HonestOrUnkind2
● D. Maze Master
● C. 321-like Searcher
● D. Set Menu
● E. Complete Binary Tree
● D. Dice in Line
● D. Lunlun Number
● F. #(subset sum = K) with Add and Erase
● F. Shortcuts
● D. Katana Thrower
● C. Triangular Relationship
● E. Product Development
2023-10
● D. Polyomino
● F. Vacation Query
● E. Transition Game
● D. Max Multiple
● D. Merge Slimes
● E. Playlist
● D. Shortest Path Queries 2
● D. Sequence Query
● D. Linear Probing
● C. Product
● C. ±1 Operation 1
● C. X drawing
● C. Error Correction
● D. Square Permutation
● E. Joint Two Strings
● C. Iroha's Obsession
● D. Menagerie
● C. Chocolate Bar
● D. Unbalanced
● C. Shopping Street
● D. Decayed Bridges
● D. Hanjo
● C. Sensors
● E. Our clients, please wait a moment
● D. Printing Machine
● F. Sensor Optimization Dilemma
● D. Preparing Boxes
● D. AtCoder Express 2
● D. Wizard in Maze
● C. Synthetic Kadomatsu
● D. Snuke's Coloring
● D. Mixing Experiment
● D. ABC Puzzle
● E. Revenge of "The Salary of AtCoder Inc."
● D. 3N Numbers
2023-11
● D. Good Tuple Problem
● E. Maximize Rating
● D. National Railway
● E. Queen on Grid
● D. Knight
● D. Lazy Faith
● D. Coloring Edges on Tree
● D. Islands War
● D. Take ABC
● E. Modulo MST
● F. Good Set Query
● D. Five, Five Everywhere
● C. 2D Plane 2N Points
● E. Max-Min Sums
● E. Dist Max
● D. Friend Suggestions
● D. Handstand 2
● E. Flatten
● D. Practical Skill Test
● E. 1 or 2
● D. Recording
● D. Patisserie ABC
● D. Good Grid
● D. Leaping Tak
● E. Simple String Queries
● D. Rain Flows into Dams
● D. Ki
● E. Come Back Quickly
● D. Counting Ls
● C. Minimize Abs 2
● E. Mex and Update
● E. Skiing
● D. Multiple of 2019
● D. Face Produces Unhappiness
● E. Strings of Impurity
2023-12
● E. Blackout 2
● E. Set Meal
● D. Tile Pattern
● E. Set Meal
● D. Takahashi Unevolved
● D. Sum of Large Numbers
● E. Logs
● D. Bouquet
● E. Red andgreen Apples
● E. Last Rook
● D. Redistribution
● D. 8 Puzzle on Graph
● D. Poker
● D. Swapping Puzzle
● E. A Gift From the Stars
● D. Blue and Red Balls
● E. Colorful Blocks
● D. Handstand
● D. Simple Knapsack
● E. Transformable Teacher
● D. Erase Leaves
● E. Takahashi Quest
● C. ABC conjecture
● D. Project Planning
● E. Rotation Matching
● E. Traveling Salesman among Aerial Cities
● E. Sugoroku 4
● B. Christmas Trees
● C. Socks 2
● D. Reindeer and Sleigh
● E. Christmas Color Grid 1
2024-01
● F. Silver Fox vs Monster
● E. Traveler
● E. Count Median
● E. Traveling Salesman among Aerial Cities
● E. Magical Ornament
● E. Bishop 2
● F. Teleporter and Closed off
● F. Regular Triangle Inside a Rectangle
● D. Draw Your Cards
● D. Not Divisible
● E. This Message Will Self-Destruct in 5s
● C. Repsept
● E. Grid Filling
● E. Round Trip
● E. Crystal Switches
● E. Train
● E. Count Simple Paths
● E. Souvenir
● E. Unique Color
● E. Peddler
● E. Sequence Sum
● B. log
● C. Loong Tracking
● D. Loong and Takahashi
● F. Sugoroku
● E. Non-Decreasing Colorful Path
● E. Dividing Chocolate
● E. Art Gallery on Graph
● D. equeue

精進で意識していたこと

前述の通り、解く速度に関してはそんなに課題を感じていなかったので、とにかく解ける問題を増やす方向で考えていました。方針が見えなくても、なんとなく思考が進む限り、どれだけ短くとも30分-1時間ほどは考えていたと思います。

特に適正 difficulty よりも高い問題の内、行けそうで行けない、でもちょっと行けそう、みたいな問題は数日間頭の中に置いておくこともありました。途中で、まったくどん詰まりになったら解説を見ます。

そのとき、解説に書いてある解法が頭をかすりもしていなかった場合、それを新たに武器として取り入れるだけなので、話は割と単純です。その解法に関する知識をｇｇるなり何なりして、取り入れます。次回から考察時に選択肢として頭の片隅に置いておけるようになってさえいればよいです。

大変なのは、その解法が頭に一旦浮かんだにもかかわらず、その方針で詰めずに捨ててしまった場合です。なぜその方針を捨ててしまったのかを顧みる必要があります。ex. 計算量の見積りを間違えた、正当性の証明ができなかった、何となくダメそうだから捨てた、等々。

そしてその原因が、問題文の誤読や勘違いによるものであればまだいいのですが、アルゴリズムやデータ構造に関して何らかの勘違いをしていた場合、ちゃんと矯正する必要があります。これまたｇｇるなり何なりして、当該アルゴリズム/データ構造のお気持ちをちゃんと理解する方向で頭を使います。

100% の理解が無理でも、最悪そのアルゴリズム/データ構造の各操作の計算量がいくつなのか/どのようなことが実現できるのかぐらいは理解するようにしてました。

学んだこと

アルゴリズム

他にもありそうな気がしますが、覚えてる範囲だとこれぐらいです。

実装手法

その他概念とか

ライブラリ化したもの

学んだアルゴリズムも踏まえて、手元にライブラリとして置いたものを紹介します。

他にも、BFS、DFS、めぐる式二分探索 なども一時期ライブラリ化していましたが、水色になる頃には何の苦労もなくその場で書けるようになっていたので、捨ててしまってました。

ACL で使えるようになったもの

AtCoder Library の中で使えるようになったものを紹介します。

学ばなかったこと

改めて文字に起こしてみると、知らないことだらけですね。「今のところ困ったことがない」と言っているものに関しては、単純に自分の精進不足も大いにあると思います……。

全然わからないもの

何ができるかなんとなく知ってるけど今のところできなくて困ったことがないもの

代替手段が存在して今のところ困ったことがないもの

学ぼうとしたけどわからなくて一旦諦めたもの

水色になった今、何をやっているか

特に変わったことをやっているわけでもないのですが、水 diff 埋めを積極的にやるようになりました。AtCoder Problems の heat map を見てみるとこんな感じです。

あと手元のライブラリが若干増えており、

あたりを窃盗しました。使うこと自体はそんなに多くないですが、持ってると貼るだけがたまに発生します。

おわり

良い締めが思いつかないです。青目指して？気長にがんばろうと思います。まあ、そんな感じです。
ありがとうございました。

ホームへ戻る