いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Beginner Contest 062(ABC62)

AtCoder Beginner Contest 062 - AtCoder Beginner Contest 062 | AtCoder
出ました
恒例になりつつある感じで大学の友達と6人で図書館で一緒に出ました
結果は3完、時間がもっとあれば部分点くらいは狙えたかなぁという感じでした
周りに聞いた感じCは難しいらしいので嬉しいけどやっぱりなんだか悔しかった
WA4回も出してしまったのでもっといい順位狙えたなぁという感じ

A.Grouping
[1,3,5,7,8,10,12][4,6,9,11][2]の3グループがある
x,yが与えられるから同じグループか判定する
考えるより手を動かそうと思ってif文でごり押してAC
後で友達に配列をつかって[0,1,0,2,0,2,0,0,2,0,2,0]みたいな感じで放り込んでおけば短く済むよう
なるほどなぁ

B.Picture Frame
与えられた文字列を"#"で囲んで写真のフレームを作ろうみたいな
もう決め打ちみたいな感じで入力の両サイドに#出したらすぐできた

C.Chocolate Bar
長方形の長さH,Wが与えられる、しっかり整数の長方形に3分割したときに面積のmax-minが最小の時の値を出力
分割の種類はどんなのがあるかなって考えたら「目」のように分けるか「T」のように分けるかの2通りのみで、入力例でほぼ網羅されていた
なのでh,wどちらかが3で割れれば0を出力
割れなければTだと思って、実装を始めた
Tの時は最初の分割部分を全探索してやると、あとは2分割する箇所は真ん中で1つに求まるのでオーダーも間に合う
縦横でこれを行った
これで提出するとWAが2つ出た
あちこち探して出しても変わらず考察をし直した

考えたら「目」の時は3で割れた時しか弾いてないじゃないかと気づいた(偉い!)
という事で2通り追加して実装ミスってWAだしてw,hで小さいほうを入れればいいやと気がついてAC
WA出さずに通せたなぁと思いつつも時間もないし通せただけ嬉しいので次へ

D.3N Numbers
数字が3N個で構成される数列が与えられる
この数列からN個数字を削除したのち、(前のN個の合計)-(後ろのN個の合計)が最大になるような数字を出力
見た瞬間頭を抱えた、周りはCがわからんなぁとぶつぶつ言っていたけど焦りを感じた
何をやっていいか全くわからない、とりあえず例を書いたり図を書いてみたりした
何がわからないのかといえば真ん中付近の数字は、数字の削除具合によって前にも後ろにもなりうるという事だ
とりあえず9の場合について整理した
書いた図は「〇〇〇△△△□□□」こんな感じ
両サイドのN個は含まれる部分は決まっているが真ん中のN個はどっちに含まれてもおかしくない
つまり仕切る部分を△の区間で全探索すればいいんだと思った
時間が足りず実装が間に合わなかったので書けてる分でとりあえず投げたらまあそりゃWA
後半はTLEだったので実装を工夫する必要があるなぁって思って終了

後で聞いたらほぼ正解だったっぽい、データ構造についてもっと知識を深めればACまでたどり着けたかもねとのこと

緑コーダーになりました
f:id:ratetion:20170521015249p:plain
AtCoder
これからも頑張っていきます
更新が最近少ないのはC問題埋めに苦戦してるからです
AOJで典型を解く練習をしてはどうかと言われたのでしばらく1日1回C解いてあとはAOJにしようかなと