2019/12/18

Codeforces 1266 A

60の倍数⇔3の倍数かつ20の倍数として判定

プログラムを書く前にサンプルを使って手元で検証するべき

少しでも気づいた条件があれば抜けないようにメモしておく

 

Codeforces 1266 C 

盤面(行列)構築

各行に適当にgcdを割り振ってみる

→100マス計算のように、割り振った値の積を入れていけばいい

行数、列数が1の時がコーナーケース

正当性を証明するときに、隣接数が互いに素であることを使っていることから気づけた

 

Codeforces 1266 D 

グラフ構築(最小値条件)

可能な操作をよく考えると、各人に対して損得を変えないように責任関係を変えることができるとわかる

→借りのある人と貸しのある人の間に辺を結べばよい

 

構築条件が最小最大の場合、下界(上界)の達成を目指して構築していくと見えやすい?

 

操作の意味を掴むのが本質だった readforces

 

EDPC Y - Grid 2

数え上げ

障害物の位置を昇順sortして見る順番を決める、これによりスタート地点と、今調べる障害物を端点とする長方形内部の点は、全て決定した状態とすることができる→漸次決定可能

 

Codeforces 999 D

最小操作回数

具体例を書いて実験すると、m回以上足さない限り操作回数は一定と分かる

→適当に合わせる

余りの計算で引き算をして負になっていた(1敗)

 

Codeforces 999 E

数え上げ

首都から到達できない閉路の数と、首都以外の入次数が0の頂点を数え上げればよい

数え上げ方の間違いに気づかず、爆発...

(グラフはある程度ちゃんとしたサンプルを作らないと方針ミスをしやすくなる)