おはようございます。しほみんです。
ABC173です。今回はわりとあっさり早解きができてよかったです。E問題みたいな複雑なものをきちんと詰めて解答したかったなあと思います。
https://atcoder.jp/contests/abc173
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑を何とか維持。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在55回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCD、30分でした。C問題は何度も出た典型問題であっさり、D問題は考察を薦めればさっさと解けるのですんなり解けました。結局E問題は解けなかったのですが方針自体は立っていたのであと一歩だとおもました。早解きかつE問題もめどが経ったと思うので良かったなあって感じです。レーディングは1382で、レートは884→945で過去最高更新です。
今回はE問題まで振り返ります。（昨日の記事のとおり、ずっとゲームしていたのでE問題は振り返られるか怪しいです）
長くなるので前半はC問題まで書きます。
前回に引き続き考察をメインに書きます。
コードは別に上げます。
A問題
N円の商品を使います。
1000円札のみで払った場合、おつりはいくらですか？
考え方はいくつかありますが、
自分は1000円未満と1000円以上で場合分けをしました。
1000未満のときは1000-N円です。
1000円以上のときは
N%1000 == 0なら0円
それ以外はN/1000=tとして、(t+1)*1000- N円です。
t=N/1000とするとint型の割り算は切り捨て整数表記をするので枚数が出ます。
お釣りを出るために、t+1枚を払うのでそのような形をとります。
ほかにはstring型にして下3桁分で把握して、1000円から引くということも可能です。
A問題にしてはちょっとひねったなあという感じですね。
B問題
AXCコンテストを受けました。
テストケースがN個あって、それぞれ、AC, WA, TLE, REとして結果が出ます。
結果を
"AC x
WA x
TLE x
RE x"
として出力しなさい。
これは素直に実装します。
for文でn個分やって
それぞれ、AC, WA, TLE, REのときで場合分けしてカウントすればよいです。
注意点といえば、ACなどの後にある"x"の表記でしょう。
これ、エックスかばつか何かわからないです。
ここで違う文字入れるとWAになってしまうので、防がないとなりません。
一番簡単な方法は答のところをコピペしてしまうことです。
すると、全く同じになるので解決します。
意外と、仕様と一致させるとかで使える技術なので覚えておきましょう。
C問題
H行W列のマスがあります。白なら'.'、黒なら'#'と示されています。
列か行をそれぞれいくつか選んで、その行または列のところを赤く塗りつぶします。
黒がK個になる行と列の選び方が何通りあるか答えなさい。
真っ先に制約条件を見てみると、H,Wが両方6以下ということです。
ということは大体のアルゴリズムは間に合います。
ここでは、2の（H乗）や2の（W乗）に注目します。
列や行の選び方は、それぞれ選ぶか選ばないかの選択肢の2通りがあり、それが行と列分あるので、
2の(H+W乗)分あります。
今回、2の12乗=4096通りなので、1つのケースで、36個分のマスを調べて、その結果が妥当かどうか判断することをしても時間は余裕で間に合います。
よって、ここではbit全探索の手法を取ります。
これは、bitの0か1という性質を使って、どの列や行を選んだかを記録します。
例えば、0を選ばない、1を選ぶとすると、
001は、1列目のみを選ぶ
111は、1,2,3列目を選らぶ
110は、2,3列目を選ぶ
のようにできます。
あとは、この通り数ですが、1<<hのように表記します。
これは1をh bit分シフトするということでh=3のときは1000となり、10進数で8通りとなります。
よって、hとwそれぞれにおいてビット全探索で二重ループを作り、選んだ列や行以外で黒が何個残っているか数えて、K個であれば、カウントすればよいです。
bit全探索ってちょっととっつきにくいのですが、ABC128やABC147のC問題が該当します。いくつか問題をあたって復習してみましょう。
なにより、制約条件で最大でも15程度しかないので、異常にNが小さいときは疑ってみるとすんなり思いつきます。
最後に....
自分が最初に出てきたbit全探索の問題は緑diffだったのですが、今では茶diffになっていて、参加者の皆さんが勉強してレベルが高くなっているのがうかがえます。
D問題までは知らなかったら復習して身に着ければ、次から解けることは多いです。どんどん問題に挑んで新しい知識を身に着け、レベルアップしていきましょう。
ではでは。
