ABC342 （2024/02/24）
〇A問題
Yuto.icon 今回はRustで参加．Sに含まれる文字の個数を数えて，個数が2の文字を出力するだけなんだけど，めっちゃ時間かかった．なんかいつものAより難しいなぁとおもったら150点なんですね．
TK.icon文字を二種類カウント、少ないほうのindexを出力。読み込みで打ち間違いをして、予期せぬバグで沼った。
おたふく.icon from collections import Counter
tako.iconindexとrindex
kakip.iconCounterで一個しかないやつをS.find()
Kaplam.icon2重回して1個だけだったらprint
sakana.icon良い方法が思いつかず愚直に最初か最後か文字列中にある時の条件分岐
まーす.iconきたない場合分けをしてAC．私は先頭の１，２文字目に着目した．
TTT.icon 探索開始位置の移動と探索の移動の2重forです．
CarpDay.icon 多分まーす.iconさんと同じ．最初の2文字が同じか異なるかで場合分け．
〇B問題
Yuto.icon Pの逆を求めるだけ．Aより簡単
TK.icon辞書でやった
おたふく.icon value : indexのdictを作成
tako.iconB問題なのでP.index()
kakip.iconリストで人：位置
Kaplam.icon2重回して先に出てきたらprint
sakana.icon２重for文
まーす.iconKaplam.iconさん，sakana.iconさんと同じ．
TTT.icon for p in P: if p == query_A: print(query_A) break elif p == query_B: print(query_B) break
CarpDay.iconみなさんと多分同じ
〇C問題
Yuto.icon 毎回全部書き換えるとTLEになるので，各文字cについてmap[c] -> c' を持っておいて，最後に書き換える．既に登録されている時の処理でちょっと手間取ったのと，Rustの連想配列（辞書）に慣れてなくてめっちゃ時間かかった２
TK.icon最初に思いついた方針から抜け出せずDへ行く。落ち着いてから考え直す。
おたふく.icon 少し考えて思い付かなかったので一旦Dへ。
tako.icon計算量をもっとよく考えるべきだった
kakip.icondictに各文字をreplace
Kaplam.iconordとdictで何に変わるか見る
sakana.iconアルファベットの文字列を用意して、操作実行した後に、元の文章を置き換えた。
TTT.icon 時間内に良い方法がまったく思いつかなかったです．公式解説を読んで理解，実装しましたがコンテスト中にこれを思いつける自信はないです．
CarpDay.iconUnionFindだと思い込んで時間ロス．アルファベットの個数が26個しかないことに気付いて愚直に実装．
〇D問題
Yuto.icon 片方固定して，良い感じにやるのをやりたかったけど，A[i]と掛けて平方数になる相手の個数ってどうやって決めるの？二分探索？
TK.icon前にこの手の問題で二分探使って高速にやるやつあったよなと思いつつも、平方数の候補自体が√2*10^5個あって、探すペア自体も多そうだから方針的に違いそうと思いDとCを行ったり来たり。中途半端に考えたのが良くない。
おたふく.icon コンテスト終了5分後にAC...。方針は合っていたのに考え漏れに気付けず。素因数分解。
kakip.icon素因数の指数の偶奇がすべて一致していたら平方数
Kaplam.iconその数に含まれてる2乗全部とって残ったやつが一緒or片方0だったら平方
まーす.icon① Ai をそれぞれ平方数でないような形に分解する．② dictなどで数え挙げ．①で１ペナ，②で2ペナ(0が複数個のときの処理を想定していなかった)．
まーす.icon①の操作の補足，Ai = (平方数でない数 or 1) * (平方数) のように分解して，(i) Ai を (平方数でない数 or 1) に更新．(ii) Ai が 0 のときは，Aiを更新しない．このことは，任意の自然数を一通りの素数の積で表せるという事実から言える．
まーす.icon②の操作には，対称性を利用．これによって，O(k*N) = O(N),(k：Aiの①の分解にかかるループ数 )で可能．
まーす.icon今パフォーマンスみましたが，961 = 31^2なのでこの問題とマッチしていていいですね!
CarpDay.icon素因数分解して，奇数の累乗の数だけ残して，同じペアがいくつあるか数える．元々平方数の数も考慮する．0の処理が厄介で，0が複数ある場合の処理が甘く最後までWA取れず．やっと気づいてギリギリAC！と思ったら，2分過ぎてた．．
〇E問題
Yuto.icon 覗きにきたけど，無理そうだったのでDに戻る
tako.icon不等号の向きが間違ってることに気づかずにサンプルが合わず時間内提出できなかった。間違いに気づいて提出したら1WA。コンテスト後解説読んでAC。1WAの原因は>=を>にしてたこと。C問題で躓かなければ解けてたなー
Kaplam.icon逆から見てダイクストラする所までは行ったけど実装大変すぎるやり方しか思いつかなかった
〇F問題
kakip.iconDPでできそう、できた、累積和とかいっぱい使う