こんばんは、ぱそきいろです。
Atcoderの話をします。ブログでは初めて書きます。
D問題の解説とモチベーションを保つのは難しいよねという話をします。
ABC231 D問題
1 から N の番号がついた N 人を横一列に並べる方法のうち、以下の形式の M 個の条件全てを満たすものが存在するか判定してください。
条件：人 A iと人 B iは隣り合っている
シンプルな問題文だったものの、少し手惑いました。
解説にもあるのですが、以下の2点を満たすとYesと出力すればいいです。
- 3回以上登場する人がいない
- 並べたときにループが発生しない
3回以上登場する人がいないという点は、Counterを使って容易に判定できます。
ループに関してはUnion findを使いました。
条件に合うように隣り合うとするとグラフ構造になります。
N人のUnion find木を作成し、条件の隣同士のノードを結合していきます。
その際、結合前のノードの根が同じだとループになるため、Noとなります。
Union findはこちらを参考にしました。
【AtCoder】Pythonで使いこなすUnion-Find木 | amateur engineer's blog
提出したコードはこちらです。
Submission #27843253 - Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)
モチベーションを保つのが難しい
私のレーティング推移を載せます。
一年半ほど前からだらだらとコンテストに出ていますが、結果にムラがあります。
丸を付けてますが、一度緑になりそうでしたが、ちょっとコンディションが崩れるとそのまま下がり続けてしましました。。。
やっともう一回入緑しようとしています。
次こそはこのまま緑になりたいですね。
また需要があればAtcoderの記事載せます。
ありがとうございました。
