tatyam’s blog

(ﾉ) - ω - (ヾ)ﾓﾁﾓﾁ

プログラミング初心者から2年で橙になるまで

2019/11/23

ついに橙になりました！！！

というわけでここまでの経緯を書いていきたいと思います

競プロに出会う前

プログラミングについて

プログラミン とか Scratch とかを少しだけ触れた

機械・ゲームについて

パソコンに初めて触れたのが3歳 (えぇ…)

5歳あたりから数年間ブラウザゲームばっかりやってたはず

形態は変われどゲームばっかりやってる (競プロはゲーム)

数学について

授業の2年先くらいまではある程度知っている感じ (数学ガールをもっと早くやっていたらなあ…)

数I は NHK高校講座 を見せられてた

数II は 数学ガールの秘密ノート からカケラを集めて 足りないところを高校受験前の数検で対策本を一読して公式だけ入れた

数オリ系はジュニア算数オリンピックで本選にいったくらい　それ以降はほとんどやっていないので決して数オリ系の人ではない (難しくてやめちゃった)

高校について

県立高校の中で一二を争う高校。情報の先生のおかげで競プロをやる人は他より多い。

今年本選erが出るか微妙なところ。

高1

5月

先生に誘われて県のプロジェクトに参加する いろんな分野があって科学オリンピックとか研究発表とかを目指すらしい

サンプルプログラムを見てJOI予選-A が解ける

6月

JOIを練習する

JOI予選-A~B は解ける C は苦労する

7月~

JOI予選-D (主にDP) をやってみる

なんでそんな遷移思いつくの？？？ というおきもち

11月

コンテスト初参加(ABC067) 2完 50:02 Perf. 375

初参加遅くない？

12月

JOI予選 328点(あと6点) 部分点を取りましょう…

1月

Twitterを始める

2月

ABC088 4完 95:57 perf.1098

初の全完 このあたりから本格的にAtCoderをやってる (twitterは偉大)

3月

twitterと競プロ中心の生活をしていたら部活なんてやってられないことに気づいた

高2

5月

部活をやめる 家に帰ったら競プロの生活

6月

ARC099

f:id:tatyam_prime:20191124030825p:plain

とても印象深い回

E - Independence をなんとか通し、悪名高い D - Snuke Numbers のおかげで橙パフォが出た回

この時点で700を解く考察力があって、 知識と実装力が足りてない感じ

10月

PCK予選 30位

地域にライバルがいないので地域枠で通る

AGCのプロになる

f:id:tatyam_prime:20191124033830p:plain

AGCは知識と実装力よりも考察力が重要なためパフォが出やすかった

11月

PCK本選 ☀️ 6完 ☀️

12月

JOI予選 506点

これが成長なんだよね

1月

全国統一プログラミング王決定戦予選

f:id:tatyam_prime:20191124032812p:plain

800まで通して初の赤パフォ、AtCoder黄色になる

2月

JOI 本選 312点

何度か誤読したが EDPC のおかげで通る

3月

JOI春合宿 3完401点 で 9位

部分点ちゃんと取っていれば 6位くらい取れませんでしたか？

高3

5月

GCJTシャツを得る

7月

FHCTシャツを得る

10月

PCK予選 6位

11月

PCK本選 ☀️ 6完 ☀️

DDCC2020予選

f:id:tatyam_prime:20191124035534p:plain

ARC級初の全完 橙になる

まとめ

Twitterと競技プログラミングに浸かっていれば自然に強くなっていく(？)

これから

  • 大学に受かる

  • 大学に入ったら精進を進める 当面は 2600 を目標に

  • でも AtCoder でこれ以上伸びるには AGC での成功が不可欠で、数オリ系の力がちょっと足りてなさそう
  • 作問もしたいね

ABC145 解説

27分遅刻の42分全完でした f:id:tatyam_prime:20191117003620p:plain

A - Circle

半径 r の円の面積は、半径 1 の円の面積の何倍ですか？

円の面積は \pi r^2 であることを思い出すと r^2 倍である。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int r;
    cin >> r;
    cout << r * r << endl;
}

B - Echo

文字列 S は、ある文字列を2回繰り返したものですか？

n が2で割れないなら No、2で割れるなら文字列比較をする。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n >> s;
    if(n & 1){
        puts("No");
        return 0;
    }
    n /= 2;
    puts(s.substr(0, n) == s.substr(n, n) ? "Yes" : "No");
}

C - Average Length

ハミルトン路の長さの平均はいくつですか？

ハミルトン路の長さの合計をとって N! で割る。

8!*8=322560 なので、 O(N!N) が間に合う。
ある辺を使う回数は N!(N-1) / _NC_2 = 2(N-1)! 回なので O(N^2) でも解ける。

O(N!N) 解

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

double dist(pii a, pii b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main(){
    int n;
    cin >> n;
    vector<pii> a(n);
    for(auto& i : a) cin >> i.first >> i.second;
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    double ans = 0;
    do{
        for(int i = 0; i < n - 1; i++) ans += dist(a[perm[i]], a[perm[i + 1]]);
    }while(next_permutation(perm.begin(), perm.end())); // 順列全探索はこれが便利
    for(int i = 1; i <= n; i++) ans /= i;
    cout << fixed << setprecision(20) << ans << endl; // 誤差に注意
}

O(N2) 解

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

double dist(pii a, pii b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main(){
    int n;
    cin >> n;
    vector<pii> a(n);
    for(auto& i : a) cin >> i.first >> i.second;
    double ans = 0;
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) ans += dist(a[i], a[j]);
    ans *= 2;
    ans /= n;
    cout << fixed << setprecision(20) << ans << endl;
}

D - Knight

(0,0) にある駒を (i+1,j+2) または (i+2,j+1) に動かして (X,Y) に移動させる時の通り数はいくつですか？

どちらの操作も x+y 方向に 3 動いているから、 (X + Y) % 3 != 0 なら 0
操作回数を N とすると、 N=(X+Y)/3
どちらの操作も x, y 方向ともに 1 以上動いているから、次のように読み換える。

(0,0) にある駒を (i,j+1) または (i+1,j) に動かして (X - N,Y - N) に移動させる時の通り数はいくつですか？ これは有名問題で、 (i+1,j) に動くのが X - N 回、 (i,j+1) に動くのが Y - N 回の並び替えになるから、 _{X+Y-2N}C_{X-N} 通り。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll modpow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1){
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return ans;
}

int main(){
    ll x, y;
    cin >> x >> y;
    if((x + y) % 3 || x > y * 2 || y > x * 2){
        puts("0");
        return 0;
    }
    ll n = (x + y) / 3;
    x -= n;
    y -= n;
    vector<ll> fac(x + y + 1), inv(x + y + 1); // fac[i] = i! mod 1000000007, inv[i] = 1 / i! mod 1000000007
    fac[0] = 1;
    for(ll i = 1; i <= x + y; i++) fac[i] = fac[i - 1] * i % MOD;
    inv.back() = modpow(fac.back(), MOD - 2);
    for(ll i = x + y; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    cout << fac[x + y] * inv[x] % MOD * inv[y] % MOD << endl;
}

E - All-you-can-eat

見た感じナップサック問題なのでDPを疑う。
最後時間ギリギリに注文できるのが厄介。 でも O(N^2) くらいじゃないと間に合わない。
→ 最後に注文する料理をDPの状態に持てばいい。
あとはナップサック問題と同じ

DPの持ち方

dp[i][j][0]= 料理 i まで見たときに j 分までに食べ終わるときの美味しさの合計の最大値 dp[i][j][1]= 料理 i まで見たときに j 分までに食べ終わり、その後料理を1つ注文するときの美味しさの合計の最大値
このままだとメモリをかなり喰うが、遷移の順番を気をつければ、dp[T][2] に圧縮することができる。

DPの遷移

dp[i+1][j][0]=max(dp[i][j][0], dp[i][j - A][0]+B)
dp[i+1][j][1]=max(dp[i][j][1], dp[i][j - A][1]+B, dp[i][j][0] + B)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }

int main(){
    ll n, t;
    cin >> n >> t;
    ll dp[n + 1][t][2];
    memset(dp, 0x00, sizeof(dp));
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        for(ll j = 0; j < t; j++){
            dp[i + 1][j][0] = dp[i][j][0];
            dp[i + 1][j][1] = max(dp[i][j][1], dp[i][j][0] + b);
            if(j >= a) chmax(dp[i + 1][j][0], dp[i][j - a][0] + b);
            if(j >= a) chmax(dp[i + 1][j][1], dp[i][j - a][1] + b);
        }
    }
    cout << max(dp[n][t - 1][0], dp[n][t - 1][1]) << endl;
}

圧縮版

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }

int main(){
    ll n, t;
    cin >> n >> t;
    vector<vector<ll>> dp(t, vector<ll>(2));
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        for(ll i = t; i --> a; ) chmax(dp[i][1], dp[i - a][1] + b);
        for(ll i = 0; i < t; i++) chmax(dp[i][1], dp[i][0] + b);
        for(ll i = t; i --> a; ) chmax(dp[i][0], dp[i - a][0] + b);
    }
    cout << max(dp[t - 1][0], dp[t - 1][1]) << endl;
}

F - Laminate

N 項の数列 H のうち K 項以下を変えた時の \sum_{i=0}^{N-1}{max(0, H[i] - H[i-1])} の最小値を求めよ。(H[-1]=0)

谷を埋めたり、山を削ったりすると小さくなる。
K 項以下がやっかいだけど、部分問題に落とせそうなのでDPを疑う。

DPの持ち方

dp[i][j][k]= 数列を i まで見たときに j 項を変えて、最後の項が k のときの最小値

DPの遷移

dp[i][j][k]=\min_l(dp[i-1][j-1][l]+max(0, k - l))
{\rm chmin}(dp[i][j][H[i]], \min_l(dp[i-1][j][k]+max(0, H[i] - l)))

しかし、このままでは O(N^4) でTLEになってしまう。
O(N^4) かかっている上の遷移の無駄について考えると、ある項を変えるときは、前の項と同じにするのがよいとわかる。(どんな項が続いても山も谷もできないため)

dp[i][j][k]=dp[i-1][j-1][k]
{\rm chmin}(dp[i][j][H[i]], \min_k(dp[i-1][j][k]+max(0, H[i] - k)))

k の値が不連続であるため、unordered_map を使いたくなるが、 TLEする可能性が高いので座標圧縮する。

サンプルコードは疲れたのでこれで

JOI予選 1A 参加記

授業終了が12:30のためお昼を食べて電車内からスマホ参加

14:00にタイマースタート

A - 3 つの整数 (Three Integers)

1 か 2 が 3つ与えられます。どちらが多いでしょう？

実装時間を考えてmapを選択(中央値のほうがよかった)

signed main(){
    map<ll,ll>m;
  rep(3){
    LL(a);
    m[a]++;
    }
  if(m[1]>1)out(1);
  else out(2);
}

AtCoder直書きのためインデントがガバガバ

提出 1'03"

B - 母音を数える (Counting Vowels)

文字列が与えられます。母音はいくつでしょう？

条件を連ねるのは時間がかかるのでchar配列で実装(is_vowel() は存在しない)

signed main(){
    LL(n);
  STR(s);
  ll ans=0;
  auto t="aiueo";
  each(i,s)each(j,t)ans+=i==j;
    out(ans);
}

提出 2'07"

1問目はAC

C - マージ (Merge)

2つのソート済みの数列が与えられます。マージソートしてください。

よく読んでただのマージソートであることを確認
ソートすればいいので繋げてソート

signed main(){
    LL(a,b);
  VEC(ll,c,a);
  VEC(ll,d,b);
  each(i,d)c.push_back(i);
  sort(range(c));
  each(i,c)out(i);
}

提出 3'53"

2問目はCE

Bに戻る

エラーメッセージを読むと t の型が const char * でループが回せないらしい

signed main(){
    LL(n);
  STR(s);
  ll ans=0;
  char t[]="aiueo";
  each(i,s)each(j,t)ans+=i==j;
    out(ans);
}

提出 4'23"

ここでタイマーストップ

2,3問目はAC

感想

さて、完走した感想ですが、2問目のCEが痛い

これは再走ですね…

GCJ 2019 Round 1A - Golf Gophers

codingcompetitions.withgoogle.com

問題文

去年、たくさんの厄介なホリネズミたちが私たちの果樹園に住んでいました。

私たちは果樹園をやめてミニチュアゴルフコースを開業しました。

しかし、ホリネズミたちもついて来てしまったようです！

そこで、何匹のホリネズミがいるか調査する必要がありますが、ホリネズミは普段隠れていて夜行性なので、直接数えることができません。

ただ、全部で 1 匹以上 M 匹以下であることは分かっています。

私たちのミニチュアゴルフコースは、18ホール全てに小さな扇風機があることで有名です。

i 番目の扇風機には 2 ≤ B_i ≤ 18 枚の羽根があり、それらは時計回りに 0 番から B_i - 1 番まで番号が付けられています。

毎晩、寝る前に扇風機の電源を切り、それぞれの扇風機の羽根 0 が下を向くようにします。

これは扇風機が次の日にちゃんと充電されているようにするために重要です。

しかし、次の日には扇風機の羽根の位置が変わっていることに気がつきました。

ミニチュアゴルフコースは風のない地域にあるので、いたずら好きのホリネズミの仕業に違いありません！

全てのホリネズミは毎晩1回だけやってきて、扇風機を1つランダムに選んで羽根を反時計回りに1つ分回転させます。

例えば、羽根が3枚の扇風機の場合、最初のホリネズミが羽根を回すと羽根 1 が下を向き、次のホリネズミが羽根を回すと羽根 2 が下を向き、さらにホリネズミが羽根を回すと羽根 0 が下を向きます。

私たちはホリネズミの数を調べる計画を立てました。

ゴルフコースの難易度を変えるために、扇風機の羽根の数は簡単に変えられるようになっています。そこで、これを利用するのです！

毎晩、寝る前にそれぞれの扇風機の羽根の枚数を 2 〜 18 枚で選んで変えます。

全ての羽根の枚数を同じにしたり、毎晩同じ枚数にする必要はありません。

そして、朝にそれぞれの扇風機の羽根の向きを確認します。

私たちはホリネズミの数 G を調査するために N 晩使うことができます。

G を特定してください。

入出力

この問題はインタラクティブ問題です。出力の後にフラッシュする必要があります。

まず、テストケースの数 T、使える日数 N、ホリネズミの最大数 M が与えられます。その後、 T 回テストケースを繰り返します。

各テストケースでは N + 1 回までジャッジとやり取りをすることができます。

そのうちの N 回は以下の通りです。

あなたのプログラムは 2 以上 18 以下の18個の整数を1行に出力します。これらの i 番目は、その夜に i 番目の扇風機に取り付ける羽根の数を表します。

ジャッジは18個の整数を1行で返します。これらの i 番目は、ホリネズミがいたずらをした後、i 番目の扇風機の下を向いている羽根の番号を表しています。

無効なデータ（範囲外の数字、不正な行など）を送信した場合は、代わりに -1 が返されます。

どのホリネズミがどの扇風機を回すかはランダムで一様であり、他のホリネズミの行動によって変わることもありません。

このように 0 回以上 N 回以下やり取りをした後、あなたのプログラムはホリネズミの数 G を出力します。

ジャッジは1つの整数を返します。あなたの答えが正しい場合は 1、正しくない場合（または不正な形式の行を出力した場合）は -1 です。

ジャッジが -1 を返した場合、それ以降ジャッジは入出力を行いません。あなたのプログラムは終了しなければ Time Limit Exceeded になります。

制約

1 ≤ T ≤ 20

実行制限時間 : 20秒

メモリ制限 : 1GB

小課題

小課題1 (11点)

N = 365

M = 100

小課題2 (21点)

N = 7

M = 106

考察

羽根の枚数をバラバラにするとあまり情報が得られなさそう

羽根の枚数を同じにすると羽根の枚数で割ったあまりがわかる

→ 中国剰余定理

qiita.com

互いに素になるように上から選ぶと、

17 * 16 * 13 * 11 * 9 * 7 = 2.450448 * 106

だから N = 6 で十分

ACコード :

Code Jam - Google’s Coding Competitions

GCJ 2019 Round 1A - Pylons

codingcompetitions.withgoogle.com

問題文

私たちの宇宙戦艦のAlgorithmica船は、Pylonsと呼ばれるしつこいロボットによって宇宙の中を追跡されています！

私たちはPylonsを撒くために新しい銀河にテレポートしました。

できるだけ長くこの銀河にいて、次の計画を立てる時間を稼ぎたいです… しかしPylonsに捕まりたくはありません！

この銀河は、縦R行、横C列のマスからなります。i 行目 j 列目 のマスを，マス(i, j) と表します。私たちは好きなマスから始めて、銀河の全てのマスをちょうど1回ずつ訪れるようにワープし続けなければなりません。

つまり、最初のマスを含めて1度来たマスにはもう1度行くことはできません。

Pylonsに私たちが次にどこへ行くかを予測されたくないので、次に移動するマスは今のマスと行や列、対角線が同じマスを選ぶことができません。

つまり、今のマスを (r, c)、次に移動するマスを (r’, c’) として

r = r’

c = c’

r - r’ = c - c’

r + r’ = c + c’

のいずれも成り立ってはいけません。

そのような条件を満たす R × C マスの訪問順はあるでしょうか？

それともPylonsから逃げることは不可能なのでしょうか？

入力

1行目にはテストケースの数 T が与えられ、それ以降の行に T 個のテストケースが与えられます。

各テストケースは 1 行からなり、行の数 R と列の数 C が与えられます。

出力

各テストケースについて、Case #x: y と改行を出力してください。

ここで、x は1から始まるテストケースの番号、 y は問題文の条件を満たすことが可能なら POSSIBLE 、不可能なら IMPOSSIBLE です。

その後、可能であればさらに R × C 行出力してください。

それらの行の i 行目は r_i と c_i からなり、i 回目に訪れるマスが (r_i, c_i) であることを表します。

制約

実行制限時間 : 20秒

メモリ制限 : 1GB

小課題

小課題1 (8点)

T = 16

2 ≤ R ≤ 5

2 ≤ C ≤ 5

小課題2 (23点)

1 ≤ T ≤ 100

2 ≤ R ≤ 20

2 ≤ C ≤ 20

解説

実験してみよう

2 × 2 、2 × 3 、2 × 4 、3 × 2 、3 × 3 、4 × 2 はできない

4 × 4 は複雑

パターン化するには…？

2列・3列を埋めるパターンがあれば良さそう

実装

回転して横長にする

4 × 4 だけ場合分け

2列のとき、3つ進んで2つ戻る(必要な横幅は5)

3列のとき、ぐるぐるする(必要な横幅は4)

残りが奇数列のとき3列、偶数列のとき2列を選べばよい(横長なので大丈夫)

ACコード :

Code Jam - Google’s Coding Competitions

GCJ 2019 Round 1A - Alien Rhyme

codingcompetitions.withgoogle.com

問題文

ある地球外探査で、あなたは宇宙人の詩の形跡を見つけました！

言語学者のチームは、その宇宙人の言語の各単語は1つの位置（文字）にアクセントがあると判断しました。

ある単語の、アクセントがある文字とそれ以降の部分をaccent-suffixと呼びます。

2つの単語のaccent-suffixが等しい場合、それらの単語は韻を踏むと言います。

例えば、PROLとTARPOLの場合、2つの単語のアクセントがOにある場合とLにある場合は韻を踏んでいますが、それ以外では韻を踏んでいません。

あなたは宇宙人の詩の一部であるかもしれないN個の単語のリストを得ました。

残念ながら、あなたはそれぞれの単語のアクセントの位置がわかりません。

あなたはこれらの単語のうち0個以上を捨て、残りの単語にアクセントを割り当て、それらの単語全てをペアにした時に、「ペアどうしは韻を踏んでいるが他の単語とは韻を踏んでいない」ようにできると思っています。

このようにペアを作ることができる最大の単語数を求めてください。

入力

1行目にはテストケースの数 T が与えられ、それ以降の行に T 個のテストケースが与えられます。

各テストケースは N + 1 行からなります。

最初の1行に単語の数 N が与えられます。

残りのN行に単語 W_i が与えられます。

W_i は英大文字からなり、単語は各テストケースの中で互いに異なります。

同じ単語が異なるテストケースでは異なるアクセントを持つ可能性があることに注意してください。

出力

各テストケースについて、x を1から始まるテストケースの番号、 y をテストケースの答えとして、

Case #x: y と改行を出力してください。

制約

1 ≤ T ≤ 100

実行制限時間 : 20秒

メモリ制限 : 1GB

1 ≤ |W_i| ≤ 50

W_i は英大文字からなる

i ≠ j ならば W_i ≠ W_j

小課題

小課題1 (10点)

2 ≤ N ≤ 6

小課題2 (27点)

2 ≤ N ≤ 1000

考察

文字列の後ろ i 文字を高速に比較したい

→ suffix tree : 文字列に何が足されたかで木にする

　ローリングハッシュ : 文字列を P 進数と見て大きな数で割った余りを比較する

1度使ったaccent-suffixはもう1度使えない

アクセントを後ろにずらせば使えるようになる

→ できるだけaccent-suffixは長い方がいい

後ろ i 文字が一致するペアを長い方から貪欲に取ればいい

ACコード :

Code Jam - Google’s Coding Competitions

JOI本選/みんプロ参加記

2/9~2/10のJOI本選に参加しました。

前日

  • ゆきこをする(事故をおこす)
  • ついったーをする
  • 名刺をつくる
  • 1:30にねる

いちにちめ

  • 荷造りをする
  • 秋葉原で数名と合流
  • EDPCをする
  • Q'tでオムライスをたべる
  • 国際会議場につく
  • くちもちをもちもち

ぷらくてぃす

  • 5問目のネタバレをうける
  • 30分で全完する
  • りんご3つでジャグリングをする
  • 人々とお話をする
  • 素数大富豪をする

よるごはん

  • 人々とお話をする
  • 自己紹介をする

みんプロ

  • 鍵をもらうと1分前
  • 部屋に入るまえにロビーで開始
  • Aを30秒で提出(2度ペーストする)
  • AのコードをBに提出
  • ABをAC
  • Cはめんどそう
  • 1度条件を整理してAC
  • 耳に石を入れる…？？
  • 条件を整理すると0偶奇偶0とすればよい
  • EDPCをやっていたのでDPでいけることに気づく
  • DをAC(この時点でパフォ2600)
  • Eを悩む
  • パフォが2450まで落ちてくる
  • 気づいたらFめっちゃ解かれてる
  • 作りたいボールの列がある時、そのボールの前がコンベアになることで作ることができそう
  • 前からi個目までのボールで作れる列をDP(またDPが活躍)
  • E解けないから素数大富豪をする
  • ABCDF5完、パフォ2496

よる

  • シャワーをする
  • おーじにあいさつする
  • 0:30に寝る

ふつかめ

  • 起床AC(眠れてよかったです)
  • 朝食を食べる

本選競技

  • Aは累積和の掛け算
  • Bは価値が低いのを入れると左側が入れづらくなることに気づけば価値が大きい方から右に入れるだけ(ここまで24分)
  • Cを誤読して実装する("交換する"に気づいていない)
  • Cを誤読して実装する("隣り合う"に気づいていない)
  • Cがよくわからないのでstringのeraseを使ってDPする(75点)(ここまで2時間)
  • Dはとりあえず圧縮
  • 上から順に各マスに配置してみる(嘘解法)
  • 嘘だったのでとりあえずDP(37点)
  • CとEを悩む
  • 残り10分でEの4点を取りにいく
  • 提出5秒間に合わず(結局訂正して検証時間中に4点)

問題解説

  • Cの交差する個数は前と後の累積和から出せるのに気づきたかった
  • Eは直径をとってなんやかんや天才をする
  • Dは縦の個数を先に2個に揃えるといい(直感的に近いところまではいくけどそこからが難しい)
  • 難易度は5-7-8-10(11?)-12といった体感(上の方の難易度がよくわかっていない)
  • ボーダー予想 : 100-100-20-37-0 で 257 点

おつかれさまでした

100 - 100 - 75 - 37 - 0 の 312 点でした。春合宿もがんばりたいと思います。