印象に残った問題（TC編）
SRM553 Div2 Easy「PlatypusDuckAndBeaver」
全探索でも十分間に合うが、算数の問題として解ける。
その結果↓
class PlatypusDuckAndBeaver{
public:
int minimumAnimals(int webbedFeet, int duckBills, int beaverTails){
return webbedFeet/2-beaverTails;
}
};
印象に残った問題（CF編）
Codeforces 245H 「Queries for Number of Palindromes」
累積和で解くのがよいそうです。
自分は、dp[a][b]=string[a]からstring[b]の部分文字列内に含まれる回文数として、string[a]からstring[b]の部分文字列が回文:
dp[a][b]=dp[a+1][b]+dp[a][b-1]-dp[a+1][b-1]+1
回文ではない:
dp[a][b]=dp[a+1][b]+dp[a][b-1]-dp[a+1][b-1]
と計算しました。
また、
回文のうち、すべての文字が等しくないと、後ろに1文字付け加えた時に回文にならない。すべての文字が等しく、かつ付け加える文字がその等しい文字だったときのみ回文になる。
という事実を使ったところ、TLE→ACになりました。
以下ソースコード↓(AC 2012/11/23)
コードの編集について
コードのよい乗せ方を知っている方、教えてください＞＜
今まで解いた印象的な問題(AOJ編）
0557 JOI 2010 予選 4番 「一年生」
普通のDP。0~20の範囲を外れたものを無視すればよい。
以下ソースコード↓（AC 2012/9/30)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=496880
0524 JOI 2007 予選 4番「星座探し」
星座を構成するn個の星をそれぞれの星m個に対応させて、すべて一致すればOK。
以下ソースコード(AC 2012/10/08)↓
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=532267
0573 JOI 2012 本選 3番「夜店」
典型DP。Sをまたぎ超すときは更新しない。それだけ。
以下ソースコード↓(AC 2012/11/15)
(コード内の/*DEGwer*/とは、手持ちのエディタで行番号が3456になったからです^^）
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=525755
0569 JOI 2012 予選 5番「イルミネーション」
全体を一回り大きくし、(0,0)から隣接している六角形のうち、建物がないなら建物に囲まれていないマスとする。これをすべて行った後、建物のある座標から周囲6方向に進み、建物に囲まれてないマスにであったら、周囲の長さに1を足す。
以下ソースコード↓(AC 2012/10/06)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=499954
AOJ 0560
JOI 2011 本選 1番「惑星探索」
二次元累積和の問題らしい。
左上の頂点の座標が(1,1)、右下の頂点の座標が(x,y)である長方形内に含まれる要素の数をnum[x][y][3]とすると、(num[x][y][0]は"J"の数、num[x][y][1]は"O"の数、num[x][y][2]は"I"の数)
左上の頂点の座標を(a,b)、右下の頂点の座標を(c,d)の長方形に含まれる要素数は、
num[c][d][a]-num[c][b-1][a]-num[a-1][d][a]+num[a-1][b-1][a]
(0<=a<3)
で計算される。
以下、ソースコード↓
#include <cstdio>int exist[1001][1001][3]={};char field[1001][1001];int m,n,Q;int main(){ scanf("%d %d %d",&m,&n,&Q); for(int i=0;i<m;i++){ scanf("%s",field[i]); } for(int i=0;i<m;i++){ for(int j=i;j<m;j++){ if(field[i][0]=='J'){ exist[j][0][0]++; }else if(field[i][0]=='O'){ exist[j][0][1]++; }else{ exist[j][0][2]++; } } } for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(field[0][i]=='J'){ exist[0][j][0]++; }else if(field[0][i]=='O'){ exist[0][j][1]++; }else{ exist[0][j][2]++; } } } if(field[0][0]=='J'){ exist[0][0][0]=1; }else if(field[0][0]=='O'){ exist[0][0][1]=1; }else{ exist[0][0][2]=1; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ for(int k=0;k<3;k++){ exist[i][j][k]=exist[i][j-1][k]; } for(int k=0;k<=i;k++){ if(field[k][j]=='J'){ exist[i][j][0]++; }else if(field[k][j]=='O'){ exist[i][j][1]++; }else{ exist[i][j][2]++; } } } } for(int i=0;i<Q;i++){ int a,b,c,d; scanf("%d %d %d %d",&a,&b,&c,&d); if(a>=2 && b>=2){ printf("%d %d %d\n",exist[c-1][d-1][0]-exist[c-1][b-2][0]-exist[a-2][d-1] [0]+exist[a-2][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1]-exist[a-2][d-1][1]+exist[a-2][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]-exist[a-2][d-1][2]+exist[a-2][b-2][2]); }else if(a<2){ printf("%d %d %d\n",exist[c-1][d-1][0]-exist[c-1][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]); }else{ printf("%d %d %d\n",exist[c-1][d-1][0]-exist[a-2][d-1][0],exist[c-1][d-1][1]-exist[a-2][d-1][1],exist[c-1][d-1][2]-exist[a-2][d-1][2]); } } return 0;}後半が滅茶苦茶になってしまった＞＜
