ABC293参加記録
Published on 2023-03-17Last Modified 2023-09-22
Table Of Contents
ABC293参加してきました。(今更感)
もっとエントリ更新に力を入れると言っておきながらABC292の分をサボってしまいました。ABC293からすでに6日くらい経過していますが、一応有言実行ということで参加記録です。(すまんかった)
総評
今回の戦績です。
A, Bの2完でした。パフォーマンス375、レート変動553→535(-18)でした。
結果だけを見ると正直結構やらかしてしまったなという感じですが、ほとんど理解していないアルゴリズムが問われているので当然の帰結だと思います。あと、これで3週連続冷えなのでじわじわレートが下がっています。
問題など
今回は解けてはいないけどC問題まで紹介します。
A - Swap Odd and Even
問題文はこちらです。
操作によって文字列長が変化しない上、制約も優しいので普通にシュミレートすれば解けます。C言語等を使っている人はバッファオーバーランに気をつけましょう。この問題の制約下では文字列長が偶数になることがわかっているのでループ変数に2を加えていく方針でACできます。バッファオーバーランに気をつけるなら、操作に使う変数とループ変数を分けるのが良いでしょう。
B - Call the ID Number
問題文はこちらです。
こちらも基本的には言われたとおりにシュミレートすれば解ける問題になっています。ただし、A問題と比べて複雑になっているので注意深く問題分を読むべきだと思います。
「すでに番号を呼ばれた人」は割り当てられた番号を読み上げることができないので、これをシュミレートするために以下のような実装が考えられます。
-
人iが呼ぶ番号Aiを配列に格納する。(配列のi番目に人iの情報を入れる)
-
配列を最初から順に見ていって、「その要素番目」にある要素を-1(インデックスとして無効な値なら何でも良い)で上書きする。
最後にもう一度最初から見ていって、要素が-1になっていない人がまだ呼ばれていない人で、これはすでに昇順になっています。
配列が強すぎる
ACコード(前半はソート関数郡です。(必要なかった))
C - Make Takahashi Happy
問題文はこちらです。
経路上に存在する数字がかぶるかどうかを判定するためには、すべての経路を具体的に知っていなければいけません。すなわち、重複順列の全列挙です。そこで、いくつか方法があります。
私の取った方法はbit全探索です。0と1を「右に進む」「下に進む」に対応させることで重複順列をすべて列挙することができます。ビット数はw + h - 2になります。たぶん知らないとできません。
具体的には、最下位ビットの加算を行うたびに全ビットを見ていって、「下に進む」を表しているビットの総数がh - 1に到達したときに求めたい組み合わせの一つになります。高校数学を履修した人にとっては馴染み深い考え方かもしれません。(経路の数を求める問題で出てくるはずです。)
pythonやc++であれば、順列の列挙をするライブラリが利用できるはずなので、使い方を知っていればACしやすいと思います。C言語にそんなものはありません。(血涙)
完走した感想
今回のコンテストはちょうど対策が薄かったところばっかり出てきて中々苦しかったです。特に、組み合わせの列挙は近いうちの目標だったのですが、面倒くさくて放置していました。
D問題はグラフに関する問題が出ていました。まじでグラフをなんとかしないと茶色から落ちそうなのでがんばります。(C言語は動的配列のサポートが薄く、隣接リストを微妙に作りにくいからずっと面倒臭がって放置しています。)
全然関係ないけど200AC超えました。
それではまた次のエントリで