ABC343（2024/03/02）
〇A問題
Yuto.icon やるだけ．今回もRustで参加．来週のコンテストも飛び賞狙いでRust参加しようかな...
tako.iconてきとう
おたふく.icon 指示通り。
Kaplam.iconそのまま
yuichang.iconやる
TTT.icon forでやりました．
まーす.iconforでiを0から9までまわしてA + B != iがTrueなら，出力＆break．
CarpDay.icon合計が1なら0，それ以外なら1
〇B問題
Yuto.icon やるだけ２
tako.iconてきとう2
おたふく.icon 隣接行列から、隣接リストに直す。
Kaplam.iconそのまま2
yuichang.iconvector<set<lint>>
TTT.icon A[i][j] == 1であればans[i].append(j)していったかんじです．インデックスに注意．
まーす.icon二重forでAij == 1なら，出力．
CarpDay.icon 多分TTT.iconさんと同じ．
〇C問題
Yuto.icon 最初，18桁以下で回文になり得るものを全列挙して，立方数判定しようとしてたけど，18桁以下で回文になり得るものの個数が多いことに気付く．N以下の個数はsqrt(10^18)なので大体10^6個くらい．これなら全列挙できる．正の整数にゼロを含めてゐなくて1WA．
おたふく.icon 正の整数には0を含めないのでは？？
Yuto.icon WAの原因，N以下じゃなくてN未満を見ていたのが原因やったわ
おたふく.icon x^3 = 10^18を満たすとき、x = 10^6よりO(10^6)で立方数を全探索できる。
tako.iconx^3がNをこえるまでループ回す
Kaplam.icon同上
yuichang.icon 1e6まで回す
TTT.icon 先にN以下の立法数のリストを作っておいて，値の大きい方から順に文字列として見ていき，回文であれば即座にprint, exit()．
まーす.icon同上．TTT.icon さんの方が賢明ですね．私は，x^3 <= 10^18より，高々O(10^7)なので，for文の中でx^3 == Kの処理と回文の処理を同時にしていました．1ペナの理由は，恐らくYuto.iconさんと同じで，1WAが出た瞬間に気づいた......
CarpDay.icon tako.iconさんと同じ．回文判定するのに，N^3を文字列にしたものの，先頭と末尾から1つずつずらして同じか判定．文字列ごと反転して，文字列ごと比較すれば簡単なのに．．複数のデータ（文字列やリスト）をまとめて比較するのに，なかなか慣れません．
〇D問題
tako.iconSortedList使って解いてみた
Kaplam.icon辞書とか使ってこの数字が0個になったら1種類引いてみたく
Yuto.icon 最初Rustで解いていたけど，Pythonのsortedcontainersが欲しくなったので乗り換え．SortedDictを使って，d[score] = {player1, player2, ...}を管理すれば解ける．
おたふく.icon それぞれのプレイヤーのスコアと、それぞれのスコアの個数を管理するだけ。
yuichang.icon辞書で管理
TTT.icon コンテスト内の残り40分をDに費やすも時間内に解けず．コンテスト後に解説見ずに辞書で実装するもAC19，WA6．サンプルが全て通っている分修正箇所が分かりません．
Yuto.icon 下のテストケース試してみ
code:txt
input:
2 3
1 2
1 1
2 2
correct:
2
2
2
output:
???
まーす.iconおたふく.iconさんと同じ．辞書の有用性が分かる問題．
CarpDay.icon同様．defaultdictで実装．
〇E問題
tako.icon問題読んだけど解く気になれずスキップ
Kaplam.icon解説と同じようにやって謎の2WAが消えなかった、いつまでもEが通らない_(:3」∠)_
おたふく.icon 良いところまで考察は出来ていると思うのだが...。立てていた方針が合っていたが考え漏れが有ったことを解説を見て確認。解説通り行った結果、TLEに苦しむ。
Yuto.icon 幾何は無理です
まーす.icon同感です．Euclid 原論はこれよりもっと難しい......．
Yuto.icon _(:3」∠)_
おたふく.icon 幾何要素は少ないよ💪
まーす.icon制約的にa1 = b1 = c1 = 0と固定すると全探索できるが，場合分けが面倒そう......．
CarpDay.icon 20分考察したが時間の無駄だった．とりあえず面積で考えてみて，各体積を求められることは確認．次に各体積を素因数分解して，7以下の3項の積で表せるかチェックすれば．．．のところで，ちょっとしんどくなってFを見に行く．
〇F問題
tako.iconセグ木。イイ感じのモノイドを乗せてあげましょう
Yuto.icon またも爆速でタコが通してたので，セグ木だろうなーと思って問題文を読む．
おたふく.icon セグ木かなと思うも持たせる情報に困り、E問題に戻る。タコちゃん強い...。
kakip.iconpythonで通らなかったのでchatGPTにC++に変えてもらったけどバグ取れず。C++だとmapつかっても通るっぽい
yuichang.icon セグ木で頑張れずに終了
CarpDay.icon 初めは4つのセグ木を作る方針で考えていたが，1つのセグ木でできることに気付く．いい感じで実装したが，場合分けが漏れていて時間がかかる．入力例3の最後の出力が合わない．場合分けでコピペ＆修正が甘い箇所があり，気付いたときには3分オーバー．無念．tako.iconさん，セグ木・遅延セグ木，得意分野になったね．
〇G問題
Yuto.icon AHC028の類題．Zアルゴリズム+TSP．焼いてみたけど，39ケース中 36AC, 3WA が限界だった....たぶん近傍が悪いんだと思う（変化が大きすぎる？多様性が無い？）
CarpDay.icon 「G問題が面白い」と事前にちょっとネタバレもらっていたけど，見ることもできず．．