ARC011 A, B, C 考察

arc011 A - 鉛筆リサイクルの新技術

m 本の使用済みの鉛筆から n 本の新しい鉛筆をつくって販売できる。最初 N 本を販売するとき最終的に何本の鉛筆を販売できるか。販売した鉛筆はすべて使用される。

1 回目の再利用を考える。 N 本が使用されて戻ってくる。 N >= m なら N / m * n 本の鉛筆を改めて販売できる。販売の総数は N + N / m * n になる。

2 回目は 1 回目の再利用の余りである N % m と改めて販売した N / m * n を合わせた N % m + N / m * n に対して >= m を調べて……と続ける。

n < m < N <= 1000 なので愚直にシミュレーションしても間に合う。

各単語は 30 文字で 1000 単語の単純置換なので愚直にシミュレーションしても間に合う。

母音のみからなる単語しかないときなどに改行を出力しそびれて 1 WA 。

各単語を頂点・ 1 文字違いの単語間の繋がりを辺とした無向グラフにおける最短経路・経路復元を実装できれば良い。

単語とそれ以外の単語を選び前から順に一致する文字数を数える O(N^2) 。単語数は 1000 で各単語は 30 文字なので 1000 * 1000 * 30 微妙だけど間に合うはず。最短経路・経路復元は O(N^2) 未満のはず。

first last 間のつながりを考慮しそびれて 1 WA 。

リングフィットアドベンチャーを続けている。

『ユースケース駆動開発実践ガイド』をざっと読んだ。今週中に改めて読む。