0.はじめに
3連休中日なので、うっかり忘れないよう気をつけながら参加。
A問題が150点と歯ごたえのある問題から始まりましたが
Cも350点と若干難しめ。
それでも自分的最低ラインのD問題までは解けたので
まぁ満足でした。時間は結構ギリギリでしたが。
レートは微増の979と最高値更新。そろそろ緑コーダを名乗っても
よさそうかなと思いました。
1.A - Yay!
意外と面倒な問題。
いろいろやり方はありそうではありますが
なんとなく思いついた以下で対応。
【実装】
・辞書を用意
・文字列を頭から見ていく
-辞書にない場合はキーに文字、値に位置を登録
-辞書にある場合は、値を-1に変更
・辞書の値の最大値を出力して終了
https://atcoder.jp/contests/abc342/submissions/50565226
2.B - Which is ahead?
求められることを素直に実装すればよさそうな問題。
素直に実装してAC
【実装】
・辞書を用意
・辞書を用意
・リストAを読み込み、辞書のキーにリストの値を
値にリストの位置を登録
・クエリーを読み込む
-Aの位置とBの位置を辞書から取り出し
位置の値が小さい方を出力する。
https://atcoder.jp/contests/abc342/submissions/50569366
3.C - Many Replacement
なかなか厄介な問題で取り掛かるまでに悩みました。
制約が大きいので、どこを繰り返すのが効率が良いかを考え
以下に行きつきました。
【考え方】
・アルファベットの文字毎に、最終的にどのアルファベット文字に
なるかの辞書を作って、最後に文字列Sアルファベットをそれぞれ
変換していく。
【実装】
1.辞書Dを用意
2.辞書のキーと値にアルファベットのa～zまでの文字をセット
3.クエリー数を読み込みクエリーごとに以下の処理を行う
-1.AとBを読み込む（問題上はCとDですが辞書にDを使ったので・・・）
-2.辞書のキーを変数kに、値を変数vに順に読み込んでいく
→vがAと一緒の時、D[k]にBをセット
4.リストansを用意
5.文字列Sを読み込んでいいき、各文字ごとに
辞書Dから、値を検索してansに追加
6.最後にansを結合した文字列を作り出力して終了
https://atcoder.jp/contests/abc342/submissions/50585713
4.D - Square Pair
TLE回避のためには二工夫くらいしないといけない問題。
解き終わった後に、なんか似た問題あったなと思ったりもしました。
【考え方】
・リスト内の0は、どの数字とでも平方数を作れる
・２つの数字を掛け合わせて平方数になる場合
それぞれの数字を素因数分解して得られた値
それぞれでペアを作れる
→素因数分解した時点でペアがあった場合は
省いておけば、省いたあとの2つの数字が同じ場合
平方数になると言える。
例）３と１２の時
・3 →3
・12→2×2×3→3
→掛け合わせると平方数になる。
・リストＡから、０は省きつつ、各数字を素数の2乗で割りきれる
だけ割った後の数字を別リストに格納していき
別リスト内で同じ数字の組み合わせ数を集計すれば
回答ができる。
（0を省くときはその時に残っている値数分答えに加算）
上記考え方を実装していきましたが、
・別リスト内で同じ数字の組み合わせ数を集計
の部分を単純に全組み合わせを確認する実装したら
TLEとなったので、慌ててpythonのCounterを調べ
nCrの公式を調べ・・と泥縄式にバタバタしつつ
10分残しでACとなりました。
また、素数の2乗のリストを作るロジックが
結構長くて埋め込むと見難かったので
必要な分だけリストにして手動でソースに張り付けるという
荒業を使ってしまいました。
【実装】
1.変数NとリストAを読み込む
2.素数の2乗リストL（4、9、25・・・201601）を定義
3.以下を定義
・答えを格納する変数ansを0で定義
・Lから選抜した値をセットするリストPを空で定義
・L内の0以外の値の数を持たせるN2をNで定義
4.リストAを順にみて以下の処理を行う
-1.リストA[i]が0の時
→N2から、1を引きansに加算
-2.リストA[i]が0以外の時
--1.変数jに0をセット
--2.pにA[i]をセット
--3.以下を、L[j]がpより大きくなるか、pが1になるまで実施
---1.pがL[j]で割り切れる時
→pにをL[j]で割った値をpにセットし、jに0をセット
---2.pがL[j]で割り切れない時
→jに1を加算
--4.リストPにpを加算
5.PNにcollections.CounterでPの値：個数の辞書を構成
6.PNの値xを順に読み込む。
-1.xが2以上の時
ansに(x*(x-1))//2を加算
7.ansを出力して終了
https://atcoder.jp/contests/abc342/submissions/50604911
以上