ABC285 (2023/01/15)
〇A問題
TTT.icon グラフか木構造を作ることしか頭にありませんでした。b=a*2かb=a*2+1のどちらかであればYesであることに気づいたのが開始1時間後という悲惨な結果に(汗)
TK.icon隣接辞書を作ってゴリ押した。
CarpDay.icon 2で割る
おたふく.icon親の番号iから見て、子の番号は2*i or 2*i+1になっていることを使った
Yuto.icon完全二分木なので，子の番号は2*i or 2*i+1（上に同じ
〇B問題
TTT.icon S(k) != S(k+i) かつ (l+i<=N)の限りkとlをインクリメントしました。
TK.iconループの添え字がわけわからなくなってきたが、冷静に考えるとできた
CarpDay.icon上に同じく，添え字でパニックになりデバッグにもたつく．問題に合わせて1-indexにしたらできました．for文のrangeで混乱するぐらいなら，大きめに取っておいて，if文でbreakした方が作成早い．今後に生かします．
Yuto.icon 愚直にやったらPythonもPyPyもTLEしたのでB問題にしては重いな..と思いつつ，Lを二分探索してAC
おたふく.icon添え字の処理でもたつき大幅な時間ロス。1-indexにしようと文字列の連結を行うとTLE。文字列の連結はもうしない😢
CarpDay.iconPythonでTLEのプログラム，PyPyで投稿したらACでしたよ！
おたふく.icon再帰関数以外ではpypyを使うようにしようと思います。
CarpDay.icon+による文字列連結を多用する場合もPyPyは避けましょう！
〇C問題
TTT.icon 考えていましたがプログラムを組むのが大変そうだなと思っていました。時間内に実装できず。以降見ていません。
TK.iconノリは27進数。数字の代わりにアルファベットを使っているイメージ
CarpDay.icon 1～26までの26進数かな．string.ascii_uppercaseでアルファベット→1～26にする辞書を作成
おたふく.iconCarpDay.icon同様アルファベットの辞書作成。
Yuto.icon i桁目の時「pow(26, i)の累積和+i桁目の文字s(ord(s)-ord("A"))」の総和としたけどWA．
〇D問題
TK.icon現在のユーザID「S」とリクエストを受けているユーザID「T」をそれぞれ集合で持ち、Tの中でSと重複していない要素をとってきて、Tから削除、削除した要素に対応したもとのIDをSから削除、Sに消去したIDを追加。という風にして処理をすすめ、重複していない要素がなくなった時点で処理を終了し、Tが空集合出ないならNo、空集合ならYesとしたが、TLE。6件だけだが実装の仕方・考え方がそもそも違う気がする。
CarpDay.icon解説見ないで自分で解きたい人向けにヒント（考え方）を下に記します．
Sの名前もTの名前もグラフ上の点と考える．名前をSiからTiに変更することを，Si→Tiとなる有向枝（矢印，アーク）で表す．Siはすべて異なるので，ある点から2つの矢印が出ることはない．Tiはすべて異なるので，ある点に2つの矢印が入ることもない．ある点はある矢印の終点（Ti）であり，かつ，別の矢印の始点（Sj）である，ということはありうる．今，各ユーザが自分のSiの点の上に乗っている状態を考える．各ユーザはある順番で矢印に沿ってSiからTiに移動する．このとき，1つの点に2人のユーザが乗ることがないように，移動させる順番があるかどうか，がこの問題．逆に言えば，どうやっても，1つの点に2人が乗ってしまうことが起こるような状態って，グラフがどんな形になったとき？と考える．
おたふく.iconCarpDay.iconのヒントで分かった。非常に悔しい。
Yuto.iconぱっと見有向Graphのトポロジカルソートが思い浮かんだので，そんな感じで解いたけど無理だった
〇E問題
CarpDay.iconコンテスト終了2分25秒後にACでした．．．悔しい(; ;) ユーザー解説に近い考え方でした．ナップサック問題に帰着するユーザー解説に感動！分割問題を，分割後の要素を組み合わせる問題に変換する，という発想の転換がすばらしい．
〇F問題
CarpDay.icon E問題で諦めかけたときに覗いて，方針が分からずすぐにE問題に戻りました．終了後，セグメント木を使うところまでは分かったものの，正解まで思いつかず．解説見てAC．この分野の問題も早く解けるようになりたい．
Yuto.icon コンテスト後、勉強会で解説してもらった。個人的にはEよりも簡単に理解できた。初めてセグ木を勉強したけど大まかなイメージは掴めた。期末試験が終わったらセグ木ライブラリを整備しよう…