ABC196の感想

AtCoder Beginner Contest 196に参加しましたのでその感想を書いていきます。問題はこちらから。

結果はこんな感じでした。

ABC (27:26）
順位：2839 / 8630
パフォーマンス：914

いつも通りという感じでした。レートは少し下がりましたが、、でも今日は非常に落ち着いていたと思います。AB問題は特に誤読もなく、すんなりと頭に入ってきました。C問題も少し悩みましたが焦ることなく取り組めたかなと。
ただ、D問題に弾かれました。くやしい。

A問題

x-y の最大値を出力します。候補となりうるのは、a,b,c,d,0この辺の値をうまい感じに使ったときだな、と考えました。でもこれ以上考えるのは嫌だったもので、制約の小ささにかまけて全探索しました。これで無事AC。ひとまず、よい滑り出しでした。

B問題

小数点を含む数字の整数部分のみを出力します。言語によって難易度が結構変わるのはないのでしょうか。

今回はstringで文字列を受け取って、小数点の'.'が出現するまで出力しました。stringのままでいいのかなと思いつつ提出したら無事AC。次行きます。

C問題

n以下の前後が等しい数字の数を数えます。

まず、n 以下でどんな数字があるかを数えました。nが4桁の時には11-99の9個はOKで、1010 から n までのうちで繰り返しになるものを数え上げる。5桁の時は9個と1010から9999までの90個の99個、6桁の時は、、、

のようにさながら前回のC問題のように考えてました。もちろんこれでも解けると思いますが、どこかでバグを含みそうだなと思い、一旦立ち止まりました。

制約を見るとn<=1e12でしたので、今度はこちらから攻めようと思いました。n 以下となるを一旦無視して、前後の繰り返しとなる数って、その前半は1-999999までしかないことに気がつきました。

そこからは早かったです。1から1e6までをfor文で回して、

n >= i * 10 ^ (iの桁数) +&nbsp;I

で判定して数え上げ。これにて無事にAC。つぎつぎ！

D問題

畳を敷き詰める問題です。

先に言います。制約を勘違いしてました。縦横それぞれ16以下で、総面積256以下だと思ってました。でも実際は総面積16以下でした。コンテスト後に気がつきましや。

ですので、コンテスト中は256以下の制約のもとで考えてました。

まず。すぐにdpを使おうとなりました。構成は

dp[h][w][a][b][0or1]:

hi,wiマス,ai,bi個の畳を使用、今見ているマスに畳は敷かれているかどうか？

です。ただし、これだと遷移がいまいちわからず、一旦お預け。どうやって遷移するのかなーと考えたり、ググったりしていると、どうやらbitDPでいけるらしい。

dp[h][w][a][b][s]

ここでsは境界状態らしいです。この考えを実装して、動かして見るとサンプルが合わない合わない。これは困りましたね。

そのまま時間切れでした。

制約が小さければ全探索行けるのになー、とコンテスト中は考えてましが、なんか恥ずかしいですね。制約は小さいので全探索できます。

悔しさの残る問題でした。

E問題

Dの方がだいぶ正答率が高かったので見てないです。

F問題

こちらも見てないです。

あとがき

今回は問題の制約の読み間違いをしました。ただ、これって競技プログラミングの力といいよりももっと人間的な問題なので、この問題難しい、わからん、となるよりダメだと反省しています。でもやっぱり悔しいですね。解きたかった。

しっかりと復習をして強くなります。今日はそれまでの1ページということで、この結果を受け止めようかなと思います。がんばるぞ。

解答記事も早めに書き上げようと思ってます。現状はそう思ってます。明日のARCまでにはあげたいなと、現状はそう思ってます。

いつも以上にだらだらと書きましたが、ここまで読んでいただきありがとうございました！