予鈴

競プロとか備忘録とか…

AOJ -0235 Sergent Rian

問題文:Sergeant Rian | Aizu Online Judge すべての橋を爆破する最短コストは、最もコストが掛かる島(葉ではなく、1から到達するまでに最もコストがかかる島)を爆破する順番を最後にすれば良い。 サンプルを最短コストになるように鉛筆でなぞると、最もコス…

D-Simple Knapsack

コンテストに参加しなかったのですが、想定解ではない方法で解いたので記事にします。 ABCのD問題、重さを圧縮したらdpで解けるんじゃねと思ってやってるんですが無限にWAを生成してます。なぜ— yebi (@sigsigma19) 2017年5月2日解法は,重さの制約が特殊なの…

Kansai Camp 参加記

3月26~3月29日にかけて、KMC(京都大学マイコンクラブ)とNAIST、RiPProで行った合同合宿の参加記です。 全部書いてると長くなるので、コンテストの内容とかはおいおい書くつもりです。 1日目 2日目 3日目 最終日 まとめ 1日目 集合場所も知らず、準備も全くせ…

典型ナップサックを1次元配列で解く。

B - 書き換え(Rewrite) の問題を解く。 二次元DPで解くと、 時間の時に個書類を選んだ(or使わなかった)ときの最大値で という漸化式になる。時間のときの最大の価値 となるdp配列を考えます。 ①dp配列を逆順(mから0)に更新していくと、重複して更新するこ…

RUPC 2017 参加記

0日目 基本的に事務的な準備をしてました。 問題文や解法の議論に全く参加できなかったので、来年はそういう積極的に参加したい。 さて、明日のコンテストは立命勢の日ですが今年はなんと阪大勢とのコラボです!!☺️そしていつもよりコンテストが1時間長いで…

ABC C - Factors of Factorial

N!の約数の個数を数える問題。 の数字を片っ端から素数で割っていく。 は添字に素数を持ち、N!の素因数の数を持つ。 の値を初めて更新するとき()は、が含まれるからにしてる。 #include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<cmath> #in</cmath></vector></queue></stack></algorithm></cstdio></string></iostream>…

ABC C-Brute-force Attack

制約がだったのでnext_permutationだと思ったけど違った。再起できれいに書けてAC。辞書順ってところに時間を取られすぎてしまった… #include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<cmath> #include<utility> #include<set> #include<complex> #include<map> #define</map></complex></set></utility></cmath></vector></queue></stack></algorithm></cstdio></string></iostream>…

ARCのB :回文分割

個人的にすごく苦しんだ。(同期はプログラミング始めて二ヶ月でACしてる) 偶奇に分けて、奇数なら2で割った値をに足す。 を2で割ると"偶数のペア"の数がわかるから、奇数にいくつ肉付けできるかがわかる。 (イメージは、奇数は(1+偶数)になっているから、'…

ブログ始めました。

2017年になったので、ブログをはじめました。 競プロとか英語とかの備忘録になる予定です。