ゆらのふなびと

競プロ, Python, C++

Codeforces の Good Bye 2015 に参加しました

解けた問題から順に解説を書いていきます。

結果

f:id:pakapa104:20151231141250p:plain

Aしか解けんかった。

とりあえずAはひたすらif文書いてやりすごした。Bはビットの話が全然わからないので飛ばしてCは処理速度が足りなかった。Dは再帰?と思ったけど再帰もよくわかってないしEは場合分けややこしすぎてギブ。後はもうしらない……

A. New Year and Days

codeforces.com

「毎週○曜日」あるいは「毎月○日」でキャンディーを貯めていくと、2016年中にいくつ貯まりますかという問題。なお、2016年は金曜日から始まる。

とりあえず2016年はうるう年だったよな? オリンピックあるし。ということは1年は366日で2月は29日まである。31日まである月は2,4,6,9,11以外の7個……以上を踏まえてひたすらif文を書いた。

s = raw_input().split()
x = int(s[0])
ans = 0
if s[2] == "week":
    if x == 5 or x == 6:
        print 53
    else:
        print 52
else:
    if x <= 29:
        print 12
    elif x == 30:
        print 11
    else:
        print 7

みなさんのsubmitを見てると配列使って2,3行で済ませてたりしてかっこいいんですけど、それを試みてミスるの怖かったので……(チキン)

B. New Year and Old Property

codeforces.com

a以上b以下の正の整数を2進数表示したとき、0をちょうど1個だけ含むような数はいくつあるか。a,bの範囲が<=10**18とでかいので、効率のよい計算をしないといけない。とりあえずビットの計算するんだろうな……ということはわかったけどビットよくわからないので本番では飛ばした問題。


まずはビットのお勉強から。

qiita.com

ふむふむ。なかなか便利らしいぞ。特にシフトのあたりはこの問題でも使いそう。


さて問題に戻ると、「2進数表示したときn桁の数」の中には、「0が1個だけ現れる数」はn-1個あるということがわかります。(例:n = 4 → 1110, 1101, 1011の3個)

これを踏まえて、条件を満たす数を順に探していきましょう。たとえばa = 5(101), b=10(1010)だとすると、

  1. 4桁の数:
    • 1110 > 1010 → 不採用
    • 1101 > 1010 → 不採用
    • 1011 > 1010 → 不採用
  2. 3桁の数:
    • 101 <= 110 <= 1010 → 採用
    • 101 <= 101 <= 1010 → 採用
  3. 採用されたのは2個なので、答えは2個


これをコードに落としこんだものが以下になります。言葉で解説すると、

  1. bと同じ桁の'1'だけのビット列cを用意する(c=1111)
  2. 最上位だけが1,他は0のビット列jをつくる(j=1, 10, 100,...)
  3. a <= c-j <= b なら採用
  4. cの桁を1つ減らして2に戻る

という感じです。

a, b = map(int, raw_input().split())
c = 2
while c <= b:
    c *= 2
c -= 1
ans = 0
while c > 1:
    j = 1
    while (j<<1) < c:
        if c-j >= a and c-j <= b:
            ans += 1
        j <<= 1
    c >>= 1
print ans

もっと効率化するとしたら、 * cが1桁になるまで計算している→aの桁までにする * c-jが[a,b]の範囲に入っているかの判断を毎回している→端の方だけにする という辺りでしょうか。私はよくわかってないのでやりません

C. New Year and Domino

codeforces.com

縦hマス横wマスの長方形の紙があります。各マスは正方形で、'.'(空き)か'#'(forbidden)で表現されます。シロクマくんはこの紙に12の長方形を1個埋めたいです。さて埋め方は何通りあるでしょう、という問題。

<ポイント>

  • クエリが来るごとに計算していると無駄なので先に「端からある点まで何通りか」を求めておく
  • 「左上から[i,j]まで」だと計算がよくわからないので、横方向と縦方向で配列を分ける
  • クエリが与えられたら、その範囲内で列ごと、行ごとの場合の数を配列の引き算によって計算し足し上げる

何言ってるかよくわからないと思うのでコードです(まったく同じのをPythonで書いてたんですがどうしても通らなかったのでC++にしました)

#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>

using namespace std;

char grid[505][505];
int dp_row[505][505];
int dp_col[505][505];

int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>grid[i][j];
        }
    }

    for(int i=0;i<=h;i++){
        dp_row[i][0] = 0;
    }
    for(int j=0;j<=w;j++){
        dp_row[0][j] = 0;
    }

    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            dp_row[i][j] = dp_row[i][j-1] + (grid[i][j] == '.' && grid[i][j-1] == '.');
            dp_col[i][j] = dp_col[i-1][j] + (grid[i][j] == '.' && grid[i-1][j] == '.');
        }
    }

    int r1,c1,r2,c2,q;
    cin>>q;
    while(q--){
        cin>>r1>>c1>>r2>>c2;
        int cnt = 0;
        for(int i=r1;i<=r2;i++){
            cnt += dp_row[i][c2] - dp_row[i][c1];
        }
        for(int j=c1;j<=c2;j++){
            cnt += dp_col[r2][j] - dp_col[r1][j];
        }
        cout<<cnt<<endl;
    }

    return 0;
}

C++久しぶりすぎて書き方忘れてた。諸氏のコードを参考にしながらなんとかクリア……。

ていうかdpって書いたけどこれはほんとにdpなのだろうか。

<追記>

どうやらこれは「累積和」という手法を用いる問題らしい。

paiza.hatenablog.com

paiza.hatenablog.com

kenkoooo.hatenablog.com

今回の問題はマスにまたがって長方形が置かれるからややこしいんだな。そうでない場合は割とシンプル

D. New Year and Ancient Prophecy

解くぜ!