NEC プログラミングコンテスト2022 (AtCoder Beginner Contest 267)に参加しました。

結果

A,B,C,Dの4問正解でした。

A,B問題は聞かれていることは簡単だけど実装が面倒な問題だった印象。

Cはいつもよりちょっと難しかった？ちゃんと考えたら最初に思ってたよりは簡単だったけど。

D問題はいつも通りDPの問題だった。DPは慣れてきたから頭で漸化式立てて実装してたけどちょっと失敗だった。何回かWAしたから手計算して、落ち着いて漸化式を整理したらすぐに解けた。

CとD問題でちょっと時間を使いすぎてWAを出しすぎた。

A - Saturday

問題文の通り実装する問題。

何曜日かを英語で入力されるから土曜日まで何日かを出力する問題。 switch文で処理するのが一番スッキリすると思う。C++のswitch文どうだっけと数瞬迷ったので、調べる手間を惜しんでif文のコピペで実装した。

曜日の英語は問題文からコピペしてきたけど、1箇所半角スペースもついてきたのに気づかなかったせいで１WA。ちょっともったいない。

文字列の内容比較とか条件分岐とかができるかを聞いている問題なのかなと思う。

B - Split?

ボウリングのピンがスプリットになっているかどうかを答える問題。

聞かれていることは割りと単純だけど実装が面倒くさかった。
どのピンが同じ列かは問題文で示されているから、列ごとに全部のピンが倒れているかどうかを確認して、
ピンが残っている　－　ピンが全部倒れている　が1列以上連続している　－　ピンが残っている
という状態になっているかどうかを確認して答えた。列の数も7列だけなので3重ループで確認した。

ちゃんと考察したらもう少し簡単で賢い実装方法があるのかなあと思いながら解いた。

C - Index × A(Continuous ver.)

いつものC問題よりは難しい気がした。（いつもなら問題文読むとすぐに解き方が思いつくけど今回はちょっと悩んだから）

数列Aから連続した項を連続部分数列Bとして取り出して $i \times B _ {i}$ を計算して最大値を答える問題（Bの項数は指定されている）。ぱっと問題を読むと連続部分列の開始位置 $A _ {i}$ が動くと全部計算し直さないとなあと思いつつ、そんな事すると計算量が $O(N ^ {2})$ になってTLEになると予想できるのでどうやって解こうかなと考えた。

$A _ {i}$ を開始位置として数列Bを作ったとすると数列Bの和は $1 \times A _ {i} + 2 \times A _ {i+1}+・・・+M \times A _ {i+M-1}$ になる。これをもとに $A _ {i+1}$ を開始意図したときの数列B和を計算することは可能で、 $A _ {i}$ から $A _ {i+M-1}$ までの和を引きつつ $M \times A _ {i+M}$ を足せば求められる。

例えばM=3の時 $A _ {i}$ を開始位置とした時の和は
$A _ {i} ＋ A _ {i+1}＋ A _ {i+1}＋ A _ {i+2}＋ A _ {i+2}＋ A _ {i+2}$
となるが、開始位置が1ずれて $A _ {i+1}$ を開始位置とした時の和は
$A _ {i+1} ＋A _ {i+2}＋ A _ {i+2}＋ A _ {i+3}＋ A _ {i+3}＋ A _ {i+3}$ となる。この2つの和の差は $A _ {i}、A _ {i+1}、A _ {i+2}$ が1つずつ減っていて、 $A _ {i+3}$ が3個増えている。

一般化すると、 $A _ {i}$ を開始位置とした時の数列Bの和が求まっているときに、 $A _ {i+1}$ を開始位置とした数列Bの和を求めるには $A _ {i}$ から $A _ {i+M-1}$ の和を減らして、M $\times A _ {i+M}$ を足せば求められることになる。

累積和と $A _ {1}$ を開始位置としたときの和を求めておけば、ループ1回で全通り分の和を計算できる。あとは計算しながら和の最大値を控えておいて、最後にその値を出力すればいい。

D - Index × A(Not Continuous ver.)

C問題と似ているけど数列Aの項が連続していなくても良いパターンの問題。

解き方がぱっとは思いつかないので少し考えた。

ある項を数列Bに加える・加えないの判断をすると見なせばbit全探索で全通り確認すれば手っ取り早いなあと思った。けど、項数が最大で2000なので $2^{2000}$ 回処理することになってTLEするのは計算するまでもないので、bit全探索は使えない。
最大値を求めたいのでソートして大きい順に採用すればと思ったけど数列Bは数列Aの部分数列なので順番は重要。ソートして順番をぐちゃぐちゃにするのはまずい

とかを数秒で考えたけど、これならできるというアルゴリズムではなかった。

少しメタいけどD問題はDPで解く問題なことは最近は多いのでDPが使えないかなあと思ったら解けそうな気がした。(よくよく考えたらbit全探索で $2^{N}$ 処理するのならDP[N][x]でも処理できるから、たしかにDPで解ける。)

漸化式もそれほど難しくなと思ったので頭で考えて実装してみたらWA...
何回かデバッグ実行してDPの途中経過を確認してたら思ってたのと違うなあとなり、結局紙に手計算して、漸化式を整理して、改めて実装し直してみると1回で直った。

その上DPの初期値を何も考えずに0にしていたせいで $A _ {i}$ が負の場合にDPがおかしくなってWAした... ちょっと詰めが甘かった...

丁寧に解くのは大切だなあと思った。

E - Erasing Vertices 2

時間がなかったから問題文を読んだだけ。

以下は問題文を読んで数分で考えたこと。後でちゃんと解いておきたい。

愚直に解こうとすると $O(N^{2})$ くらいでNは最大で $2 \times 10 ^ {5}$ なのでTLEしそうだなと思った。
N回操作を繰り返すから $O(N)$ は必須で、各回で平均 $N/2$ 個の頂点を処理することになるので $O(N^{2})$ になる計算。厳密には平均の隣接頂点数がさらに掛けられると思う。

隣接する頂点数を初めに数えておいて、操作を1回するたびに残っている全頂点分の隣接頂点数を $O(1)$ で更新できれば $O(N)$ で解けるとは思った。一括更新があるならセグメントツリーかなと思った。更新するものがある区間じゃないから使えない気もするけど。

よくよく見ると実行時間制限が4秒と長めだったのでちょっと重めの処理でも間に合いそう。(ループの各回で $O(N log N)$ くらいかなあ。 $O(N ^ {2} log N)$ とかも実は間に合うのかも。)

F - Exactly K Steps

これはコンテスト後に問題文を読んだだけ。

頂点と距離が指定されるから指定された頂点から指定された距離の頂点数をどれか1つ答えるというのをQ回行う問題。

Q回とも頂点が異なる可能性があるので距離の計算は全対地間分が必要そう。なのでN回ダイクストラ法を実行するとかワ－シャルフロイド法で全対地間分を事前に計算しておくのかなあと思いつつ、頂点数が最大 $2 \times 10 ^ {5}$ なのに対してワーシャルフロイド法は $O(N ^ {3})$ なのでTLEしそう。

N回ダイクストラ法を実行が思いついた中では有力だけど、経験則的にN回ダイクストラ法だと事前計算の場合はメモリが確保できなくてエラーになることが多いので多分REになる。頂点と距離を受け取るたびにダイクストラ法を実行するとTLEになりそう。

これも後でちゃんと解いて見ようと思う。(多分解けなくて解説見ることになると思うけど。)

れとろのメモ置場

とあるSEのメモ置場

NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

結果