tooh’s diary

半角全角、常体敬体が入り乱れるカオス

2/18 AtCoder(boolean配列、リストのn番目でソート)

AtCoder

解くに至った問題(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感謝します

d.hatena.ne.jp

リストLに対して、

L.sort()とすればリストの最初の要素でソートしてくれるけど、2番目の要素とかでソートしたいなーってなったら、

L = sorted(L, key = lambda x:x[1])

とすればよい