【C#】ABC367 C問題のみ備忘録

探索の必要があるものの制約はさほど大きくなく計算してみても最大5⁸=390625程度、であれば全列挙した上で条件に合わないものを弾けばいい。

全列挙するには再帰か、QueueやStackをWhileでぶん回す、全部ループを書くなどがあるが、どれでも通るので自分が書きやすい方で。

解説
1. 数列の辞書順
感想

解説

この問題における難しさは配列の全列挙を書けるかに集約される。

ただ全部列挙するのではなく、各要素Riの上限を守り、その上で辞書順で出力すること。

言い換えれば配列のコピーをたくさん作る必要があるので、そういうコードをきちんと書けるかが問われる。

C#における再帰とBFS・DFSの書き方は以下の2つを参考に。

【C#】再帰ってどうやって書けばいいんだ？となった時に読む記事

再帰の書き方に苦手意識を持つ全ての初心者プログラマを救済すべく書き上げました。嘘です。苦手意識を持ってたのは私です。使用環境はC#13.0、.NET 10.0。もしVisual Studioに「このバージョンでそんな書き方できネーヨ」と怒ら...

【C#】BFS・DFSを実装する

BFS（幅優先探索）とDFS（深さ優先探索）を実装する力を身につけるための記事です。「概念は分かってんだよ」という人のためにそこの説明は軽くやっておしまいです。枝切り（枝刈り）探索についてはここでは扱いません。記事内のコードのバージョンはC...

公式解説には再帰であれば並び替えの必要がない書き方をしているが、R_iを1からR_nまでとして列挙を始めるならQueueを使っても並び替えの必要はなく辞書順に揃う。

Stackは試してないけど恐らく並び替えの必要はあるはず。

数列の辞書順

数列の辞書順について数学仕草を以て解説されているが、これは一般的な辞書順と同様であることの説明をしているだけ。

1番目は「愛（あい）」と「相槌（あいづち）」なら「愛」の方が先になるということで、

2番目も「相打ち（あいう―）」と「相槌」なら、「相打ち」の方が先になるということ。

このどちらかに当てはまれば左側が小さいことが分かるね、という話。つまり辞書順を考えるとき、それが日本語の場合でも数列の場合でも同じ考え方をしていいですよという前提が置かれている。

感想

ABで時間を掛け過ぎたことで回答できず、終了後にC問題を解こうとして考え方は間違ってなかったが、実装にあたって細かい部分の調べ物が多すぎて。
再帰しよう、BFS(幅優先探索)しよう、配列のコピーってどうすればいいんだっけ。
そんな基礎的な部分がネックになって解けるはずの問題も解けなかった。悔しい。
最初から効率を求めすぎなんだよな……もっとこう柔軟に考えたい、時には強引な解決方法でもいいんじゃないか。

考え方が合ってても「これどうやって実装するんだっけ」とコードレベルの経験値が不足しまくってる。それで点落としてりゃ世話ないね。