解くに至った問題(8問)
ABC:066C/068C/082C/085D/088C/108C/109C/113C
ABC068C
二つの島を行き来する定期便があり、往復する島がリストで与えられるので、一回の乗り換えで、島1→島i→島Nと行くことができるかを判定する問題
一個一個のリストを調べて[1,i]と[i,N]の存在を調べるのは非効率なので、ここではTrue、Falseを持ったリストを二つ作り、照らし合わせることを考える
具体的には、FalseをN+1個持ったリストJ,Kを作る。これを使って島1と島i、島iと島Nが結ばれているかどうかを判定する
島1と島iが結ばれていれば、リストJのi番目の要素をTrueに変更。島iと島Nが結ばれていれば、リストKのi番目の要素をTrueに変更。こうしてできた二つのリストを最初から見ていき、同じi番目がTrueを持っていれば、島iを経由して島1から島Nに行けると判断できる
ABC088C
実質連立方程式 変数の自由度が高ければ、1つ(ここではa_0)の値を0と仮定することで確かめることができたりする
ABC113C
11行目のところ
for k in range(M):
if l == L[k][0]:
cnt += 1
L[k].append(cnt)
のcntとappendの位置が逆になっていたことが原因で昨日バグらせていた taiyoslime感謝します
リストLに対して、
L.sort()とすればリストの最初の要素でソートしてくれるけど、2番目の要素とかでソートしたいなーってなったら、
L = sorted(L, key = lambda x:x[1])
とすればよい