DDCC 2017 予選
作成日：2017.10.08
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点が$100-200-300-600$だから、早解き勝負である。
とはいっても100位以内に入ればいいからそんなに慌てる必要もない。
1時間以内に解ければ十分であろう。
コンテスト中
開始直前までパソコンの調子が悪かったのでスタートが1分ほど遅れる。
ローカルテストがなかなかできなかったので、A問題とB問題のコードを両方書き終えてからテストをした。
ほぼ同時に提出。[A 05:09 WA][B 06:19 AC]
A問題のWAはYes/NoをYES/NO(大文字)で出力していたためであった。
Codeforces同様に大文字・小文字問わずにACにしてほしい。[A 07:10 AC]
C問題は300点であることから難しく考えすぎないように気を付けて解いた。[C 11:44 AC]
C問題を解いた時点で200位近い順位だったので若干焦った。
なので、はじめD問題の解法の偶奇分けで迷走しかけた。
しかし、なんとかまとめて解き切った。[D 48:38 AC]
コンテスト後(結果)
全完48:38の50位。100位の人が67:04なので当初の見通しは正しかった。
コンテスト後に気付いたのだが、D問題は「$H,W$は偶数」という制約を見落としていた。
これが原因で時間を食ったが、仮にこの制約がない問題が出されたとしても迷走せずに解けるようになりたい。
各問題の(軽い)解説
A : DDCC型文字列
cin >> S;
cout << (S[0] == S[1] && S[1] != S[2] && S[2] == S[3] ? "Yes" : "No") << endl;B : 鉛筆
cin >> A >> B >> C >> D;
cout << A * 1728 + B * 144 + C * 12 + D << endl;C : 収納
問題文
2本の棒を入れるケースの数を$n$とすると、棒で短いものから$n$本は2本入っているケースにあると考えて良い。
よって棒を長いものからケースに入れていく時に、残っている棒の中で最も短いものも入れることができれば入れるということを繰り返していけば良い。
D : 石
問題文
対称でない間は幸福度は増えないので、極力対称になるように石を取り除くと良さそうである。
先に南北方向に対称にするか東西方向に対称にするかを決める。
そして決めた優先順位で各方向が対称になるように無駄なく石を取り除いていく。
両方向に対称になったら幸福度がより増える方向を優先して石を取り除いていく。
この時、$(x,y)$,$(H+1-x,y)$,$(x,W+1-y)$,$(H+1-x,W+1-y)$の4マスを1つのグループとすると、対称性はグループ毎に確かめれば良いことに注意する。
具体的には以下のとおりである。
グループでその中に石が4個あるものが$q$個、3個あるものを$t$個、2個あるもので南北方向、東西方向に並んでいるものがそれぞれ$a,b$個あるとする。
また$d$を初期状態にした時に得られる幸福度とする。
この時、解は$max(A*(a+t),B*(b+t))$$+max(A,B)*q$$+(A+B)*(q+1)-d$である。
＜(古い記事)
関連
＜(古い記事) CODE FESTIVAL 2017 qual A
CODE FESTIVAL 2017 qual B (新しい記事)＞