情報オリンピック夏季セミナー 2013 小学生並の参加記
後になるほど失速します
8月26日(月曜日)
やる気に満ち溢れている．
8月27日(火曜日)
まだちゃんとやる気がある．
8月28日(水曜日)
突然やる気がなくなって，文章とりあえず半分まで書けばいいみたいな感じになる．
8月29日(木曜日)
やる気のかけらもない．
8月30日(金曜日)
もうどうにでもなれ．
Google Code Jam 2013 Qual
長く苦しい戦いだった……．ソースを載せます．
A (LOLCODE)
一番苦労した．言語の公式サイトにつながらないし，WebArchiveからSpecificationを探してきて頑張って書いた．特に超不便な連想配列しか用意されていない点や，文字列の i 番目にアクセスすることができない点は辛かった．後者は特にどうしようもなかったので Python で input を改行区切りに変換するスクリプトを書くことで対処した．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A BRD ITZ A BUKKIT
I HAS A ROW ITZ 0
I HAS A COL ITZ 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
IM OUTTA YR RDLPC
BRD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
I HAS A DTRMND ITZ FAIL
ROW R 0
IM IN YR RLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
COL R 0
IM IN YR RLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR RLPC
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR RLPR
COL R 0
IM IN YR CLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A XC ITZ 0
I HAS A OC ITZ 0
I HAS A TC ITZ 0
ROW R 0
IM IN YR CLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS COL, WTF?
OMG "X", XC R SUM OF 1 AN XC, GTFO
OMG "O", OC R SUM OF 1 AN OC, GTFO
OMG "T", TC R SUM OF 1 AN TC, GTFO
OIC
IM OUTTA YR CLPR
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XC AN BIGGR OF XC AN 3 AN BOTH SAEM SUM OF XC AN TC AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OC AN BIGGR OF OC AN 3 AN BOTH SAEM SUM OF OC AN TC AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
IM OUTTA YR CLPC
I HAS A XCDA ITZ 0
I HAS A OCDA ITZ 0
I HAS A TCDA ITZ 0
ROW R 0
IM IN YR DIAGA UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
I HAS A TML ITZ BRD'Z SRS ROW, TML'Z SRS ROW, WTF?
OMG "X", XCDA R SUM OF 1 AN XCDA, GTFO
OMG "O", OCDA R SUM OF 1 AN OCDA, GTFO
OMG "T", TCDA R SUM OF 1 AN TCDA, GTFO
OIC
IM OUTTA YR DIAGA
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDA AN BIGGR OF XCDA AN 3 AN BOTH SAEM SUM OF XCDA AN TCDA AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDA AN BIGGR OF OCDA AN 3 AN BOTH SAEM SUM OF OCDA AN TCDA AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A XCDB ITZ 0
I HAS A OCDB ITZ 0
I HAS A TCDB ITZ 0
COL R 0
IM IN YR DIAGB UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS COL, TML'Z SRS DIFF OF 3 AN COL, WTF?
OMG "X", XCDB R SUM OF 1 AN XCDB, GTFO
OMG "O", OCDB R SUM OF 1 AN OCDB, GTFO
OMG "T", TCDB R SUM OF 1 AN TCDB, GTFO
OIC
IM OUTTA YR DIAGB
NOT DTRMND, O RLY?
YA RLY, BOTH OF BOTH SAEM XCDB AN BIGGR OF XCDB AN 3 AN BOTH SAEM SUM OF XCDB AN TCDB AN 4, O RLY?
YA RLY, VISIBLE "X won", DTRMND R WIN
MEBBE BOTH OF BOTH SAEM OCDB AN BIGGR OF OCDB AN 3 AN BOTH SAEM SUM OF OCDB AN TCDB AN 4
VISIBLE "O won", DTRMND R WIN
OIC
OIC
I HAS A DC ITZ 0
ROW R 0
IM IN YR DCNTLR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN 4
COL R 0
IM IN YR DCNTLC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN 4
I HAS A TML ITZ BRD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN ".", O RLY?
YA RLY, DC R SUM OF 1 AN DC
OIC
IM OUTTA YR DCNTLC
IM OUTTA YR DCNTLR
BOTH OF NOT DTRMND AN BOTH SAEM DC AN 0, O RLY?
YA RLY, VISIBLE "Draw", DTRMND R WIN
OIC
NOT DTRMND, O RLY?
YA RLY, VISIBLE "Game has not completed"
OIC
IM OUTTA YR LOOP
KTHXBYE
B (LOLCOCDE)
内容的にも慣れ的にも明らかに A より楽だった．
HAI 1.3
I HAS A CSN ITZ A NUMBR
GIMMEH CSN
I HAS A CURCS ITZ 0
IM IN YR LOOP UPPIN YR CURCS WILE DIFFRINT CURCS AN BIGGR OF CURCS AN CSN
I HAS A RWS
I HAS A CLS
GIMMEH RWS
GIMMEH CLS
RWS IS NOW A NUMBR
CLS IS NOW A NUMBR
I HAS A FLD ITZ A BUKKIT
I HAS A ROW ITZ A NUMBR
I HAS A COL ITZ A NUMBR
ROW R 0
IM IN YR RDLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
I HAS A LNE ITZ A BUKKIT
IM IN YR RDLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
LNE HAS A SRS COL
GIMMEH LNE'Z SRS COL
LNE'Z SRS COL IS NOW A NUMBR
IM OUTTA YR RDLPC
FLD HAS A SRS ROW ITZ LNE
IM OUTTA YR RDLPR
I HAS A HGHT ITZ 1
IM IN YR CTLP UPPIN YR HGHT WILE BOTH SAEM HGHT AN SMALLR OF HGHT AN 100
ROW R 0
IM IN YR CTLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CTLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW, BOTH SAEM TML'Z SRS COL AN HGHT, O RLY?
YA RLY
I HAS A RC ITZ 0
I HAS A CC ITZ 0
I HAS A TR ITZ 0
I HAS A TC ITZ 0
IM IN YR CNTLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR
EITHER OF BOTH SAEM TTML'Z SRS COL AN HGHT AN BOTH SAEM TTML'Z SRS COL AN 0, O RLY?
YA RLY, RC R SUM OF 1 AN RC
OIC
IM OUTTA YR CNTLPR
IM IN YR CNTLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TC AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW
EITHER OF BOTH SAEM TTML'Z SRS TC AN HGHT AN BOTH SAEM TTML'Z SRS TC AN 0, O RLY?
YA RLY, CC R SUM OF 1 AN CC
OIC
IM OUTTA YR CNTLPC
BOTH SAEM RC AN RWS, O RLY?
YA RLY
TR R 0
IM IN YR FLDLPR UPPIN YR TR WILE DIFFRINT TR AN BIGGR OF TR AN RWS
I HAS A TTML ITZ FLD'Z SRS TR, TTML'Z SRS COL R 0
IM OUTTA YR FLDLPR
OIC
BOTH SAEM CC AN CLS, O RLY?
YA RLY
TC R 0
IM IN YR FLDLPC UPPIN YR TC WILE DIFFRINT TC AN BIGGR OF TR AN CLS
I HAS A TTML ITZ FLD'Z SRS ROW, TTML'Z SRS TC R 0
IM OUTTA YR FLDLPC
OIC
OIC
IM OUTTA YR CTLPC
IM OUTTA YR CTLPR
IM OUTTA YR CTLP
I HAS A K ITZ WIN
ROW R 0
IM IN YR CHKLPR UPPIN YR ROW WILE DIFFRINT ROW AN BIGGR OF ROW AN RWS
COL R 0
IM IN YR CHKLPC UPPIN YR COL WILE DIFFRINT COL AN BIGGR OF COL AN CLS
I HAS A TML ITZ FLD'Z SRS ROW
K R BOTH OF K AN BOTH SAEM TML'Z SRS COL AN 0
IM OUTTA YR CHKLPC
IM OUTTA YR CHKLPR
VISIBLE "Case #" AN SUM OF 1 AN CURCS AN ": "!
K, O RLY?
YA RLY, VISIBLE "YES"
NO WAI, VISIBLE "NO"
OIC
IM OUTTA YR LOOP
KTHXBYE
C (J言語)
J言語は書きやすい言語です．これだけははっきりと真実を伝えたかった．
load'printf'
OUT =: 'C:\GCJ\qual2013\c.out'
S =. 1!:1 <'C:\GCJ\qual2013\c.in'
states =. 3 : 0
0 10 #: <. 10 * > -.&a: <@".;._2] 0 :0
)
splitWord =. 0;(states'');a.e.CRLF,LF
1.1 0
1 0.3
)
input =: splitWord ;: S
T =: ".>{.input
input =: }.input
largeSqrt =: 3 : 0
'lo hi' =. 0; y + 1
while. 1<hi-lo do.
mid =. <.-:hi+lo
if. y>:*:mid do. lo=.mid else. hi=.mid end.
end.
lo
)
comb=: 4 : 0
if. x e. 0 1 do. z=.<((x!y),x)$ i.y
else. t=. |.(<.@-:)^:(i.<. 2^.x)x
z=.({.t) ([:(,.&.><@;\.)/ >:@-~[\i.@]) ({.t)+y-x
for_j. 2[\t do.
z=.([ ;@:(<"1@[ (,"1 ({.j)+])&.> ])&.> <@;\.({&.><)~ (1+({.j)-~{:"1)&.>) z
if. 2|{:j do. z=.(i.1+y-x)(,.>:)&.> <@;\.z end.
end.
end.
;z
)
palindrome =: (=|.)@":
solveL =: 3 : 0
if. y=1 do. 4 return. end.
ks =. 1,(i.4)!<:<.-:y
+/ks*>(2|y){1 1 1 1 1;2 3 3 2 2
:
if. y=1 do. 4<.>:x return. end.
res =. 0
if. (t<:x)*.palindrome t=.2+2*10x^<:y do. res =. res+1 end.
if. (1=2|y)*.(t<:x)*.palindrome t=.t+10x^<.-:y do. res =. res+1 end.
for_p. i.4<.>:d=.<:<.-:y do.
res =. res + +/x>:s=.(>:10x^<:y)+((10x^>:d+2|y)*(+/"1)10x^cs-~<:d)+10x*(+/"1)10x^cs=.p comb d
res =. res + (2|y)*+/x>:s+10x^<.-:y
res =. res + (2|y)*(2>p)*+/x>:s+2*10x^<.-:y
end.
res
)
solve2 =: 3 : 0
N =. largeSqrt y
res =. 0
for_d. >:i.#":N do.
if. d=#":N do. res =. res + N solveL d
else. res =. res + solveL d end.
end.
res
)
solve1 =: 3 : 0
'A B' =: y
-/solve2"0 B,<:A
)
replace=: 4 : 0
'p q'=. y
j=. p nosindx x
if. ''-:j do. x return. end.
d=. p-&#q
k=. (j+(0>.-d)*i.#j)+/i.#q
select. *d
case. 1 do. (0 (j+/(#q)+i.d)}1$~#x) # q k}x
case. 0 do. q k}x
case. _1 do. q k} (0 (d{."1 k)}1$~(#x)+(#j)*|d) #^:_1 x
end.
)
nosindx=: 4 : 0
s=. x I.@E. y
i=. s I. s+#x
(i.&_1 {. ]) (s,_1) {~ (i,_1) {~^:a: 0
)
solve =: 3 : 0
'' 1!:2 <OUT
for_n. >:i.T do.
ps =. 'x',~(>(<:n){input) replace ' ';'x '
('%d\n' sprintf n) 1!:2 <2
('Case #%d: %d\n' sprintf (n,solve1".ps)) 1!:3 <OUT
end.
)
solve''
20歳になりました
2013年です．0〜20まで数えて感慨深い思いに浸りましょう．
/: 2013
# 2013
{. 2 013
{: 201 3
# 2 0 1 3
p: {. 2 013
+/ 2 01 3
p: {: 201 3
2 ^ {: 01 3
2 ^~ {: 01 3
+/ }. p: 2 01 3
2 0 1 p. 3
+: +/ 2 01 3
}. 2 013
2 * {: p: 01 3
+/ p: 2 01 3
2 ^ +/ 01 3
p: +/ 2 01 3
<. o. +/ 2 01 3
p: p: {: 201 3
{. 20 13
【「『JOI 2011年春合宿 Day1 の問題『Dragon』は強実装』はウソ」はウソ】はウソ
http://tozangezan.hatenablog.com/entry/2013/03/29/004026
upper_bound や lower_bound を使いまくったり， -1, -2 を乱発したりしない Dragon の実装が求められているそうなので書きました．
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long long Int; int H, W, N; struct dragon { int x, y; } D[100050]; bool cmpx(const dragon& a, const dragon& b) { return a.x != b.x ? a.x < b.x : a.y < b.y; } bool cmpy(const dragon& a, const dragon& b) { return a.y != b.y ? a.y < b.y : a.x < b.x; } struct event { int x, y; bool query; event(int x, int y, bool q) : x(x), y(y), query(q) { } }; bool operator < (const event& e, const event& f) { return e.y < f.y; } int solve() { int res = 0; vector<int> xr, yd; for (int i = 0; i < N; ++i) { xr.push_back(D[i].x); yd.push_back(D[i].y); } sort(xr.begin(), xr.end()); sort(yd.begin(), yd.end()); xr.erase(unique(xr.begin(), xr.end()), xr.end()); yd.erase(unique(yd.begin(), yd.end()), yd.end()); vector<event> es; sort(D, D + N, cmpx); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].x == D[j].x; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, false)); } sort(D, D + N, cmpy); for (int i = 0, j; i < N; i = j) { for (j = i; j < N && D[i].y == D[j].y; ++j) ; es.push_back(event(D[j - 1].x, D[j - 1].y, true)); } sort(es.begin(), es.end()); set<int> xs; for (int i = 0; i < (int)es.size(); ++i) { if (es[i].query) { int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr); } else { xs.insert(es[i].x); } } return res; } int main() { cin >> H >> W >> N; for (int i = 0; i < N; ++i) { cin >> D[i].y >> D[i].x; --D[i].x; --D[i].y; } set<int> xs, ys; for (int i = 0; i < N; ++i) { xs.insert(D[i].x); ys.insert(D[i].y); } Int sol = (Int)H * W - (Int)H * xs.size() - (Int)W * ys.size() + (Int)xs.size() * ys.size(); int M = 0; for (int rot = 0; rot < 4; ++rot) { for (int flip = 0; flip < 2; ++flip) { M = max(M, solve()); for (int i = 0; i < N; ++i) { D[i].y = H - D[i].y - 1; } } swap(H, W); for (int i = 0; i < N; ++i) { int x = D[i].x, y = D[i].y; D[i].x = y; D[i].y = H - x - 1; } } cout << sol + M << endl; return 0; }
例によって main は回転などをしているだけ，solve も大半は座標圧縮などの造作も無い処理です．問題の箇所がこちら．
int rr, dd; dd = yd.end() - upper_bound(yd.begin(), yd.end(), es[i].y); set<int>::iterator it = xs.upper_bound(es[i].x); if (it != xs.end()) { rr = xr.end() - upper_bound(xr.begin(), xr.end(), *it); res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd); } rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1); res = max(res, W - (es[i].x + 1) - 1 - rr);
upper_bound のみ 4 回使用，いずれも単純な呼び出しにとどまっていると思います．また +1, -1 などについては
res = max(res, (H - es[i].y - 1) + (W - *it - 1) - rr - dd);
これは逆順に走査するときなどによく見る N - i - 1 の形です．また
rr = xr.end() - upper_bound(xr.begin(), xr.end(), es[i].x + 1);
こちらはドラゴンのいる x 座標(es[i].x) の隣に M 理事長が居る場合を考えるので +1 をつけています．そして
res = max(res, W - (es[i].x + 1) - 1 - rr);
これは上ふたつの複合です．
少なくとも「人が死ぬレベル」「複雑すぎる」といった形容は必要ない程度にはシンプルにまとまったと思います．
「強実装は多実装ではありません。『手ごわい』実装なのです。」という理解は正しいと思います．「強実装」という概念には単に記述量が多いだけでなく，正しく書きづらい，複雑な記述になってしまう，デバッグ時に動作を追いづらいなどの要素が含まれているでしょう．
さて，ぼくはこの問題を解くのは 3 度目ですが，この問題はとても良い問題だと思います．そして，決して簡単な問題ではないとも思います．しかし，「強実装である」という点に関してだけはそうではないと思います．
この問題の良い点，そして同時に難しい点というのは「解法の詰め方」と「適切な実装方法の選択」であります．この問題の解法自体がそこまで難しいかといえば，少なくともJOI春合宿で出題された問題の中ではそうでもないでしょう．では実装が難しいのかといえば，それも難しいとは限らない(少なくとも今回載せた実装はそこまで難しいわけではない)のがポイントです．
「他の人のソースコードを見ても、このような1や2といった数字が多数混在しています。」とあることからも分かるように，多くの人は(そしてぼくも初めて解いたときには)複雑怪奇，とても人間のデバッグするようなものではないソースを書いてしまうようです．これはこの問題が決して簡単ではないことを示しているでしょう．
今回載せた実装を最初から書くことができれば，この問題は難しいものではありません．しかし，その実装方法を選択すること，あるいはその実装方法へ至るまで正しく解法を詰められるかということ，これはとても難しいと思います．事実，ぼくも 2 度目に解いたときに比べ，さらによい実装方法を選択することができました．
パッとでてきた解法ですぐに勝負すると大変になってしまうことこそ多いが，じっくり解法を詰め，できるだけシンプルで書きやすくてバグを埋め込みにくくて動作を追いやすい，という実装方法へ至ることでスッと解けてしまう．そんな問題がぼくはとても好きであり，その点を見事に体現しているこの Dragon という問題は解くたびに新たな発見のある，非常に楽しくて良い問題なのだと，またひとつ確信させて頂きました．
天下一プログラマーコンテスト 2012 本戦
9月15日に KLab オフィスで行われた天下一プログラマーコンテスト 2012に参加しました。
まとめ
3位でした。やったー。
詳細
A
A問題なのでやるだけに違いない。そこそこの早さでAC。
B
B問題なので簡単に違いない、と思っていたらむずかった。
点の座標が不自然に小さいので自然に直線を全列挙した。直線に沿って累積和をとっていくとヨサゲだった。
ちょっと時間使ったが特にハマることなくAC。
C
B問題が結構頭使ったのでC問題は難しいに違いない、と思っていたら簡単だった。
単なるBFSで、連続する B の個数は 100 まで考えればいいという考察はいるけれどもわりと自明だった。
多少バグらせたりはしたが特にハマらずAC。
D
C問題が簡単だったのでD問題これもう(どんな問題が出るか)わかんねえな、と思っていたらほんとに見たことない問題が出た。おもしろかった。
どうみてもマラソン勢の wata さんとか瞬殺しそうだなあという感じで、逆にマラソンガチ苦手勢のぼくとかはどうしようもなさそうな感じだった。
しかし E が満点は激ムズそうで、部分点も頑張って実装したらボーナス点あげますぐらいの感じだったのでせっかくだから面白い問題を楽しんだほうがよいと思って E は無視して D に全力を尽くすことにした。
まず最初に N <= 18 の DP を書いて送ってみたりした。ここでバグらせて WA を積んだりしていて悲しかった。
DPで得られた厳密解を観察していると、(左下隅の点, 右下隅の点, 上真ん中の点) みたいな三角形がたくさん作られていたので、そういう三角形をたくさん作ることにした。四隅の点を O(N) で探してきて、 左下と右下を決め打ったときに三角形を最大にする3個目の点を普通に O(N) で求めるのを N/3 回繰り返すとちょうど O(N^2) でよさそうだったので書いた。
さすがにサンプル(格子状に並んでいるだけ)ではそこそこの解が得られるが、あんまり点がたくさんあるときにいい解が出せる自信がなかった(外側の点を無限に消費していくので最後のほうは小さい三角形ばっかりになりそう)。しかし送ってみたら通った。
E
読んで、実装を確実にやって確実に点を拾うならこっちで、100点を狙うなら D だなあと思った。
全体
- A よい
- B もっと早く解けてもよかった
- C そこそこ
- D 運
- E さて
各問題だけ見るともう少し改善できそうだが、全体で見るとわりと良かった。WAはそこそこ出してしまったがそもそも最後に点が更新されたときの時間がペナルティなのであまり影響はなく、ドハマリして時間を無駄に消費することもあまりなかった。順番もA->B->C->Dと順調に解いていくことができ、しかもDを通したのが終了4分前ぐらいだったので全体を通して充実感があってチョー楽しかった。
戦略的には D, E が残った際に E を忘れて D に全力を傾けようという決断がよかった。どんなコンテストでも問題間を右往左往して解けるものが解けなくなってしまうとかありがちなので、うまい選択が出来たのは強かった。もちろんこれで選択する方を間違えてしまうと悲惨だが、しかしぶっちゃけ選択を間違えるのと右往左往するのとか大して変わんない気がするし、どの問題を解くべきか判断する力はとても重要だと思うので積極的に選択していくほうがよさそう。
ソース
A
はい
#include<cstdio> typedef long long Int; int main() { Int X; scanf("%lld", &X); Int F[60]; F[0] = 0; F[1] = 1; for(int i=2; i<60; ++i) F[i] = F[i-1] + F[i-2]; int res = 0; while(X > 0) { int x = 0; while(F[x] <= X) x++; X -= F[x-1]; res++; } printf("%d\n", res); return 0; }
B
ちょっと実装頭わるい感じでよくない。実際のコンテスト中でも思いついたら即書き始めてアホなことするより、実装をある程度練ってから書いたほうが全体のコストは小さくできると思うので気をつけたい。
#include<cstdio> #include<set> using namespace std; typedef long long Int; int P[100][100]; const Int MO = 1000000007; int gcd(int m, int n) { return n ? gcd(n, m%n) : m; } int main() { int N; scanf("%d", &N); for(int i=0; i<N; ++i) { int x, y; scanf("%d%d", &x, &y); P[y][x]++; } Int sub = 0; for(int dx=1; dx<=99; ++dx) { for(int dy=-99; dy<=99; ++dy) { if(dy == 0) continue; if(gcd(dx, dy<0 ? -dy : dy) == 1) { Int C[100][100] = {}, R[100][100] = {}; for(int y=dy>0 ? 99 : 0; ; ) { if(dy > 0 && y < 0) break; if(dy < 0 && y >= 100) break; for(int x=0; x<100; ++x) { C[y][x] = P[y][x]; int ny = y+dy, nx = x+dx; if(0<=nx && nx<=99 && 0<=ny && ny<=99) { C[y][x] += C[ny][nx]; R[ny][nx] = 1; } } if(dy > 0) y--; if(dy < 0) y++; } for(int y=0; y<100; ++y) { for(int x=0; x<100; ++x) { if(!R[y][x] && C[y][x] >= 3) { sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)/6LL*(N-C[y][x]) % MO; if(sub >= MO) sub -= MO; sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)*(C[y][x]-3)/24 % MO; if(sub >= MO) sub -= MO; } } } } } } for(int y=0; y<100; ++y) { Int s = 0; for(int x=0; x<100; ++x) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } for(int x=0; x<100; ++x) { Int s = 0; for(int y=0; y<100; ++y) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } Int all = (Int)N*(N-1)*(N-2)*(N-3)/24 % MO; all -= sub; if(all < 0) all += MO; printf("%lld\n", all); return 0; }
C
WA はあったものの細かい条件のミスとかがなかったのは良かった
#include<cstdio> #include<algorithm> #include<queue> using namespace std; int N, A[32], B[32], C[32]; int dp[31][101][101][101]; struct st { int id, ehp, shp, cb; st(int a, int b, int c, int d) : id(a), ehp(b), shp(c), cb(d) { if(cb > 100) cb = 100; } }; const int INF = 1001001001; inline void checkmin(int& a, int b) { if(a>b) a=b; } inline void check(queue<st>& q, st x, int f) { if(dp[x.id][x.ehp][x.shp][x.cb] > f) { dp[x.id][x.ehp][x.shp][x.cb] = f; q.push(x); } } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d%d", &A[i], &B[i], &C[i]); A[N] = 0; for(int i=0; i<=N; ++i) for(int j=0; j<=100; ++j) for(int k=0; k<=100; ++k) for(int x=0; x<=100; ++x) dp[i][j][k][x] = INF; dp[0][A[0]][100][0] = 0; queue<st> q; q.push(st(0, A[0], 100, 0)); while(!q.empty()) { st s = q.front(); q.pop(); if(s.id == N) { printf("%d\n", dp[s.id][s.ehp][s.shp][s.cb]); return 0; } int damaged = s.shp - B[s.id]; if(damaged <= 0) continue; int f = dp[s.id][s.ehp][s.shp][s.cb] + 1; if(s.ehp <= 5) { check(q, st(s.id + 1, A[s.id + 1], damaged, 0), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - 5 + C[s.id]), damaged, 0), f); } check(q, st(s.id, min(A[s.id], s.ehp + C[s.id]), min(100, damaged+50), 0), f); int k = s.cb + 1; if(s.ehp <= k) { check(q, st(s.id + 1, A[s.id + 1], damaged, s.cb + 1), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - k + C[s.id]), damaged, s.cb + 1), f); } } puts("-1"); return 0; }
D
終了5分前ぐらいに超焦って書いてたのでひどい。
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; typedef long long Int; int x[3030], y[3030], oid[3030]; Int dp[1<<18]; int prev[1<<18], used[3030]; int N; int search_left(int a, int b, Int& M) { Int mx = -1; int mxc = -1; if(a == b) { M = -1; return -1; } for(int i=0; i<N; ++i) { if(a==i || b==i || used[i]) continue; Int x1 = x[a]-x[i], y1 = y[a]-y[i]; Int x2 = x[b]-x[i], y2 = y[b]-y[i]; Int A = x1*y2 - x2*y1; if(A < 0) A *= -1; if(mx < A) { mx = A; mxc = i; } } M = mx; return mxc; } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d", &x[i], &y[i]); if(N <= 18) { dp[0] = 0; Int area[18][18][18]; for(int i=0; i<N; ++i) { for(int j=i+1; j<N; ++j) { for(int k=j+1; k<N; ++k) { Int x1 = x[j]-x[i], x2 = x[k]-x[i]; Int y1 = y[j]-y[i], y2 = y[k]-y[i]; area[i][j][k] = x1*y2 - x2*y1; if(area[i][j][k] < 0) area[i][j][k] *= -1; } } } for(int i=1; i<(1<<N); ++i) { int pc = 0; for(int j=0; j<N; ++j) if(i & (1<<j)) pc++; if(pc % 3 == 0) { int ps[18], k = 0; dp[i] = -1; for(int j=0; j<N; ++j) if(i & (1<<j)) ps[k++] = j; for(int p=0; p<k; ++p) { for(int q=p+1; q<k; ++q) { for(int r=q+1; r<k; ++r) { int sel = (1<<ps[p])|(1<<ps[q])|(1<<ps[r]); Int A = area[ps[p]][ps[q]][ps[r]] + dp[i ^ sel]; if(dp[i] < A) { dp[i] = A; prev[i] = sel; } } } } } } for(int i=(1<<N)-1, t=0; t<N/3; t++, i^=prev[i]) { for(int j=0, k=0; j<N; ++j) if(prev[i] & (1<<j)) printf("%d%c", j, ++k == 3 ? '\n' : ' '); } } else { for(int i=0; i<N/3; ++i) { int tl, tr, bl, br; for(int j=0; j<N; ++j) { if(!used[j]) { tl = tr = bl = br = j; break; } } for(int j=0; j<N; ++j) { if(!used[j]) { if(y[tl] - x[tl] < y[j] - x[j]) tl = j; if(y[tr] + x[tr] < y[j] + x[j]) tr = j; if(-y[bl] - x[bl] < -y[j] - x[j]) bl = j; if(-y[br] + x[br] < -y[j] + x[j]) br = j; } } Int M[4] = {0}; int C[4]; C[0] = search_left(tl, tr, M[0]); C[1] = search_left(tr, br, M[1]); C[2] = search_left(br, bl, M[2]); C[3] = search_left(bl, tl, M[3]); Int mx = -1; int mxc = -1; for(int j=0; j<4; ++j) { if(mx < M[j]) { mx = M[j]; mxc = j; } } if(mx >= 0) { if(mxc == 0) printf("%d %d %d\n", tl, tr, C[0]), used[tl] = used[tr] = used[C[0]] = 1; if(mxc == 1) printf("%d %d %d\n", br, tr, C[1]), used[br] = used[tr] = used[C[1]] = 1; if(mxc == 2) printf("%d %d %d\n", br, bl, C[2]), used[br] = used[bl] = used[C[2]] = 1; if(mxc == 3) printf("%d %d %d\n", tl, bl, C[3]), used[tl] = used[bl] = used[C[3]] = 1; } else { int found = 0; for(int j=0; j<N; ++j) { if(!used[j]) { printf("%d%c", j, found==2 ? '\n' : ' '); found++; used[j] = 1; } } } } } return 0; }
JOI 2011-2012 予選第二問も解いた
Shakespeare で。
第一問は 5 個の整数が入力だったので微妙だと思って、N 個の入力が必要になるような問題を解いた。問題は こんなやつ。
第一問に比べて詰めて書いたはずなのに長さが3倍ぐらいになってしまった。
solve joi 2011-2012 yo-t2.
Achilles, the number of teams.
Banquo, counts the number.
Claudio, first team.
Dionyza, second team.
Emilia, score of first team.
Fenton, score of second team.
Gertrude, stores points.
Hecate, stores points reversed.
Isabella, the number of matches.
John of Gaunt, points the first team will earn.
John of Lancaster, points the second team will earn.
Lady Macbeth, modified point.
Malcolm, counts the number.
Octavia, with the last result.
Pantino, remembers the point.
Shallow, have the rank.
The Abbot of Westminster, copy.
Romeo, talks with others.
Juliet, a Romeo's lover.
Desdemona, feeds lines to others.
Helen, returns with a carriage.
Act I: First Process.
Scene I: The Introductions.
[Enter Romeo and Desdemona]
Romeo:
Thou art as fine as the sum of a pretty flower and a lovely
smooth rich plum.
[Exit Desdemona]
[Enter Helen]
Romeo:
Thou art as fine as the sum of Desdemona and the sum of a red
rose and a flower.
[Exit Helen]
[Enter Achilles]
Romeo:
Listen to your heart.
[Exit Achilles]
[Enter Isabella]
Romeo:
Thou art as gentle as the quotient between the product of
Achilles and the difference between Achilles and a father and
a amazing brother.
[Exit Isabella]
[Enter Banquo]
Romeo:
Thou art as embroidered as Achilles.
Scene II: The Initializations.
[Exeunt]
[Enter Juliet and Gertrude]
Gertrude:
Thou art nothing!
Juliet:
Remember me.
[Exit Gertrude]
[Enter Banquo]
Juliet:
Thou art as honest as the difference between thyself and a
moon. Are thou worse than a lamp?
Banquo:
If not, let us return to scene II.
Scene III: The Termination of Act I.
[Exeunt]
[Enter Romeo and Banquo]
Romeo:
Thou art as mighty as Isabella.
Act II: Process Matches.
Scene I: Input a Match and Process.
[Exeunt]
[Enter Romeo and Malcolm]
Romeo:
Thou art as reddest as Achilles.
[Exit Malcolm]
[Enter Claudio]
Romeo:
Listen to your heart.
[Exit Claudio]
[Enter Emilia]
Romeo:
Listen to your heart.
[Exit Emilia]
[Enter Dionyza]
Romeo:
Listen to your heart.
[Exit Dionyza]
[Enter Fenton]
Romeo:
Listen to your heart.
[Exit Romeo]
[Enter Dionyza]
Dionyza:
Am I better than you?
Fenton:
If so, let us proceed to scene II.
Am I better than you?
Dionyza:
If so, let us proceed to scene III.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as noble as a sky!
John of Lancaster:
Thou art as peaceful as the town!
We must proceed to scene IV.
Scene II: Dionyza beats Fenton.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as good as zero.
John of Lancaster:
Thou art as honest as the sum of a mistletoe and a proud town.
We must proceed to scene IV.
Scene III: Fenton beats Dionyza.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as trustworthy as the sum of a warm summer's day and
a stone wall.
John of Lancaster:
Thou art nothing.
Scene IV: Update Points.
[Exeunt]
[Enter Gertrude and Lady Macbeth]
Lady Macbeth:
Recall your imminent death!
Gertrude:
Thou art as disgusting as me.
[Exit Gertrude]
[Enter Malcolm]
Lady Macbeth:
Are you as pretty as Claudio?
Malcolm:
If so, let us proceed to scene V.
Lady Macbeth:
Are you as smooth as Emilia?
Malcolm:
If so, let us proceed to scene VI.
We must proceed to scene VII.
Scene V: Claudio Get Points.
[Exeunt]
[Enter Lady Macbeth and John of Gaunt]
John of Gaunt:
Thou art as healthy as the sum of thyself and me. We must
proceed to scene VII.
Scene VI: Emilia Get Points.
[Exeunt]
[Enter Lady Macbeth and John of Lancaster]
John of Lancaster:
Thou art as lovely as the sum of thyself and me.
Scene VII: Hecate Get Modified Points.
[Exeunt]
[Enter Lady Macbeth and Hecate]
Lady Macbeth:
Remember me.
[Exit Lady Macbeth]
[Enter Malcolm]
Hecate:
Thou art as cursed as the difference between thyself and a
thing. Are thou worse than a wind?
Malcolm:
If not, let us return to scene IV.
Hecate:
Thou art as noble as Achilles.
Scene VIII: Reverse Hecate.
[Exeunt]
[Enter Hecate and Lady Macbeth]
Lady Macbeth:
Recall what you said.
Hecate:
Thou art as mighty as me!
[Exit Hecate]
[Enter Gertrude]
Lady Macbeth:
Remember me.
[Exit Lady Macbeth]
[Enter Malcolm]
Gertrude:
Thou art as handsome as the difference between thyself and an
uncle. Are thou worse than a son?
Malcolm:
If not, let us return to scene VIII.
[Exit Gertrude]
[Enter Banquo]
Malcolm:
Thou art as foul as the difference between thyself and a
niece. Are thou worse than a sister?
Banquo:
If not, let us return to scene I.
Act III: Calculate Ranks.
Scene I: Prepares.
[Exeunt]
[Enter Romeo and Banquo]
Romeo:
Thou art as loving as Achilles.
Scene II: Push Points to Hecate.
[Exeunt]
[Enter Gertrude and Hecate]
Hecate:
Recall the point!
Gertrude:
Remember me.
[Exit Hecate]
[Enter Banquo]
Gertrude:
Thou art as mighty as the difference between thyself and a
nose. Are thou worse than a nephew?
Banquo:
If not, let us return to scene II.
Gertrude:
Thou art as loving as Achilles.
Scene III: Copy The Points.
[Exeunt]
[Enter Gertrude and Hecate]
Gertrude:
Recall what I said!
Hecate:
Remember me.
[Exit Gertrude]
[Enter The Abbot of Westminster]
Hecate:
Remember me.
[Exit Hecate]
[Enter Banquo]
The Abbot of Westminster:
Thou art as amazing as the difference between thyself and a
mother. Are thou worse than a niece?
Banquo:
If not, let us return to scene III.
The Abbot of Westminster:
Thou art as blossoming as Achilles.
Scene IV: Actual Computation.
[Exeunt]
[Enter Gertrude and Shallow]
Gertrude:
Thou art as rich as a squirrel.
Shallow:
Recall the point you have.
[Exit Shallow]
[Enter Pantino]
Gertrude:
Thou art as proud as me.
[Exit Pantino]
[Enter Malcolm]
Gertrude:
Thou art as reddest as Achilles.
Scene V: Calculation.
[Exeunt]
[Enter Shallow and The Abbot of Westminster]
Shallow:
Recall the point I will fight.
The Abbot of Westminster:
Am I better than Pantino?
Shallow:
If not, let us proceed to Scene VI.
The Abbot of Westminster:
Thou art as embroidered as the sum of thyself and a purse.
Scene VI: Next Team.
[Exeunt]
[Enter The Abbot of Westminster and Hecate]
The Abbot of Westminster:
Remember me.
[Exit Hecate]
[Enter Malcolm]
The Abbot of Westminster:
Thou art as clearest as the difference between thyself and a
lantern. Are thou worse than a horse?
Malcolm:
If not, let us return to scene V.
The Abbot of Westminster:
Thou art as bold as Achilles.
Scene VII: Restore.
[Exeunt]
[Enter Hecate and The Abbot of Westminster]
The Abbot of Westminster:
Recall what I gave you.
Hecate:
Remember me.
[Exit The Abbot of Westminster]
[Enter Malcolm]
Hecate:
Thou art as cunning as the difference between thyself and a
hamster. Are thou worse than a moon?
Malcolm:
If not, let us return to scene VII.
Scene VIII: Store The Rank.
[Exeunt]
[Enter Shallow and Octavia]
Shallow:
Remember me.
[Exit Shallow]
[Enter Banquo]
Octavia:
Thou art as cute as the difference between thyself and a
morning. Are thou worse than a hair?
Banquo:
If not, let us return to scene IV.
Act IV: Output The Result.
Scene I: Prepare for Output.
[Exeunt]
[Enter Octavia and Banquo]
Octavia:
Thou art as fair as Achilles.
Scene II: Actual Output.
[Exeunt]
[Enter Octavia and Romeo]
Romeo:
Recall the rank! Open your heart!
[Exit Octavia]
[Enter Helen]
Romeo:
Speak your mind!
[Exit Helen]
[Enter Desdemona]
Romeo:
Speak your mind!
[Exit Desdemona]
[Enter Banquo]
Romeo:
Thou art as fine as the difference between thyself and a
fellow. Are thou worse than a door?
Banquo:
If not, let us return to scene II.
JOI 2011-2012 予選第一問を解いた
Shakespeare で。
solve JOI 2011-2012 yo-t1.
Paris, just counts the number.
Benvolio, reads first three lines.
Romeo, with the most inexpensive pasta.
Capulet, reads last two lines.
Juliet, with the most inexpensive juice.
Montague, stores total price of the set.
Desdemona, feeds lines to others.
Helen, returns with a carriage.
Act I: A menu is presented.
Scene I: The introductions.
[Enter Romeo and Desdemona]
Romeo:
Thou art as fine as the sum of a pretty flower and a lovely
smooth rich plum.
[Exit Desdemona]
[Enter Helen]
Romeo:
Thou art as fine as the sum of Desdemona and the sum of a red
rose and a flower.
[Exit Helen]
[Enter Juliet]
Juliet:
Thou art as fine as the cube of a lovely beautiful charming
rich summer's day.
Romeo:
Thou art as charming as the cube of a lovely pretty smooth
white flower.
[Exit Juliet]
[Enter Paris]
Romeo:
Thou art as good as the sum of a lovely rose and a flower.
Scene II: The three pastas.
[Exeunt]
[Enter Romeo and Benvolio]
Romeo:
Listen to your heart.
Benvolio:
Am I worse than you?
If so, you are as fine as I.
[Exit Benvolio]
[Enter Paris]
Romeo:
Thou art as good as the difference between thyself and a
brother. Are you worse than a cat?
Paris:
If not, let us return to scene II.
Scene III: Preparing for the juice.
[Exeunt]
[Enter Juliet and Paris]
Juliet:
Thou art as fine as a white flower.
Scene IV: The juice.
[Exeunt]
[Enter Juliet and Capulet]
Juliet:
Listen to your heart.
Capulet:
Am I worse than you?
If so, you are as charming as I.
[Exit Capulet]
[Enter Paris]
Juliet:
Thou art as fine as the difference between thyself and a
rose. Are you worse than a tree?
Paris:
If not, let us return to scene IV.
Act II: Order the set.
Scene I: Calculating the price.
[Exeunt]
[Enter Romeo and Paris]
Romeo:
Thou art as good as a little tiny furry white animal.
Thou art as fine as the sum of thyself and a delicious
flower. Thou art as fine as the sum of a lovely smooth
rich furry red plum and thyself.
[Exit Paris]
[Enter Montague]
Romeo:
Thou art as good as I.
[Exit Romeo]
[Enter Juliet]
Juliet:
Thou art as fine as the sum of I and thyself.
[Exeunt]
Scene II: Print the price.
[Enter Paris and Montague]
Paris:
Thou art as foul as the difference between thyself and I.
Open your heart!
[Exit Montague]
[Enter Helen]
Paris:
Speak your mind!
[Exit Helen]
[Enter Desdemona]
Paris:
Speak your mind!
[Exeunt]
