ABC296 (2023/04/01)
〇A問題
Yuto.icon S[i]==S[i+1]を見るだけ．ループ範囲に注意する
TTT.icon 方針はYuto.iconさんと同じです。
まーす.icon↑と同様
CarpDay.icon奇数番目が1番目と違う，または偶数番目が1番目と同じならNo．問題に男性同士が隣り合う箇所も女性同士が隣り合う箇所も存在しないとき、かつ、そのときに限り、男女が交互に並んでいるとあるのに読めていない...
おたふく.icon Yuto.icon同様
TK.icon難しく考えすぎて時間がかかった、方針は次が違うものが来るかどうかを見ていく感じ
sakana.icon複雑にしてしまったが、前後が違う文字かどうかを判定した
〇B問題
Yuto.icon ラスタスキャン(画像工学でやったやつ)
TTT.icon 添え字 i のfor文に添え字 j のfor文をネストした状態で、*であればprint(chr(ord("a")+j),end="") print(8-i)としました。
まーす.icon困ったら、総当たり定期。
CarpDay.icon二重ループで*探す．行方向の1～8は8-iでいいのに，わざわざ検索用文字列"12345678"を作成する不始末．
おたふく.icon TTT.icon同様
TK.iconCarpDay.icon同様二重ループで探した。
sakana.icon”abcdefgh”と"87654321"の文字列を作成しておいて、二重ループ
〇C問題
Yuto.icon 二乗を消したい．Ai - Aj = X ⇆ Ai = X + Ajと言い換えると一乗に落ちる．ここまで9分で良いペース．
TTT.icon A_listの集合型A_setを生成し、if A_list( i )+X in A_set : を満たすときにYesと出力しました。
まーす.icon集合{A+X},{X-A}を用意し、これのいずれかを満たせばYesを出力。(A-Xを忘れてWA)
CarpDay.iconAj = Ai + XなのでAi + XがAの中に存在するか確認．確認するだけなのに，わざわざbisect使う不始末．
おたふく.icon Ai + X がset(A)内に存在しているかどうか確認。
TK.iconAj = Ai + XなのでAi + XがAの中に存在するか確認.
sakana.icon解法はTK.icon同様。”yes”となっていてWA出した CarpDay.icon "Yes"の"Y"が小文字になっていた，ということね！
〇D問題
Yuto.icon aを「あり得る範囲で」全探索して，bはにぶたんした．コンテスト後落ち着いて考えてみるとにぶたん要らなかったけど，まあいいや．「あり得る範囲」というのがちょっと難しかったものの，スムーズに考察, 実装できた．素晴らしい．久しぶりに全ての問題を学内FA(first accept)．
TTT.icon (Yuto.iconさん、scrapboxでのpythonプログラムの書き方を教えてくださりありがとうございます！) 最初は愚直に、
code:python
for i in range(1,N):
for j in range(i,N):
if M <= i*j:
print(i*j)
exit()
pirnt(-1)
としましたが、案の定自分の開発環境でsample03がTLとなったので組み合わせの探索アルゴリズムを考えている最中にコンテストが終了しました。D以降はほとんど見ていません。
CarpDay.icon今日は絶対にD問題解くと決めていたので，最後まで諦めずに挑み，最後まで解けずに終わる．敗因は素数列挙や約数列挙にこだわりすぎ．TTT.iconのような素直な発想ができれば...
TK.icon範囲の不等式を見て、Xの値の範囲は特定できると思ったが、うまく活用できていない。-1になる場合がすぐ思いついたが、そこから失速。ｘ範囲をしぼってもTLEになりそうな発想しかできなかった。
おたふく.icon 方針としては時間内に考えていたもので概ね合っていた。後日解説を読み、数行追加することでAC。
〇E問題
Yuto.icon Dまで簡単だったのにE以降が難しすぎる．手も足も出ずにコンテスト終了．
まーす.iconそもそも問題文がわからない。でも個人的にDよりは希望があると思ってる。 追記4/3 am5:30↓(解説見ていない&AC出てないけど答えにかなり近そうなので伏せときまーす!) 場合分けを以下のようにすると良さそう。(まだ、コードわからんけど......) ①自己ループ ②環状ループ ➂側鎖(トルエンなどの-CH3基を指す) ➃その他(自己ループに向かうAの要素) このとき、Aの添え字とAiが結合していると考える。例えば、i=3でA3=2ならば頂点3と頂点2が１つの辺を持つということ。 Aの添え字は全順序。辺の数はN個(①含む)、頂点N個。ナフタレンのような２つ以上の環がくっついたものは除いてよい。 (環は単独で存在するということ) 出力部＝①＋② もう少し本格的に考えるとiとAiの関係RとしてR^Nを求め、グラフR^Nの到達可能な頂点を探索すればよい。
CarpDay.iconコンテスト終了後に問題を読む．まーす.iconと同感，個人的にはD問題より簡単に感じた．5分ぐらいで基本方針を発見，1TLEで本質を発見して，40分ぐらいでAC．本質的には，サイクルに含まれる点数のカウントになるため，少し前の問題で扱ったトポロジカルソートで解決．1つの問題に意固地にならず，諦める潔さも重要（以前にもそう記した気が．．．）
おたふく.icon 閉路に含まれる頂点数を数えるために強連結成分分解を勉強。CarpDay.iconの計算時間と比較して、自分のコードでの計算時間が大きくギリギリだったので次回の勉強会でアルゴリズムを教わりたい。
CarpDay.icon 勉強会後の追記： 1TLEした解法について，「ユーザ解説と方針同じなのに，自分はTLE」との発言をしたけど，大きな間違い．自分の方法は1回ずつ遷移した結果を利用．ユーザ解説はダブリングを使って，30回ループして$ 2^{30}回遷移した結果を利用．ダブリングとは，powの繰り返し2乗法と同じように，$ M回のループで$ 2^M回の遷移（変化）結果を獲得する方法．あるいは，$ 2^m (m=0, 1, ..., M-1)回の移動結果を計算しておいて，2進数計算と同じ方法で$ i=0, 1, ..., 2^M-1回の移動結果を獲得する方法．$ N要素内を$ K回の移動した結果を$ O(N\log K)で獲得可能．詳しくはこちら． 〇F問題
まーす.iconC終了以降、ずっとここを考えている。順列(signature)の互換の回数で解けそうなんだがWA２個、TLEたくさんある(F問題下から３つ目のWA参照)。まず反例はなんや(まじでわからん)。 4/2 am7:00カンニング後↓ 考え方は合っていた。ただ、自分は線形代数の教科書p52 問題3.1の大問７あみだくじの問題の要領でやっていたが、どうやらその節でやった転倒(解説では反転と記載)を利用するようだ。マジで惜しい。悔しい。因みに、個人的に公式の解説が分かりにくかったので、他の人のものを参考にして転倒数にセグメント木を使えばよいことを知った。
CarpDay.iconコンテスト終了後に，グラフで考える．サイクルの長さと個数で判定できそうだが，同じ要素が複数存在する場合に対応できず解説を見る．鉄則の一つ，不変量を考える問題．まーす.iconが記した通り，数学的には転倒数を考える問題．セグメント木やBITでも良いが，マージソートを基とする方法でも同じ計算量で実行できることを知って実装．なるほど．Φ(. . )ﾒﾓﾒﾓ