AtCoder Beginner Contest 003

結果

 400/401 82:29(2) 35位相当

 

 開始時刻 2017/07/21 13:51:00 提出履歴

A: AtCoder社の給料 - AtCoder Beginner Contest 003 | AtCoder

 3:02(AC)

 平均値の計算問題。普通に解く。少し遅かった。

B: AtCoderトランプ - AtCoder Beginner Contest 003 | AtCoder

 11:37(AC)

 先頭から比較していき、S[i]==T[i]だったり'@'を置換して上手くいくならOK。こっちもまあ遅い。

C: AtCoderプログラミング講座 - AtCoder Beginner Contest 003 | AtCoder

 32:38(WA)68:06(WA)72:29(AC)

 初めはDPか?と思ったけど、どう考えても100!を管理しきれるはずがなく、少し唸る。

 とりあえず強い人(Rの高い人)の動画を見ていくのがいいんだろうとは思ったけれど、その順番に悩む。最終的に直近で見た動画の影響力が一番強くて、遠くなるたびに半分になることに気づく。上位K個の値を小さい順に足しては割り…を繰り返せば良さそう。

 しかし実装でサボってR/(1<<k)的な書き方をしてしまう。当然オーバーフローしておかしくなったのでWA。気づくのにも時間がかかったし良くなかった。

D: AtCoder社の冬 - AtCoder Beginner Contest 003 | AtCoder

 60:09(WA, 100/101)

 とりあえずX*Yの区間がいくつ設定できるかを数える。これは(R-X+1)*(C-Y+1)なので楽勝。

 X*Yの中は(Dの選び方)*(Lの選び方)で良さそうなのでコンビネーション。簡単にパスカルの三角形を使って実装。最大でもn=900なのでメモ化再帰で適当に。ここまでで一度提出して部分点100点。

 問題はこの後。D+L<X*Yの時はフチにデスクやラックがない可能性がある。少し考えて、ベン図の足し引きでどうにかできそうだとは思いつく。ただ、4状態のベン図の足し引きがわからず、紙に書いてても時間だけがすぎて行ってしまった。

 結局二時間の間には解けなかったけど、終わって五分くらい後に閃いてテスト。なんかD+L=X*Yのテストケースが1つだけおかしくなったので、即席で条件分岐してAC(よくない解き方)。

 そういえばベン図の足し引きは包除原理っていうらしいですね。

感想

 オーバーフローはパッと見わからないので嫌い。でも書いた自分が悪いので気をつけます。

 Dは時間内には完答できなかったけれど、包除原理は偶奇で分ければいける、っていう知見は結構いい知見でした。次からは感覚で書けるようになりたい