出力を入力へ

プログラミングに関する基本的な事を中心にまとめます

参加記録 Codeforces Educational Round 41

久しぶりのCodeforces & 初のEducational. よく知らないままにとりあえず参加.

ABC解いて1619th, Rank 1402でRatings 1408 -> 1419 (+11). 久しぶりの海外コンテストかつEducationalの形式を知らない中で参加した割にはまあ満足. ただし,コンテスト終わり際になってDの方針が決まるものの, 提出できないで終わったのが悔しい.

A: Tetris

最初はまったく問題文が理解できずに時間が経つ. 問題文のテトリスという単語からやっと意図を理解して解いた.

問題を理解してからはすぐに解けた.

B: Lecture Sleep

どこで起こすとスコアが最大になるか,しゃくとり法で探索するだけ. 比較的すぐに解くことができた. (しゃくとり法というアルゴリズム名自体は忘れていた).

C: Chessboard

分割された各パネルの左上を黒or白にするコストを計算し, その組合せが最小となるように選べばいい.

解いている最中から気になってはいたけど, 黒にするコストと白にするコストの両方を計算する必要はなかった. このせいで無駄に複雑にしてしまった.

また,コストの総和が最小となる組合せの選び方を どうすればいいかわからず謎実装してしまった.

D: Pair Of Lines

最初は方針が立たなかった. よく考えれば3点が直線に並んでいれば直線は確定なのだから 最初の5点から1つの直線を決めて,直線にのらない点はもう1つの直線候補として保存, 以降はどちらの直線にものらなくなった時点で不可とすればいいだけだと気付く.

方針を決定した時点で残り時間があまりなく,実装しきれなかったのが悔しいところ. 実装方針もよくなかったし,実装にオーバーフローによる不具合もあったのでダメダメだった.

E: Tufurama

一目シンプルで簡単に解けそうだと思ったけど方針がたたなかった.

Wavelet Matrixというアルゴリズムを利用する問題らしい(参考). 要復習.