htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 029

oox--- 1542 -> 1560

A - Irreversible operation

AC: Submission #3794678 - AtCoder Grand Contest 029

完全にあさっての方向に突っ走ってしまい20分もかけてAC。AC時の順位が4桁で配点的にもう一問解ける保証もなかったしほんと涙目だった。BWBWBWのテストケースを紙の上でシミュレートしたとき書き換えられる部分がピラミッド状に積み上がったので、各区間ごとに和の公式を取ればいいのでは的な方向でしばらく時間を潰してしまったが、単に各Wの左にあるBを数えるだけだった(逆でも可)。スワップごとにWが左にBが右に移動するのでWとBですれ違える回数を数える。

B - Powers of two

AC: Submission #3799094 - AtCoder Grand Contest 029

問題文を読む限りどうしてもフローとか最大流とかの問題としか見られなくて、ちょっと考察してみても、例えば

1 1 3 5 7 15

   ┌5
┌─ 3 ─┐
1─ 7 ─1
└─15─┘

のように取り合いが発生し、うまくやれば3ペア作れるけど1と3をマッチングさせちゃうと2ペアしか作れないので、これマッチング問題ってやつだアルゴリズムも考え方も知らないから解けね−っとパスしそうになった。

しかしこれ、例えば

 3 (0011)
 5 (0101)
11 (1011)

の場合、5は3とペアにすると8(1000)が、11とだと16(10000)が作れるが、逆に最も大きな数である11から見ると、自分に抜けているビットを埋めた数+1、つまりペアになる数は一意に定まる。自分以下の数とペアを組んで2べきを作る場合、結局2進数で1桁上がった数を目指すしかない(1011 -> 10000)ので、大きい方から貪欲でマッチさせていくと選択肢の狭い方からマッチさせていくことになるので最適。

数列の数の出現回数を数えて、大きい方からペアを作っていき、ペアになった小さい側の数の出現回数をmin(大きい数の個数, 小さい数の個数)分減らし同じ数を答えに加算していく。最初から2べきの数は自分同士をペアにすることで上の2べきが作れる点に注意(1WA)。

C - Lexicographic constraints

辞書順に並んだ文字列という設定だけどこれはx進数の数字と読み替えても問題なく、各桁を管理しながら何進数だと桁があふれないか答えよという問題。

max(数列) <= 10^9 よりナイーブに実装しようとすると時間計算量も空間計算量も足りないのだけど、そもそも109くらい長い文字列がいくら積もろうとものっ凄い小さい数がこちゃこちゃと繰り上がっていくだけでそれが上位桁まで上がってくることなんて無いんだから無視して良くない?っていうのが必須の気づきポイント。それどころか 2^18 = 262144 > N = 200000なんだから文字数18が200000個並んでいても全て2種類の文字で表現しきれてしまうわけで、上位18桁くらいだけ保持しておきそれ以上の文字数の文字列は全無視でいい。ただし数列が狭義単調増加の場合は1が答えになるのでこのケースは事前に処理しておく。

ここまでは割とするっと思いついたのだけど、文字数2から始めて繰り上がりを処理していく過程で文字数を増やさざるを得なくなったときにその場で文字数を増やすような貪欲で実装していったのでWAが取れず。増やさざるを得なくなる前に先に文字数を増やしておいたほうがいいケースが思い当たり、あっこれ二分探索???とよぎったのが終了1分前。Ω\ζ°)チーン

AC: Submission #3805697 - AtCoder Grand Contest 029

pythonだとかなり頑張らないと通せない系なので頑張った。今気づいたけど10行目の枝狩りはインチキっぽい。2 4 3と真ん中を捨てた2 3って同じじゃないよな……。