ABC283 (2022/12/24)
〇A問題
Yuto.icon pow
TTT.icon for文でc言語っぽく処理しました。
wataumi.icon 同上
TK.iconpowを使って計算、mathの方のpowを使ったが、結果がfloat型になっていたのでintでキャスト。
CarpDay.icon a**b
おたふく.icon CarpDay.icon に同じく
〇B問題
Yuto.icon A[k]を更新して出力するだけ
TTT.icon queryは2次元配列で受け取って、len ( query( i ) ) == 3 ならクエリ1, ==2 ならクエリ2と識別しました。
TK.iconクエリをリストで受けて最初の数字を見て条件ごとに処理。
wataumi.icon同上
CarpDay.icon 問題名の通り，クエリの練習問題
おたふく.iconクエリの1つ目の数で条件分岐
〇C問題
Yuto.icon 2桁以上残ってて00なら100倍，そうでなければ10倍して現在見ている桁を足せば良い．
TTT.icon len(S) - (S.count('00')) の1文だけで処理できました。そのことに気づくのに30分もかかっちゃったわけですが...汗
CarpDay.icon'10000'.count('00')は2になりました．3かもしれないな，と思っていました
wataumi.iconコンテスト中に再提出したものは上に同じです。一度目に提出したものは、下と方針は同じですが、Sの１０の位が０以外かつ１の位が0である場合が条件から抜けていました。
TK.icon数字を文字列として持って置き、文字列で一文字ずつループを回した。0以外ならカウントするだけ。0の場合は、前の文字を別変数で持って置き、それも0なら（2個連続なら）加算しないとした。
CarpDay.icon同上(^^)
おたふく.iconSのlistをforで回して、0が来た時に次の数も0なら添え字を1つ進めるという処理をした
〇D問題
Yuto.icon ()の処理は良いとして，問題はボールの処理．取り出す処理が重そう→区間更新のセグメント木？と思ってセグ木を調べていたけど，そんなもの要らないと気付く．j:iを更新する時，j～iを見るんじゃなくて，アルファベットを見れば26個しかない．(の位置を保持するstackと，全てのアルファベットが最後に入れられた時刻を保持しておけばok．
TK.icon多分本番中にＤ通ったの初かな？素直に文字を持つ集合を更新して行く方針で考えた。はじめは文字列をインデックスでまわして、"("のあるインデックスをスタックに保存して")"が出てきたときにスタックから取り出してi,jを確定。jからiまで回したがやはりTLE。ループを減らすためにどうすればいいか考えたとき、インデックスでなく(と(に囲まれた文字列をスタックに保存、後半の)と)に囲まれた文字列が確定するたびにスタックから取り出して集合から削除すればよくねと思いその方針で実装しAC。
TTT.icon 例1と例2の処理だけ見てそれを愚直にコーディングしたらWA2つを除いてすべてACでしたが、実は問題文の意味をしっかり理解できていません。WA2つを取り除こうと残り時間で奮闘していたわけですが、「良い文字列となる最大の整数」がどういう意味かしっかり理解できていなかったので、結局残りの2つをACに変えることはできませんでした。はじめてD問題ですべてACが出せそうだったので、悔しいです。「追記：」after contestで再度同じプログラムを提出したところ、ALLはAC、after_contest01.txtとafter_contest02.txtのうち01だけWAになってました。理由は分かりません。
CarpDay.icon二つ上の方と（多分）同じ(^^)
おたふく.icon残り3分でミスに気付きAC(感動)。Sをforで回して1文字ずつ別のlistに保存していき、' ) 'が出てきたら次に' ( 'が出てくるまでpopするようにした。
wataumi.iconコンテスト後に挑戦するもTLE。
〇E問題
Yuto.icon むずい．問題の意味が理解出来なかった
TTT.icon これ以降は見ていません。
TK.icon日本語が難しい... ぱっと見で問題の理解が難しかったので残り時間的にFの方が意味がわかるという理由でFへ
CarpDay.icon1時間考えた．DPも検討したが，最終的にはBFSで実装したが時間切れ．コンテスト後に実装するもBFSではTLE．DPで状態変数として保存する行を最後の1行ではなく2行にすればDPで実装可能なことに気付き，実装して何とかAC．コンテスト中に思いつきたかった．残念．
おたふく.icon時間内に解ける気はまだまだしないが、勉強会で学んだことが生きていることを実感。ただ、pythonでTLEで直すところが全然思いつかず、もしかしたらと思いpypy3で提出するとAC、pythonとpypyのそれぞれの強みと弱みを覚えて使い分けられるようになろうと思った。
〇F問題
Yuto.icon これ以降見てない．
TK.icon前回の学びを活かして、単純な組み合わせだけでなく完全グラフにして辺の重みで考えてみるなど多面的に考察してみたが、考察しているだけで時間切れ
CarpDay.icon少し確認した．全2点間だとO(N^2)なので，きっと順列であることが重要なんだろうけど思いつかずEに戻る．翌日に考えるも方針さえ思いつかずギブアップ．解説に記されたような式変形，コンテスト中にできるか！！と少し憤慨したが，別解に記されたようにマンハッタン距離での最短な点を求める問題，と考えればコンテスト中でも考えられたかも．セグメント木とマンハッタン全域最小木の勉強しっかりして，やっとこさAC