2022年2月11日
うーーーーーーーーーーーーーーーーーーん
メロンティーお願いします。あ、氷抜きで。
そういえば
新年のあいさつ忘れていました~~~
あけましておめでとうございます。
あ、いえいえ、私は別に何もしていないですよ、、、でもありがとうございます。
今日の一曲。湊あくあ きらきら
湊あくあ、ApeXソロマスターおめでとうございます。
今日の問題
ABC225 C - Calendar Validator
- [書けばわかる、サンプルがすべてじゃない、オーバーフローしない、灰diff]
灰色diffだけど、そこそこ難しい。サンプルが通っても勝ちじゃない
書けばわかるんだけど、行列Aを書くと、こうなるよ
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
最初、(i-1) * 7 + j を (i-1) * (7+ j)と誤解していて厄介になっちゃった。
解き方
for(int i = 0; i < n; i++){ int a = b[i][0]; //解き方、サイズn * m の行列bが与えられたら、同じ行内で一番列的に左のものをaとして if(i != 0){ if(a != b[i-1][0]+7){ cout << "No" << endl; //1行上のもの+7じゃないとダメ return 0; // プログラムを終了 } } for(int j = 0; j < n; j++){ if(b[i][j] == a+j){ // a+jなら、ok } else { cout << "No" << endl; return 0; // プログラムを終了する } } }
これで通るかなって思ってサンプル回すと、サンプルは通ります。しかしWAです。なんでかわかりますか…?
上の行列Aの表を見てみると、同じ行の7つの数字には、ある特徴があります。
7で割ったときの切り上げが同じ。です。
よって、行列Bに関して言えば、同じ行のmつの数字を7で割ったときの切り上げが全部同じじゃないといけません。
int roundUp = (a[i][0] + 6) / 7; for(int j = 0; j < m; j++){ if((a[i][j] + 6) / 7 == roundUp) continue; else { cout << "No" << endl; return 0; } }
こんな感じなコードを足してYes/No判定すれば、okです。round up で切り上げって意味らしいです。
あ、そうそう、行列Aの成分に関して言えば、long long で収まらない数字もあるんですけど、行列Bの要素の制約は、int型に収まっていますね
行列A書いてみてわかったと思うけど、行列Aにはint型に収まるすべての整数が入っていることが分かるね。だから、行列Bの要素が上のようなYes/No判定してあげればいいってわけ。
荻野風に言うと、「ただな、この条件判定を覚えたからと言って、行列Bに64bitを超える整数が与えられたときに解けるようになったと思うんあ。所詮、int型に収まるように作られた競プロという問題の中でしかぁー、いっ、生きていけない解答に過ぎないんだ。いいかぁー?だから、ACするためだってそれでいいんだよ。ぉーん。ぃぃかー?」