fuu32のブログ

精進記録

ABC104 All Green

竸プロ DP 全探索 AtCoder

過去最低のパフォーマンスを出したので記録に残しておきます。

(C問題から解く戦略をとったけど、普通にAからやるべきですね)

問題概要

C - All Green

1以上D以下のそれぞれの整数iに対して、100i点の問題がp_i問ある。100i点の問題をp_i問全て正解すると、c_i点が加点される。G点以上獲得する時に少なくとも何問解く必要があるか？

制約

1≤D≤10
1≤pi≤100
100≤ci≤1000000
100≤G
入力中のすべての値は整数。
c_i,Gはすべて 100の倍数。総合スコアを G点以上にすることは可能。

考えたこと

コンテスト中は、ナップサック問題のようなDPで解けるのではないかと考えていました。
dp[ i ][ j ] :=100i点の問題まで見た時に、j点にする最小の問題数
のような感じでdpテーブルを作りました。が時間内で解けず終焉を迎えました。

きちんと紙で遷移を確認してACをもらいました。

提出コード:Submission #2960796 - AtCoder Beginner Contest 104

想定解のやり方でも解きました。

提出コード:Submission #2960740 - AtCoder Beginner Contest 104

学んだとこ

想定解としてはD \leq 10なので全部解く問題を決め打ちして、それでもG点に達しない場合は点数の大きい問題から解いていく方法でACができる。各問題全部解くかとそうでないかの2通りずつなので全体では2^{10}=1024通り。ちゃんと計算量を見積もって考察をしていきたいね。

「ある量を決め打つと、残りの最適戦略はGreedyに決まる」を心に刻みました。

SoundHound Inc. Programming Contest 2018 -Masters Tournament- D問題 Saving Snuuk

竸プロ グラフ問題 最短経路問題 AtCoder

コンテスト中に解けなかったので記録.

問題概要

D - Saving Snuuk

{n}頂点{m}本の辺からなる無向グラフが与えられる。

頂点{s}から頂点{t}に移動するとき、1回だけ両替所の存在する頂点で円→スヌークへ全額両替する。

この時かかる金額(円+スヌーク)の最小値を求めたい。

初期状態として各頂点に両替所が存在するが,{i}年後には頂点{i}の両替所は閉鎖され以降使用不可。

考えたこと

とりあえず、頂点{s}から頂点{t}への最小コストを求めたいので、円とスヌークをそれぞれ重みとしたダイクストラをやるのかと思った...がそこから考えが進まず、コンテスト終了。

これって{n-1}年後を考えると両替できるのが頂点{n}だけで、これは「円でダイクストラをした時の頂点{s}から頂点{n}へのコストと、スヌークでダイクストラをした時の頂点{n}から頂点{t}へのコストの和」でも求まるんですよね。

で{n-2}年後は{n-1}年後か同様に「円でダイクストラをした時の頂点{s}から頂点{n-1}へのコストと、スヌークでダイクストラをした時の頂点{n-1}から頂点{t}へのコストの和」の最小値を取ればいいんですよ。

ということは{n-1}年後から{0}年後に向かって累積minを求めれば{i}年後について全て求まるんですね。

提出コード:

Submission #2811840 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

学んだこと

問題の言い換えは大切({i}年後に頂点{i}の両替所が廃止/設立)

比較する候補が少ない状態(使用可能な両替所の数)から多くなる方向に考えを巡らせることは典型らしいので身に付けたいね。

ACPC2017 参加記

竸プロ

9/18~20にかけて行われた会津大学競技プログラミング合宿2017に参加してきました。

 

＜合宿前日＞

前乗りしていたので、１８時ごろには会津若松に到着。

１，２回生の６人で夕飯を済ませ、ホテルに戻った後はまだ寝るには早い時間だったので１回生の３人で勉強会を行った。ここでvvataarneにセグ木を教わり、RMQとRSQの問題の解き方をなんとなく理解して就寝。

 

＜合宿１日目＞

初日の集合時間は１３時だったが、ホテルのチェックアウトの関係上午前中に会津大学に着いてしまう。ヅ大生が見当たらず、開かない自動ドアの前で少々待つことに（これは毎年の儀式の一種であるらしい）。

 

この後無事ヅ大生に発見され、コンテスト開始時間に近づくにつれ他の参加者も到着し始める。

 

この日は立命館セットであったが、今回自分は作問に参加していなかったのでコンテストに参加。そうめん(somennagasi)さんとkei(clavis1107)さんにチームを組んでもらいapcp_sdcというチーム名で出場。

 

自分がA問題、keiさんがB問題、そうめんさんがC問題をそれぞれ担当することに。

開始１０が経ちA問題をAC。ここで私のコンテスト１日目は実質終了となる。

Eを少し考えるがわからず。蟻本に解法が載っていることを教えてもらうも理解できず。

結果として、keiさんがBをそうめんさんがCを、お二人でDを通してチームとしては４完してコンテスト終了。Aを解いてから、座っているだけの存在になっていたが、RiPPro１回生は毎年通る道らしい。

 

懇親会は会津若松駅近くの中華料理屋で行われたが、コミュ力が低いので少ししか喋れなかった気がする。

 

＜合宿２日目＞

問題は会津大学セット

この日は、tuki_remon(tukiremon)先輩とimulan(__imulan__)さんにチームを組んでもらいACPC_fitのチーム名で出場。

この日も自分がA問題を担当し、B問題をtuki_remon先輩がC問題をimulanさんが担当することに。

Aを解いた後D問題を少し考えていたところで、imlanさんがCを通していたので一緒に考えてもらう。その後tuki_remon先輩がBをACし、D問題もimulanさんがコードを書いてAC。

EとFを通しているチームが多かった気がするが、いまいち解法が浮かばず後回しに。

I問題をtuki_remon先輩が考察しimulanさんが実装していた。

その時自分は他にどんな問題が残っているのかを見ていたところ、Lのタイトル

"RMQ 2"を目にし心の中でテンションが上がる(２日前にセグ木の存在を知っていたので)。テンションは上がったが、自分で実装できる自信もなく先輩方に「Lはセグ木で解けませんか？」と伝え隣から実装を眺めることに。

LをACした後、どうにか残っているEとFを解きたいと思い考察していた。が結局自分は力になれずにF、Eを順にimulanさんが通してコンテスト終了。

チームとしては８完。

５時間セットはあっという間の気がしたが、後半はこの日も座っているだけだった気がする。考察力がもっとあれば楽しめたのかなとも思う。

 

この日はこの合宿の協賛であるRCOさんのスポンサーセッションの時間が設けられており、RCOさん特にアドテク部について話を聞いた。

フレックスタイム制？を採用していたり、会社のお金で竸プロができたりといろいろすごかった。この日の昼飯（牛丼）も懇親会費もRCOさん持ちなので本当すごい。

 

＜合宿３日目＞

最終日は北大セット。

この日のチームは、初日にチームを組んでもらったkeiさんとuwi(uwitenpen)さんと組んでもらった。基本的に自分とkeiさんが問題を解くことに。

コンテストが始まり、自分がA問題をkeiさんがB問題を担当。

私がAを書いている時に、uwiさんがC以降の問題に目を通しており大体の(確かE以外の)

解法を考えついていたらしく、本当にすごいの一言。

AをACしCの方針を聞き実装するも、再度、再々度くらい助けてもらい無事AC。

keiさんもB,Dを順に通していた。B問題はModの取り方に注意が必要だったらしい。

G問題はuwiさんがいつのまにか通していた（私は問題すら読んでない）

Fの解法を丁寧に教えてもらうも、いまいち理解できずにいたがこの問題はkeiさんが実装して通していた。

チームとしては６完。

前日の５時間セットを経験していたため、３時間が本当に短く感じられた。

 

＜合宿終了４日後(9/24)＞

合宿から数日経ち、大雑把な内容になってしまった気がする。

参加記はなるべく早いうちに書いたほうがいいことを実感（書く気持ちと記憶がなくなっていくので。

記事が殺風景になってっしまうので、ヅ大の写真とかを撮っておけばよかった気もする

合宿を通して学外の競プロerと交流できたのは楽しかったし、強い人たちと問題を共有し一緒に考察する時間はとてもいい経験になった。

 

次回のRUPCは自分も作問に加わるので、原案ぐらいは考えつけるように頑張りたい。

また、それまでにはC,D問題を積極的に解けるように成長していたいと思う。

 

 

そういえば、会津に行ってから毎日これを飲んでいた気がする。

大学の生協にも置いてくれないかなぁと…

f:id:fuu32:20170924144031j:plain