競プロ

ABC118に参加してきた

こんにちは!チズチズです。

久しぶりのブログ更新となりました。

ABC1180

僕の結果は、42分で3完でした。(遅い…

今回のABCはいつもよりかは簡単?だったかなぁという印象です。

基礎的なものが問われたのでDPまとめや過去問をしっかり解いていたら対応できると思います。

A問題

AとBが入力され、BがAの約数ならB+A、約数でなければB-Aを出力するという問題です。

最初読み間違えて符号を間違えてしまいましたが…

問題のとおりですね。

AがBの約数だったらB÷Aの余りは0であるはず!

これを利用します。

A問題は分岐を使った基礎問題ですね。

B問題

これC問題より難しいと思いました。

僕が考えたのはN*Mの2次元配列を作って、好きと答えたらその人の番号と答えた物の番号にフラグ立てるというものです。

図は汚いですが、こんな感じです。2次元配列を作成して答えたものにメモ(True)していきます。

最後に答えですが、全員が好きと答えたものなので、この配列を縦に見て全てTrueだったらOKみたいにします。

この縦に見る方法なのですが、Numpyであるような転置です。

(もちろんインポートしてわざわざやらないけど

Python Codeを優雅に

この記事を見て、転置をしました。

後は転置済みの配列をforに突っ込んで全てTrueだったら1を出して総和を取ります。

注意してほしいのが2次元配列の初期化です。

[[m]*n]*n のようにすると更新のときに値がおかしくなります。

静的確保しないと大変です。(気付くのに20分掛かった

リスト内包表記で初期化しましょう

Pythonで2次元配列の静的確保と動的確保

色んな解法はありましたが、これが視覚的にもわかりやすいかなと思います。

C問題

誰が攻撃するにしても全員に攻撃するわけだからリストAの最大公約数を取れば終わりです。

3つ以上ある内の最大公約数はこんな感じで総当たりで小さいものを取れば完了ですね。

最大公約数はmathライブラリのgcd関数で出来ますが、AtCoderの環境に無かったので自分で組みます。ユークリッドの互除法については調べて……

最大公約数は一気にはわからないので総当たりした中の一番小さい値を取ります。

今はa[0]が攻撃したことになってますが、1でも2でも変わりません。

D問題

DはDPのDでしたねw

まずマッチの本数分だけループ回します。

その後、そのi本で作れる数を探します。もちろん1番大きい数がいいので、maxで取ります。

D問題難しかったようで周りは結構簡単と言ってましたね…(DPの基礎らしい)

この問題、文字で説明するの難しいです…

7から77のところは繰り上げされています。このようなことをして最大値を求めます。

下のコードや人のコードを見ると多分分かってきます。(多分

まとめ

今回のD問題はDPをちゃんと理解していれば対応出来たかと思います。

個人的にB問題で2次元配列を動的に確保していて要素がおかしくなって詰まったところを反省しています。(そこで静的に確保していれば20分は早く解けた…

DPまとめも数週間?1ヶ月位前にあったのでその問題もやって対策していきたいです。

C++もちゃんとやりたい…

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です