実装練習と題されたバチャ（開催者は私ではありません）があったので解いてみました。また、実装ゲーとされるものがなぜつらくなるか、それを簡単にすればどうすればいいか、を考察し対策をまとめました。これらはすべてオレ流対策なので、
- わかりづらい
- むしろ考えることが増える
- かえってミスしやすい
といった批判も当然あるかと思われますが、何ががしかの参考になれば幸いです。
なぜ実装ゲーはつらいのか？
私が思う答え：変数がいっぱいあってネストも深くなるから
グリッドを全探索して更にある変数も全探索して～みたいな問題に典型的ですが、こういった問題は変数を i,j,u,v,p,q...と大量に用意する必要があります。いわゆる競プロらしい問題と違って、大量の変数がいる問題は、慣れてないと頭がバグりがちです。
また、ネストが深くなったり、非自明なネストが増えるのも問題です。
if 条件A:
if 更に特別な条件B:
return false;
return true;
else:
return false;
コーナーケースでこういう処理を要求されることは多いです。
それらへの対策を
- 全探索しなくていい条件（あれば）を見抜く
- 余計な変数を宣言しなくて済むようにする
- 番兵等を利用して余計な
ifをなくす - Python で短くコーディングできないか試す
という観点から解説していきたいと思います。
1. Batters
ソースコード（C++）
int main()
{
int n;
cin >> n;
vector<int> a(n);
cin >> a;
reverse(all(a));
int ans = 0;
int sum = 0;
rep(i, n)
{
sum += a[i];
ans += sum >= 4;
}
cout << ans << endl;
}
余計なループを回さない
問題文を丁寧にコードにすると $N \times N$ の二重ループになります。しかし、あるバッターの進塁数は自分を含む後続のバッターすべての進塁数を合計したものに気付くと、後ろからの累積和を取ればいいことに気づきます。
変数の使いまわし
累積和を別の配列として用意してから 4 以上の要素を数えてもいいですが、ans と sum を用意して逐次的に処理することにより簡潔に実装できます。直前の状態しか記憶しなくていいものはひとつの変数を使いまわしても大丈夫、というのは「余計な変数を宣言しなくて済むようにする」ルールにおいてかなり重要なテクです。
2. 1D Pawn
ソースコード（C++）
int main()
{
int n, k, q;
cin >> n >> k >> q;
vector<int> a(k);
cin >> a;
a.push_back(n + 1); // sentinel
while (q--)
{
int L;
cin >> L;
L--;
if (a[L] + 1 != a[L + 1])
{
a[L]++;
}
}
a.pop_back(); // sentinel
cout << a << endl;
}
番兵
問題文を丁寧にコードにすると「自分が列の最後にいる時」で余計な if 処理が必要となります。こういう時は番兵を使います。$N+1$ の位置に別のコマがいると仮定すると if 処理を省けます。
3. Cheese
ソースコード（C++）
int main()
{
int n;
ll w;
cin >> n >> w;
vector<pair<ll, ll>> AB(n);
rep(i, n)
{
ll a, b;
cin >> a >> b;
AB[i] = {a, b};
}
sort(all(AB));
reverse(all(AB));
ll ans = 0;
rep(i, n)
{
auto [a, b] = AB[i];
ll valid = min(w, b);
ans += valid * a;
w -= valid;
}
cout << ans << endl;
}
min/max で if を省略
ある数量 $a,b,c,...$ があって前から貪欲に合計 $x$ 個使い切りたいみたいな時。今見ている数量が使いたい量をオーバーするかどうかを if 文で判定してもいいですが、min を使うことでその分岐を減らすことができます。まあ、これは、多くの人が順当にこうするかなという感じですが。私はこの「最大限使える量」を valid （有効）と命名することが多いので、勝手に valid 法とか呼んでいます。
4. Split?
ソースコード（Python）
import re
def main():
s = input()
if s[0] == '1':
return 'No'
idx = {}
idx[1] = 3
idx[2] = 2
idx[3] = 4
idx[4] = 1
idx[5] = 3
idx[6] = 5
idx[7] = 0
idx[8] = 2
idx[9] = 4
idx[10] = 6
t = [0] * 7
for i in range(10):
t[idx[i+1]] |= (s[i] == '1')
u = ''.join(map(str, t))
pat = r'10.*?1'
res = re.findall(pat, u)
if len(res) > 0:
return 'Yes'
else:
return 'No'
print(main())
これはかなり実装ゲーという感じがしますw
分岐を配列として事前定義
まず、面倒くさいのはピンの位置がシーケンシャルではないことです。これを丁寧に if 分岐で処理するのはかなり大変です。そのため、「if 分岐をあらかじめ配列として定義しておく」 というテクを使います。コードを書く量はあまり変わりませんが、記述箇所が固まっているため、ミスに気づきやすく、後で修正もしやすいです。
正規表現
問題文の意図は「立っているピンが1 本以上存在する」列を 1、「ピンが全て倒れている列が存在する」列を 0 とした時に、1....0....1（間の 0 は一個以上連続している）という状態になっているか？ を問うていると言えます。こういった文字列の解析は正規表現により簡単に実装できます。Python だと特に使いやすいので、時に強力な武器になります。
5. NewFolder(1)
ソースコード（Python）
from collections import defaultdict
def solve(s: str, n: int) -> str:
if n == 0:
return s
else:
return f'{s}({n})'
n = int(input())
mp = defaultdict(int)
for i in range(n):
s = input()
print(solve(s, mp[s]))
mp[s] += 1
Pythonで文字列をピンポイントに処理
これまでに出てきた同じ文字列を連想配列で数えるのが問題の勘所ですが (1),(2) といった文字列を付加して出力するのも C++ だと微妙にめんどいです。Python の f-string はこういう、ピンポイントで文字列を整形したい時に便利です。 f'{s}({n})'といった形で、かなり直感的に書けます。
6. Better Students Are Needed!
ソースコード（Python）
n, x, y, z = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(zip(range(n), a, b))
c = sorted(c, key=lambda p: (-p[1], p[0]))
c[x:] = sorted(c[x:], key=lambda p: (-p[2], p[0]))
c[x+y:] = sorted(c[x+y:], key=lambda p: (-p[1]-p[2], p[0]))
c[:x+y+z] = sorted(c[:x+y+z], key=lambda p: p[0])
print(*[p[0]+1 for p in c[:x+y+z]])
Python で自由自在にソート
これについては cunitac さんのユーザー解説が天才すぎるのでほぼ丸写し。Python の sorted はキーをかなり自由に変えられので、これによって問題文をそのままコードにするかのごとく自由自在なソートができます。差し出がましくつけたしたポイントとしては、リスト内包表記や*アンパック記法を用いて for 文を省いています。
7. Knight Fork
ソースコード（C++）
string solve()
{
vector<int> dx = {-2, -2, -1, -1, 1, 1, 2, 2};
vector<int> dy = {1, -1, 2, -2, 2, -2, 1, -1};
map<pair<int, int>, int> mp;
rep(i, 2)
{
int x, y;
cin >> x >> y;
rep(d, 8)
{
if (++mp[{x + dx[d], y + dy[d]}] == 2)
{
return "Yes";
}
}
}
return "No";
}
int main()
{
cout << solve() << endl;
}
連想配列で必要な部分だけ記録
愚直に盤面を全探索するには大きすぎるので、一方のマスを中心として $5 \times 5$ マスを探索すればいいのが想定解。しかし、連想配列を使うことにより、そもそも盤面をメモリで確保しなくてもよくなります。このような発想は、振れ幅の大きい DP（動的計画法）でもよく使われており、私はそのような DP を個人的には連想配列 DP と呼んでいます。
この問題であれば、ある行き先が 2 以上のカウントを持った時点で Yes です。最大値は逐次的に更新されるので、後で連想配列全体を調べ直さなくても for ループ内で検出できます。
分岐を配列として事前定義
盤面ではなく行き先を中心に調べる場合、どこが行き先になるかを列挙する必要があります。これも、分岐を配列として事前定義することにより見通しを良くできます。このように、$x$ 方向と $y$ 方向の移動方向を事前定義しておくことは、BFS（幅優先探索）やダイクストラ法でも実装テクとして定番です。
良くある例）vector<int> dx = {1,0,-1,0};vector<int> dy={0,1,0,-1};
8. Belt Conveyor
ソースコード（C++）
vector<int> solve()
{
int h, w;
cin >> h >> w;
vector<vector<char>> maze(h + 2, vector<char>(w + 2, '#'));
rep(i, h)
{
rep(j, w)
{
cin >> maze[i + 1][j + 1];
}
}
int ci = 1;
int cj = 1;
map<char, int> di, dj;
di['U'] = -1;
di['D'] = 1;
di['L'] = 0;
di['R'] = 0;
dj['U'] = 0;
dj['D'] = 0;
dj['L'] = -1;
dj['R'] = 1;
rep(i, h * w)
{
if (maze[ci][cj] == '#')
{
ci = clamp(ci, 1, h);
cj = clamp(cj, 1, w);
return {ci, cj};
}
char now = maze[ci][cj];
ci += di[now];
cj += dj[now];
}
return {-1};
}
int main()
{
cout << solve() << endl;
}
迷路を番兵で囲む
これはかなり特殊なテクというか、使う人は少ないと自覚していますが、番兵として迷路を壁または通路で囲むということを時々やります。これにより、コーナーでの処理を一括して行え（る場合があり）ます。
つまり、
.#.
...
...
が入力として洗えられたら、高さと幅にそれぞれ 2 つずつ余裕を持たせて、
#####
#...#
#.#.#
#...#
#####
という形にするということです。
この問題では、「それ以上進めなくなったら終わり」という条件を実現するために 4 通りの実装が必要ですが、こうすることにより「# に到達したら終わり」という 1 つの条件にまとめることができます。$H \times W$ 回移動できたら -1（鳩の巣原理により証明できます）、そうでなければ、# に到達した時点の 1 つ手前のマスが答えです。
分岐を配列として事前定義
UDLR にそれぞれ方向を当てはめることにより if 分岐を省略できます。
9. Final Day
ソースコード（C++）
int main()
{
int n, k;
cin >> n >> k;
vector<int> p(n);
rep(i, n)
{
rep(j, 3)
{
int x;
cin >> x;
p[i] += x;
}
}
vector<int> q = p;
sort(all(q));
int border = q[n - k];
rep(i, n)
{
if (p[i] + 300 >= border)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
}
貪欲な条件を見抜く
問題文をそのまま読むと $300^N$ 通りのシミュレーションが必要になりそうに思えますが、少し考えると最適な条件は、自分だけが 300 点を取ることであることがわかります。
更に、同率順位の条件が「その生徒よりも合計点が高い生徒の人数に 1 を加えた値」、つまりなるべく高い方になるので（余談ですが、この考え方は「ある $x$ 以下の最大の位置」を調べる時に upper_bound を使った後にデクリメントする考え方と全く同じです）、要は自分のスコア +300 が当初の K 位の人のスコア以上になるかどうかが条件になります。
10. Poem Online Judge
ソースコード（C++）
int main()
{
int n;
cin >> n;
set<string> used;
int peak = -1e9;
int ans = -1;
rep(i, n)
{
string s;
int t;
cin >> s >> t;
if (used.count(s))
{
continue;
}
used.insert(s);
if (t > peak)
{
peak = t;
ans = i + 1;
}
}
cout << ans << endl;
}
変数の使いまわし
問題文がややこしいですが、要は「初めてその文が出現した時」かつ「最高点より高い点が出た時」にのみ更新が起こるので、逐次的に処理することができます。最高点は「その時点の最高点」を持っていれば、それを使い回すことができます。個人的にこのような変数には peak という名前をよくつけます。
余談：単位元と吸収元
この問題では peak は -1e9 として初期化しています。以前の解説で sum を使い回し変数として用意した時は 0 で初期化しましたが、これはなぜかというと、単位元の扱いの違いになります。単位元とは、それ自身を加えても何の変化も起こさないような要素を言いますが、これは番兵を設定する際にもよく使います。逆に、それを加えたら強制的にある値に収束するような要素を吸収元といいます。初期値として吸収元を使うことは普通はないですが、番兵でこれを置くことはよくありますね。
実は、この問題の制約では peak を 0 で初期化しても不都合ありませんが、問題によってはそれより小さい数（負数など）が出てきた時に予期しない挙動をします。$-\infty$ が最大値を取る操作に対する本来の単位元なのですが、整数型でそれを表現するのは不可能なので、実用上は、十分小さい数によってそれを事実的に代用します。
11. Doukasen
ソースコード（C++）
int main()
{
int n;
cin >> n;
double virtual_length = 0;
vector<pair<double, double>> vp(n);
cin >> vp;
rep(i, n)
{
auto [a, b] = vp[i];
virtual_length += a / b;
}
virtual_length /= 2;
double ans = 0;
rep(i, n)
{
auto [a, b] = vp[i];
double valid = min(a / b, virtual_length);
virtual_length -= valid;
ans += valid * b;
}
cout << fixed << setprecision(20) << ans << endl;
}
min/max で if を省略
$B$ は燃焼速度になりますが、「同じ長さを速く走っている」ことは「縮められた空間を同じ速さで走っている」と考えることができます。同じ速さで走っている場合、2 つの火がぶつかる点は明らかに中点になります。つまり、これは縮められた区間上の中点は、元の空間だとどの位置か？という問題になり、各スパンを使い切れる分だけ使う問題と同じになり、上に出てきた「min/max で if を省略する」実装が使えます。
12. C - Collision 2
ソースコード（Python）
from collections import defaultdict
def solve():
n = int(input())
vp = [[]*2 for i in range(n)]
for i in range(n):
vp[i] = list(map(int, input().split(' ')))
s = input()
left_max = defaultdict(lambda: -1e9)
right_min = defaultdict(lambda: 1e9)
for i in range(n):
x, y = vp[i]
c = s[i]
if c == 'R':
if x < left_max[y]:
return 'Yes'
right_min[y] = min(x, right_min[y])
if c == 'L':
if right_min[y] < x:
return 'Yes'
left_max[y] = max(x, left_max[y])
return 'No'
print(solve())
連想配列で必要な部分だけ記録+α
問題の意図をつきつめると、「ある行に R が出たとき、その右に L がいるか？」または「ある行に L が出たとき、その左に R はいるか？」ということになります。そのためには、「最も右にある L」または「最も左にある R」を記憶していく必要があります。
すでに値が設定されている時は単純に比較すればいいですが、問題はその行に R や L が全く設定されていない時です。if で場合分けをしてもいいですが、単位元を設定することにより包括して処理できます。これが、例えば y の制約が小さい場合は、初期値を $+\infty$ または $-\infty$ にした配列を設定すればいいですが、この問題では制約が大きいのでメモリオーバーします。
そこで、「連想配列で必要な部分だけ記録」テクが必要になりますが、例えば int 型であった場合、初期値は $0$ になります。こんな時、Python の defaultdict では、その場で関数を定義することにより初期値を都合よく設定できるので、効率的に実装できます。
left_max = defaultdict(lambda: -1e9)
right_min = defaultdict(lambda: 1e9)
13. Changing Jewels
ソースコード（C++）
int main()
{
int n;
cin >> n;
ll x, y;
cin >> x >> y;
vector<vector<ll>> dp(n, vector<ll>(2));
dp[0][0] = 1;
rep(i, n-1)
{
dp[i + 1][0] += dp[i][0];
dp[i][1] += dp[i][0] * x;
dp[i + 1][0] += dp[i][1];
dp[i + 1][1] += dp[i][1] * y;
}
cout << dp[n-1][1] << endl;
}
この問題については、動的計画法を使って解く問題で、実装効率化することもないかなと思ったので、説明を省略します。すいません。
14. Number Box
ソースコード（Python）
from itertools import product
n = int(input())
a = [input() for i in range(n)]
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
ans = ''
for i, j, d in product(range(n), range(n), range(8)):
tmp = ''
for p in range(n):
tmp += a[(i+dx[d]*p) % n][(j+dy[d]*p) % n]
ans = max(ans, tmp)
print(ans)
こういうのがまさに実装ゲー！
分岐を配列として事前定義
「$x$ 方向と $y$ 方向の移動方向を事前定義しておく」が、まさに活用される事例です。8 方向でも dx と dy を事前に定義しておくことにより、ひとつのループで回すことができます。
全探索をひとつにまとめる
これは Python 前提のテクニックになりますが、複数の変数をまとめて全探索したいとき、変数ひとつごとにネストが深くなりますが、その深さに本質的な意味はないです。itertools.product を使うことにより、リスト同士の直積（つまり全探索）を一回の命令で行うことができます。
Python の剰余の性質を利用する
これも Python 前提のテクニックになりますが、グリッド上をループする時に、x 座標や y 座標を横幅や縦幅で mod を取りたいことはよくあります。C++ だと剰余は負の値になりえるので配列外参照エラーを出しますが、Python の mod 演算は正の値を返してくれるので、こういう時には便利です。
15. X drawing
ソースコード（C++）
int main()
{
ll n, a, b;
cin >> n >> a >> b;
ll p, q, r, s;
cin >> p >> q >> r >> s;
for (ll x = p; x <= q; x++)
{
for (ll y = r; y <= s; y++)
{
if (abs(x - a) == abs(y - b))
{
cout << '#';
}
else
{
cout << '.';
}
}
cout << endl;
}
}
必要な部分だけ評価
すべてのマス目をシミュレーションすると到底間に合わないので、答えの出力に必要な部分だけシミュレーションをします。
16. Strange Balls
ソースコード（C++）
int main()
{
int n;
cin >> n;
stack<pair<int, int>> st;
st.push({-1, 0});
int ans = 0;
rep(i, n)
{
int a;
cin >> a;
if (a == st.top().first)
{
st.top().second++;
ans++;
}
else
{
st.push({a, 1});
ans++;
}
if (st.top().second == st.top().first)
{
ans -= st.top().second;
st.pop();
}
cout << ans << endl;
}
}
圧縮された状態で持つ
扱う数は大きいけど、実は順序だけが重要だったり、実は同じ状態が続くだけだったり、という状況はよくあります。前者は座標圧縮、後者はランレングス圧縮をすることにより、効率的に管理できます。今回は、後者のランレングス圧縮を使います。
17. Product
ソースコード（Python）
from itertools import product
n, x = list(map(int, input().split(' ')))
dp = [1]
for i in range(n):
L, *a = list(map(int, input().split(' ')))
dp = [p*q for (p, q) in product(dp, a)]
print(dp.count(x))
必要な部分だけ記録＆全探索をまとめる
DP で数を記録できそう＆（制約で保証されているので）必要な部分だけ連想配列で記録すればメモリを節約できそう、という発想はすぐ出てくると思います。実際にそれでも大丈夫ですが、そもそも直積を全部カウントしたいという問題の気持ちに立ち返れば、product で直積をまとめて計算することができます。繰り返しますが、最終的な数のカウントがそこまで大きくならないことは制約で保証されているので、リストに出てきた数をすべて数え上げるという愚直な手段でも AC することができます。
18. Connect 6
ソースコード（Python）
from itertools import product
def main():
n = int(input())
maze = ['*'*(n+12) for i in range(n+12)]
for i in range(n):
maze[i+6] = '*'*6 + input() + '*'*6
dx = [1, 1, 0, -1]
dy = [0, 1, 1, 1]
for i, j, d in product(range(6, 6+n), range(6, 6+n), range(4)):
criteria = 0
for p in range(6):
nx = i + dx[d]*p
ny = j + dy[d]*p
criteria += maze[nx][ny] == '#'
criteria *= maze[nx][ny] != '*'
if criteria >= 4:
return 'Yes'
return 'No'
print(main())
これもザ・実装問題という感じ。
分岐を配列として事前定義
タテ、横、ナナメの分岐を考える必要があるため、配列として事前定義します。このとき、ナナメは右下方向と右上方向の両方を考えなければいけないことに注意です。
迷路を番兵で囲む
迷路において「これより上にはいけない」「これより右にはいけない」といった状況を考えることはよくあって、if 処理で実装することができます。しかしこれは面倒なので番兵で囲むという発想がでてきます。今までのように $1$ 層の番兵だと結局 if 処理が必要になりますが、この問題では「はみ出す範囲」はたかだか $5$ なので、それを上回る 十分な厚さの番兵で囲ってしまえば 何も問題なくなります。力押し！
また、この問題では、「番兵にアクセスする＝問題の要件を満たさない」なので、番兵を単位元にするとバグります。このため * という独自のコマを用意して、ここにアクセスしたら絶対に条件を満たさない、という風にしています。数学的にいうとこれは 吸収元 になります。加法においては $-\infty$ ですが、無限はプログラムで実装しづらいので「$0$ をかける」ことによって実装しています。
全探索をひとつにまとめる
やることは「始点の縦、始点の横、方向」の全探索なので、product の直積でネストをまとめることができます。
19. Teleportation
ソースコード（Python）
import numpy as np
from itertools import permutations
from collections import defaultdict
n = int(input())
vp = [np.array(list(map(int, input().split(' ')))) for i in range(n)]
ans = defaultdict(int)
for i,j in permutations(range(n),r=2):
d = vp[i] - vp[j]
d //= np.gcd.reduce(d)
ans[tuple(d)]+=1
print(len(ans))
numpy を使う
$N$ が小さいので、すべての 2 点間の組み合わせを総当りで調べることができますが、問題の本質は、そのうち、移動手段を使い回せるものをまとめることです。この場合、移動経路を GCD で割ったものを数え上げればいいです。ベクトル間の演算、GCD は numpy の関数で簡潔に求めることができます。numpy の GCD は常に正を返すので、この問題では単純にそれで割ればいいです。
補足として、傾きだけに注目する場合は x 方向を常に正にする等の追加処理が必要です。
20. Circumferences
ソースコード（Python）
int main()
{
int n;
cin >> n;
vector<ll> x(n + 2), y(n + 2), r(n + 2);
rep(i, n + 2)
{
if (i < 2)
{
cin >> x[i] >> y[i];
}
else
{
cin >> x[i] >> y[i] >> r[i];
}
}
dsu uf(n + 2);
rep(i, n + 2)
{
rep(j, n + 2)
{
ll criteria = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) - r[i] * r[i] - r[j] * r[j];
if (abs(criteria) <= 2 * r[i] * r[j])
{
uf.merge(i, j);
}
}
}
if (uf.same(0, 1))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
例外的な形を、包括的な処理の特殊な形とみなす
ちょっと言葉での説明が難しいですが、この問題においては 「始点と終点」をそれぞれ「半径 0 の円周」とみなす ことにより、「N 個の円周と 2 個の点」という処理を、「N+2 個の円周」という形で包括的に処理できます。このような形で、「これだけは if が必要かな」という処理も、if を使わずに処理することができます。
21. Dance
ソースコード（C++）
int n;
vector<vector<int>> a;
vector<bool> seen;
int val = 0;
int ans = 0;
void dfs(int now)
{
if (now == n)
{
auto chmax = [](auto &a, auto b)
{ a = max(a, b); };
chmax(ans, val);
return;
}
int p = 0;
while (seen[p])
{
p++;
}
seen[p] = true;
for (int q = 0; q < 2 * n; q++)
{
if (seen[q])
{
continue;
}
seen[q] = true;
val ^= a[p][q];
dfs(now + 1);
val ^= a[p][q];
seen[q] = false;
}
seen[p] = false;
return;
}
int main()
{
cin >> n;
a.resize(2 * n, vector<int>(2 * n));
seen.resize(2 * n);
rep(i, 2 * n - 1)
{
rep(j, 2 * n - 1 - i)
{
int x;
cin >> x;
a[i][j + i + 1] = x;
a[j + i + 1][i] = x;
}
}
dfs(0);
cout << ans << endl;
}
やることは単純だけど、総当たりに近い処理を工夫して高速化する必要があり、けっこう実装が面倒くさい問題。
再帰の外で変数を使い回す
こういった処理は、再帰 DFS で組むのが定番ですが、再帰 DFS の中で色々な情報を扱いたいがゆえに、引数にそれを追加してしまった場合、最悪、大量のデータのコピーが発生して TLE を招きます。参照渡しにしてロスを防ぐこともできますが、関数の形はややこしくなります。
そこで、少しでも関数をスリム化＆高速化するために、再帰の外で変数を設定し、それを使い回すことを考えます。実は、再帰の処理は、
- 変数への処理
- 次の再帰処理
- 変数への処理をキャンセル
という形で再帰をつないでいけば、引数を使わずとも、あたかも変数を引き継いで再帰処理するかのように実装することができます。これも、言葉では説明が難しいですが、
seen[q] = true;
val ^= a[p][q];
dfs(now + 1);
val ^= a[p][q];
seen[q] = false;
このあたりが、そのような実装になっています。
終端条件を意識する
これも抽象的な話になりますが、「N 回目の処理が終わった後にある操作をする」という場合、
- N（プログラム上は
n-1）回目かどうかを判定した後、最後に操作をする - N+1（プログラム上は
n）回目かどうかを判定した後、最初に操作をする
これのどちらでも同じ処理ができます。日本語として素直なのは前者ですが、実装上は後者の方がやりやすくなることが多いです。半開区間との相性も良いです。vector や set においては end() に到達した状態が、これに相当します。
ただし、n の状態でアクセスを行うと配列外参照を起こすので、その点は注意です。end() も、アクセスをしようとすると未定義動作になります。
22. Unique Username
ソースコード（Python）
from itertools import combinations_with_replacement, permutations
from collections import defaultdict, Counter
n, m = list(map(int, input().split(' ')))
s = [input() for i in range(n)]
t = set(input() for i in range(m))
margin = 16 - sum(map(len, s)) - n + 1
for perm in permutations(s):
for use in range(margin+1):
for comb in combinations_with_replacement(range(n-1), r=use):
bucket = Counter(comb)
bucket[n-1] = -1
tmp = ''
for i in range(n):
tmp += perm[i]
tmp += '_'*(bucket[i] + 1)
if tmp not in t and len(tmp) >= 3:
print(tmp)
exit()
print(-1)
これも先程の問題と同じく、泥臭い全探索を行う問題ですが、更に条件がややこしくなっています。
最低限必要な試行回数を見抜く
問題文を理解すると、可能な文字列の自由度が見かけより少ないことがわかります。すべての文字列パーツを使って、なおかつ、その間には少なくともひとつの _ が入るため、最大の長さである $16$ から、文字列パーツすべての長さと、その $n-1$ を引いた長さが、許容されるマージンです。後は、そのマージンを埋める _ をどこの位置に入れるかという問題になります。
つまり、これは「総数が決まっているボールをどこに入れるか」という問題と同じになります。これは、重複組合せによって過不足なく列挙することができます。