ICPC2021 国内予選 参加記
ICPC2021@tatyam_prime @noshi91 @goodbaton の tonosama で出場します!
— tatyam (@tatyam_prime) 2021年11月5日
よろしくお願いします!
殴り書き
A : tatyam 100 までだからシミュレーションすればいいね〜 (2分くらい)
B : baton しばらくかかって AC
C : noshi めちゃくちゃ手こずってた C と D 交換した方がよかったかも
D : tatyam 置いた位置 mod 3 が 0, 1, 2 のやつを 1 個ずつ取るんだなあ (嘘)
3 つ均等に分けて総和の最小値の最大化
dp[1 つ目のグループの size][1 つ目のグループの総和][2 つ目のグループの size][2 つ目のグループの総和] = max 3 つ目のグループの総和 で 6 乗でやってみるか → WA
noshi : bool DP で良くない? たしかに 出力に diff がないけど心配なので出してみる → WA
放棄して F へ noshi が通した
E : baton めちゃくちゃがんばってた これ得意なやつだったかも
F : tatyam 完全マッチングを 1-1, 2-2, 3-3, … とすると、s -> t 辺を s -> t に張ったグラフで全ての辺がいずれかのサイクルに含まれていればいい
強連結成分分解して、sink と source を 1 つずつペアにするといけそう
実装する → うまくペアを組まないといけない場合がある どうすればいい?
(しばらく進捗なし)
次数が少ないやつから優先すればいい?
noshi : 逆向きに到達できない辺から張れば強連結成分が増えないのでうまくいく 確かに
途中までの実装があるのでがんばる (WA) ワーシャルフルイドが ijk になってる…… あれ diff がない これ 1 度辺を張った sink と source が残り続けてるな (AC)
なんとか戦犯じゃないレベルに OK
G : noshi が O((3/2)n poly) (よく覚えてない) にできたっぽい 時間は足りない
H : これはなんですか?
感想
3 並列だけあって全体的に高難易度でしたね〜 ただ解かれてないのが 2 問もあって、もうちょっと簡単でもよかったかもね〜
東工大からは 3 チーム めでたい
SPJ😿 (東大に行かなかった理由の 1 つはこれ)
前半の動きをもっと洗練する必要がありそう アジアで完差つけないといけない状況はあまりやりたくないですよね
のしのしをどう活用するか たぶん私たちが実装担当になった方がいいと思う
そういえば最近 Open Cup で問題文 (英語) の見た目から簡単な問題を選ぶことができることに気づきました
まだまだ知らない技術がいっぱいあるなあ (DM 分解, 反転)
精進をしたいところだがその時間があるかどうか……
AtCoder赤になりました。
AtCoder赤になりました。
この記事は 色変記事 Advent Calendar 2020 24 日目の記事です。
関連記事 : tatyam.hatenablog.com
11/4 色変記事AdC が作られる
色変記事AdventCalendarを作成しました。
— どきん (@ayoiyouyoeyo) November 4, 2020
みなさまの勇気ある宣言をお待ちしております!https://t.co/1NqMxq7Wu3
めちゃくちゃ面白いし、当時のレーティングが 2722 で赤になれる見込みが十分にあったので参加することにしました。
2905 * 5 で赤、了解!
— tatyam (@tatyam_prime) November 4, 2020
実際のところ、rngコンがクリスマス後だったため、平均 2935 パフォくらい出す必要がありました。
11/14 1 戦目 AGC049
Rank : 24
Perf : 3270
Rating : 2722 -> 2790 (+68, highest!)
A がめちゃくちゃ難しくてびっくりしましたが、 B も D もかなり素直な問題で、瞬殺することができた結果、銀パフォを出すことができました。🎉🎉
D は C の WA の後から考察を始めているので、 10 分で AC したわけではありません。
11/21 2 戦目 ARC108
Rank : 111
Perf : 2520
Rating : 2790 -> 2766 (-24)
F が直径取ってなんやかんやの問題なので、解けるべきだったのですが…
あと D で return を 1 つ忘れて 46 くらいパフォを落としています 😢
まあでも -24 なので耐えです。
11/28 3 戦目 ARC109
2020/11/28 AtCoder Regular Contest 109
— tatyam (@tatyam_prime) November 28, 2020
ooooo- 82:03 + 5:00
Rank: 7
Perf: 3200 (inner : 3410)
Rating: 2766 -> 2817 (+51, highest!)
AtCoder 赤になりました!!!!
\\\ウオオオ(っ `-´ c)オオオオオ///
\\\ウオオオ(っ `-´ c)オオオオオ///
\\\ウオオオ(っ `-´ c)オオオオオ/// pic.twitter.com/FCyNZqEJgb
A : 考察を省略して Dijkstra でゴリ押し
D : 考察を省略して圧縮グラフの BFS でゴリ押し
E : "色反転で最終結果が反転しないもののみ数えれば良い" に気づいたのがめちゃくちゃよかった
F がめちゃくちゃ難しかったおかげで Diff 2661 の早解きで 銀パフォが出ました。
いろいろな情報
ARC109 終了後のいろいろな情報を載せておきます。
レーティンググラフ
AtCoder Problems
Rating History
情報オリンピックに出会ったのが 2017 年の 6 - 7 月くらい AtCoder 初参加が 2017/10/28 そこから赤になるまで 3 年と少しの間に、上の表にのっていない他サイト、オンサイトなどを合わせて 3000 問以上を解きました。
赤コーダーになるために必要なもの
ってなんでしょうね。
- コンテストを楽しむ
- たくさん問題を解く 実装力を高める
- 難しい問題を解く 質は大事 レベルの高い問題を解けるようになる
- 直観的な数学とかアルゴリズムとかの理解
(こんなの?)
12/5 4 戦目 鹿島コン(ARC110)
はじめての unrated ARC めちゃくちゃ相性が良かった
最近の rated こどふぉも調子が良くてびっくりしてる 最近作問作業ばっかりで精進できてないのに
LGM タッチしたら AtCoder赤よりすごくないですか?
今後の目標
- AtCoder 2950
- Codeforces 3000
(橙のときにも言った気がするけど)そろそろ厳しくなる気がする
AtCoder Beginner Contest 162 F - Select Half
きれいな実装をします。
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 0x1fffffffffffffff; template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } int main(){ ll n; cin >> n; vector<ll> a(n); for(auto& i : a) cin >> i; const ll skip = 1 + n % 2; // 取る 取らない 取る 取らない ... を貪欲にやっていくと 1 + n % 2 個余って、 // 1 + n % 2 回飛ばせることがわかる vector<vector<ll>> dp(n + 2, vector<ll>(skip + 1, -INF)); // dp[i][j] := a[0, i) を j 要素無視して1つ飛びに取ったときの最大値 dp[0][0] = 0; for(ll i = 0; i <= n; i++) for(ll j = 0; j <= skip; j++){ if(j < skip) chmax(dp[i + 1][j + 1], dp[i][j]); if(i < n) chmax(dp[i + 2][j], dp[i][j] + a[i]); // 1個選んだら1個選ばないのもセット } cout << dp[n + 1][skip] << endl; // なので floor(n / 2) * 2 + skip == n + 1 に答えが入る }
Google Code Jam まとめ
Google Code Jam ってどんなコンテストなんでしょうか…? 調べてみました!
注 : 2020 年の情報です。
GCJ とは…?
Google 社主催の年1回の世界最大規模の競技プログラミングのコンテストです。 Round 3 まで進出するとTシャツがもらえます!
スケジュール
Code Jam - Google’s Coding Competitions
開始 (UTC+9) | 長さ | |
---|---|---|
Qualification Round 2020 | 4/4(土) 8:00 ~ | 27時間 |
Round 1A 2020 | 4/11(土) 10:00 ~ | 2.5時間 |
Round 1B 2020 | 4/20(月) 1:00 ~ | 2.5時間 |
Round 1C 2020 | 5/2(土) 18:00 ~ | 2.5時間 |
Round 2 2020 | 5/16(土) 23:00 ~ | 2.5時間 |
Round 3 2020 | 6/6(土) 23:00 ~ | 2.5時間 |
World Finals 2020 | 8/7(金) 19:30 ~ | 4時間 |
Qualification Round は 27時間、 Round 1 は 時間帯をずらして3回あるようです! ありがたいですね!
一方 Round 2 以降は 23:00 ~ と深夜帯でのコンテストとなります!
Qualification Round
4/4(土) 8:00 ~ 4/5(日) 11:00 (27 h)
Qualification Round には参加登録した人が全員出場できます!
参加登録には16歳以上であることが必要です。
参加登録 はもうしましたか?
Qualification Round で 30点以上を取ると、 Round 1 に進出します!
Qualification Round では、なんと相談自由 です! (Rules 7.1)
システムがわからない>< とか、英語がわからない>< とか、30点とれない>< とかいう場合は、誰かと相談してみてはいかがでしょうか?
Round 1
1A : 4/11(土) 10:00 ~ 12:30 (2.5 h)
1B : 4/20(月) 1:00 ~ 3:30 (2.5 h)
1C : 5/2(土) 18:00 ~ 20:30 (2.5 h)
Round 1 は Round 2 への進出が決まるまで出ることができて、
Round 1 のそれぞれで、まだ Round 2 への進出が決まっていない上位 1500 人が Round 2 に進出します。
つまり、Round 1A より Round 1B 、Round 1B より Round 1C のほうが Round 2 に進出しやすいということになります!
18:00 ~ と人権のある Round 1C が狙い目ですね!
Round 2
5/16(土) 23:00 ~ 1:30 (2.5 h)
Round 2 は Tシャツをかけた戦い です。
Round 2 の上位 1000 人が、 Round 3 に進出し、Tシャツをもらえます!
Round 3
6/6(土) 23:00 ~ 1:30 (2.5 h)
Round 3 は オンサイトをかけた戦い です。
Round 3 の上位 25 人が、 World Finals に進出します!
World Finals
8/7(金) 19:30 ~ 23:30 (4 h)
ライブ中継もあるようです!
今年も tourist が優勝するのでしょうか…?
コンテスト形式
Round 1 は 3問で100点、 World Finals は 5問で200点、それ以外は4問で100点の構成になっています。
各問題にはいくつかの小課題があり、1個以上のフィードバックのある小課題と、0個以上のフィードバックのない小課題からなります。
「小さい制約でフィードバックのある小課題を1つと、大きい制約でフィードバックのない小課題を1つ」のパターンが多く、
フィードバックのある方を Small、 ないほうを Large と呼ぶようです!
前の小課題が通らないと次の小課題はジャッジされません。
また、フィードバックのない小課題の結果はコンテスト終了後すぐに明らかになるようです!
順位は AtCoder形式 で決まり、誤答ペナルティは4分です。
コンテスト中の順位表はフィードバックのない方も全て通った場合の得点で表示されることに注意しましょう!
問題形式
基本的に1実行の中に複数テストケースがある形式で、実行制限時間は 20秒 が多いようです。
複数テストケースの場合は、このように Case #1:
が必要なことに注意しましょう!
void Case(int i){ printf("Case #%d: ", i); }
このようなテンプレートを用意しておくと良いかもしれませんね!
また、昨年は全ての Round でインタラクティブ問題が出題されていて、インタラクティブ問題が多い傾向にあるようです。
インタラクティブ問題の練習をしておくと良いかもしれませんね!
Educational Codeforces Round 22 E - Army Creation
バチャをしました
問題文
人の兵士がいて、 番目の兵士のタイプは です。
Vova はこのなかからできるだけ多くの兵士をを雇って軍隊を作りたいです。
ただし、同じタイプの兵士は 人までしか雇えません。
各クエリについて、 の兵士から軍隊を作るときの軍隊の人数を求めてください。
ただし、クエリ暗号化がされていて、オンラインで答える必要があります。
考察
だと種類数になって、 が変わっても同じように解けそう。
区間 種類数 競プロ [検索🔎]
hama-du-competitive.hatenablog.com
オンラインで答える方法が書いてある
同じ数をちょうど2つ含む区間 → 同じ数をちょうど 個含む区間 とすればよい
区間を (始点, 終点) の2次元平面上の点に落とし込んで、 [典型]
に含まれる区間の数 を領域木で求める。
コード
パフォを上げるためのテンプレートのおはなし
この記事は Competitive Programming (1) Advent Calendar 2019 13日目の記事です。*1
みなさん、テンプレート使ってますか?
テンプレートを使うとたくさんの良いことがあります
- プログラムを書くことに使う脳のリソースが減る
- コーディング量が減る
- バグりにくくなる
- FAが取りやすくなる
私は144行のテンプレートを使っています
えぇ…
まあ、こんなに多くする必要はありませんが(スニペットにもできますし)、おすすめテンプレートを紹介していきますね
★★★ - 常備したいテンプレート
#include <bits/stdc++.h> using namespace std;
い つ も の
C++の標準ライブラリを一行で一括でインクルードする - Qiita
using ll = long long;
基本的に int は使っていません
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
Dijkstra 法で長いのは書きたくないので
using pll = pair<ll, ll>;
グラフとか、2つ組の入力とかに重宝する
const ll LINF = 0x1fffffffffffffff;
INF を作ったあと作ったのでこの名前
Long_INFinity : 4倍 してもオーバーフローしない数 (4倍することがあったため)
稀に int 型の INF も使う
#define overload4(_1, _2, _3, _4, name, ...) name #define rep1(n) for(ll i = 0; i < (n); ++i) #define rep2(i, n) for(ll i = 0; i < (n); ++i) #define rep3(i, a, b) for(ll i = (a); i < (b); ++i) #define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
これ使ったらやめられないね
可変長引数マクロ __VA_ARGS__
が ...
を展開する overload4()
で5番目の名前を取り出せばそれぞれの引数の個数のマクロが出てくる
#define rrep(i, a, b) for(ll i = (b); i --> (a); )
Reverse_REPeat
これも可変長にしておくといい
# define each(i,...) for(auto&& i:__VA_ARGS__)
名前は for_each から
可変長引数にすることで間にカッコがあっても対応できる
#define all(i) begin(i), end(i)
sort(all(v)); reverse(all(v)); とかたくさん使う
これも可変長にしておくといい
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; } template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
たくさんのとこで使う 特に Dijkstra, BFS あたりで便利
template<class T> ll sum(const T& a){ return accumulate(all(a), 0LL); }
long long 型 で合計を求める
可変長all()を使う場合は #define する
template<class T> auto min(const T& a){ return *min_element(all(a)); } template<class T> auto max(const T& a){ return *max_element(all(a)); }
たくさん使う
int scan(){ return getchar(); } void scan(int& a){ scanf("%d", &a); } void scan(unsigned& a){ scanf("%u", &a); } void scan(long long& a){ scanf("%lld", &a); } void scan(unsigned long long& a){ scanf("%llu", &a); } void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); } void scan(float& a){ scanf("%f", &a); } void scan(double& a){ scanf("%lf", &a); } void scan(long double& a){ scanf("%Lf", &a); } void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){ cin >> a; } template<class T> void scan(vector<T>&); template<class T> void scan(deque<T>&); template<class T, size_t size> void scan(array<T, size>&); template<class T, class L> void scan(pair<T, L>&); template<class T, size_t size> void scan(T(&)[size]); template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); } template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); } template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); } template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); } template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); } template<class T> void scan(T& a){ cin >> a; } void in(){} template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); } void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(unsigned a){ printf("%u", a); } void print(long long a){ printf("%lld", a); } void print(unsigned long long a){ printf("%llu", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(float a){ printf("%.15f", a); } void print(double a){ printf("%.15f", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } template<class T> void print(const vector<T>&); template<class T, size_t size> void print(const array<T, size>&); template<class T, class L> void print(const pair<T, L>& p); template<class T, size_t size> void print(const T (&)[size]); template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } } template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); } template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } } template<class T> void print(const T& a){ cout << a; } int out(){ putchar('\n'); return 0; } template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; } template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
な が い
可変引数で、vectorとかを展開し、scanf/printf を使って入出力をやってくれる関数
これが一番便利だと思います(?)
return out(-1);
とかできるように out()
の返り値は 0
★★ - あると便利なテンプレート
using ld = long double; using ull = unsigned long long; using uint = unsigned int; using pii = pair<int, int>; using pdd = pair<double, double>; using tuplis = array<ll, 3>;
最近は double を使わず全部 ld にしてる
tuplis の名前は tuple<int, int, int> からきている
#define vec(type,name,...) vector<type> name(__VA_ARGS__) #define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
vector の省略宣言
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; in(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; in(__VA_ARGS__) #define STR(...) string __VA_ARGS__; in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__; in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__; in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; in(__VA_ARGS__) #define VEC(type,name,size) vector<type> name(size); in(name) #define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
宣言と入力を両方やってくれるマクロ
とっても便利
template<class T> ld dsum(const T& a){ return accumulate(all(a), 0.0L); }
long double 型で合計を求める関数
const int INF = 0x3fffffff; const ll MINF = 0x7fffffffffff; const ld DINF = numeric_limits<ld>::infinity(); const int MOD = 1000000007; const int MODD = 998244353; const ld EPS = 1e-9; const ld PI = 3.1415926535897932;
INF : int 型 の INF 2倍してもオーバーフローしない MINF : フローあたりで欲しくなった INF と LINF の中間 DINF : long double の INF (double は使わないので) MOD : いつもの MODD : いつもの EPS : だいたいこれくらいあれば大丈夫 PI : 幾何で使う
const ll four[] = {0, 1, 0, -1, 0}; const ll eight[] = {0, 1, 1, 0, -1, -1, 1, -1, 0};
グリッド上の探索に使う
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; } ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
桁DPとか、整数問題に使う
vector<pll> factor(ull x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; } vector<ll> divisor(ull x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
たまに使うやつ(速さ重視)
int first(bool i = true){ return out(i?"first":"second"); } int yes(bool i = true){ return out(i?"yes":"no"); } int Yes(bool i = true){ return out(i?"Yes":"No"); } int No(){ return out("No"); } int YES(bool i = true){ return out(i?"YES":"NO"); } int NO(){ return out("NO"); } int Yay(bool i = true){ return out(i?"Yay!":":("); } int possible(bool i = true){ return out(i?"possible":"impossible"); } int Possible(bool i = true){ return out(i?"Possible":"Impossible"); } int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); } void Case(ll i){ printf("Case #%lld: ", i); }
増え続けてるやつ
return Yes();
とか return No();
とかできるとうれしい
★ - スニペットにしたいテンプレート
sort(all(<#name#>));
sort はよく使うので 思考に追いつくために
return out(<#outputs#>); return Yes(<#result#>);
これもちょっと長い
rep(4){ ll x2 = x + four[i], y2 = y + four[i + 1]; if(x2 < 0 || h <= x2 || y2 < 0 || w <= y2) continue; }
グリッド上の探索に
ll ok = <#0#>, ng = <#100000000#>; while(abs(ok - ng) > 1){ ll cen = (ok + ng) / 2; if(<#ok#>) ok = cen; else ng = cen; }
二分探索
template<class T> struct PartialSum{ vector<T> data; PartialSum(const vector<T>& v): data(v.size() + 1){ for(ll i = 0; i < v.size(); i++) data[i + 1] = data[i] + v[i]; } T get(ll l, ll r) const { return data[r] - data[l]; } T operator[](ll at) const { return data[at]; } };
累積和
template<class T> struct PartialSum2D{ vector<vector<T>> data; PartialSum2D(const vector<vector<T>>& v): data(v.size() + 1, vector<T>(v[0].size() + 1)){ for(ll i = 0; i < v.size(); i++) for(ll j = 0; j < v[i].size(); j++) data[i + 1][j + 1] = data[i][j + 1] + v[i][j]; for(ll i = 0; i < v.size(); i++) for(ll j = 0; j < v[i].size(); j++) data[i + 1][j + 1] += data[i + 1][j]; } T get(ll x1, ll x2, ll y1, ll y2) const { return data[x2][y2] + data[x1][y1] - data[x1][y2] - data[x2][y1]; } vector<T>& operator[](ll at) const { return data[at]; } };
2次元累積和
特にこれは頭使うからstructにしておくといい
Modint
JOI2次予選2019 解説
77分で全完したので解説を書いていきます
A - ポスター (Poster)
- 回転の後塗り直すのと, 塗り直した後回転するのではコストは変わらない
- 最初に回転した後塗り直すものとして良い
- 回転するのは2回まででよい
- 各回転について塗り直す時間を求め, 最小を取る
- 計算量は
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, a, b) for(ll i = a; i < b; i++) template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } const ll INF = 0x1fffffffffffffff; void rotate(vector<vector<char>>& a){ // 回転 ll n = a.size(); vector<vector<char>> b = a; rep(i, 0, n) rep(j, 0, n) a[i][j] = b[j][n - 1 - i]; } ll cost(const vector<vector<char>>& a, const vector<vector<char>>& b){ // 塗り分けにかかる時間 ll n = a.size(), ans = 0; rep(i, 0, n) rep(j, 0, n) ans += a[i][j] != b[i][j]; return ans; } int main(){ ll n; cin >> n; vector<vector<char>> s(n, vector<char>(n)), t(n, vector<char>(n)); rep(i, 0, n) rep(j, 0, n) cin >> s[i][j]; rep(i, 0, n) rep(j, 0, n) cin >> t[i][j]; ll ans = INF; chmin(ans, cost(s, t)); rotate(s); chmin(ans, cost(s, t) + 1); rotate(s); chmin(ans, cost(s, t) + 2); rotate(s); chmin(ans, cost(s, t) + 1); cout << ans << endl; }
B - いちご (Strawberry)
- 少なくとも1番遠いいちごのところまで往復する時間はかかる
- 行き際に収穫しても帰り際に収穫しても答えは変わらないから, 帰り際に収穫するものとしていい
- 帰り際にまだ熟していなかったらその分待つ必要がある
- 計算量は
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, a, b) for(ll i = a; i < b; i++) template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } const ll INF = 0x1fffffffffffffff; int main(){ ll n; cin >> n; ll ans = 0; rep(i, 0, n){ ll a, t; cin >> a >> t; chmax(ans, a + a); // 往復分 chmax(ans, a + t); // まだ熟してなかったら待つ } cout << ans << endl; }
C - 桁和 (Digit Sum)
- "操作をすると になる整数を探す" のは難しいが, "操作したあとの整数を求める" のは簡単
- が操作して になるか と が操作して になるか は同じ
- に操作を続けて にできるか
- 計算量は
#include <bits/stdc++.h> using namespace std; using ll = long long; ll digit_sum(ll a){ ll ans = 0; while(a){ ans += a % 10; a /= 10; } return ans; } int main(){ ll n; cin >> n; vector<bool> dp(1000100); dp[n] = 1; for(ll i = n; --i; ) dp[i] = dp[i + digit_sum(i)]; cout << accumulate(dp.begin(), dp.end(), 0) << endl; }
D - テンキー (Tenkey)
- 表示されている数を で割った余りを にしたいんだから, で割った余りでまとめてDP(?)ができる
- カーソルが で、表示されている数を で割った余りが にするための最小操作回数
Dijkstra法を使って計算BFSで十分- 計算量は (定数倍10倍くらい)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, a, b) for(ll i = a; i < b; i++) template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } const ll INF = 0x1fffffffffffffff; int main(){ ll m, r; cin >> m >> r; const vector<vector<ll>> g = {{1}, {0, 2, 4}, {1, 3, 5}, {2, 6}, {1, 5, 7}, {2, 4, 6, 8}, {3, 5, 9}, {4, 8}, {5, 7, 9}, {6, 8}}; // 隣のキー vector<vector<ll>> cost(10, vector<ll>(m, INF)); queue<pair<ll, ll>> q; cost[0][0] = 0; q.push({0, 0}); while(q.size()){ ll at, r; tie(at, r) = q.front(); q.pop(); ll next = (r * 10 + at) % m; if(chmin(cost[at][next], cost[at][r] + 1)) q.push({at, next}); // キーを押す for(auto& i : g[at]) if(chmin(cost[i][r], cost[at][r] + 1)) q.push({i, r}); // 隣に移動 } ll ans = INF; rep(i, 0, 10) chmin(ans, cost[i][r]); cout << ans << endl; }
E - じゃんけん式 (Rock-Scissors-Paper Expression)
- まさか構みやつ構文解析が出るとは思わなかったなー
- 構造分析はパターンがあるので1度解いておくと良さげ
- 私のパターン : (部分文字列の範囲) → 計算結果 の関数を作る
- 対応するカッコを調べておくとオーダーが落ちる
- R → {1, 0, 0} , S → {0, 1, 0} , P → {0, 0, 1} , ? → {1, 1, 1} と変換して各演算子を実装する
- 勝ち負け, 演算子の定義, 計算順序に気をつけて計算していくと解ける ただの実装問
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, a, b) for(ll i = a; i < b; i++) template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } const ll INF = 0x1fffffffffffffff; const ll MOD = 1000000007; struct janken{ ll R, S, P; janken(ll R, ll S, ll P): R(R % MOD), S(S % MOD), P(P % MOD){} janken operator+(janken x){ ll r = R * x.R + R * x.S + S * x.R; ll s = S * x.S + S * x.P + P * x.S; ll p = P * x.P + P * x.R + R * x.P; return {r, s, p}; }; janken operator-(janken x){ ll r = R * x.R + R * x.P + P * x.R; ll s = S * x.S + S * x.R + R * x.S; ll p = P * x.P + P * x.S + S * x.P; return {r, s, p}; }; janken operator*(janken x){ ll r = R * x.R + S * x.P + P * x.S; ll s = S * x.S + P * x.R + R * x.P; ll p = P * x.P + R * x.S + S * x.R; return {r, s, p}; }; }; string s; vector<ll> close; janken parse(ll l, ll r){ if(l + 1 == r){ // 1文字なら変換 if(s[l] == 'R') return {1, 0, 0}; if(s[l]=='S') return {0, 1, 0}; if(s[l]=='P') return {0, 0, 1}; return {1, 1, 1}; } vector<janken> a; vector<char> b; rep(i, l, r){ // カッコがあったら再帰しながら分解 if(s[i] == '('){ a.push_back(parse(i + 1, close[i] - 1)); i = close[i] - 1; } else if(s[i] >= '?') a.push_back(parse(i, i + 1)); // '*' < '+' < '-' < '?' < 'P' < 'R' < 'S' else b.push_back(s[i]); } vector<janken> c = {a.front()}; // * だけ計算 vector<char> d; rep(i, 0, b.size()){ if(b[i] == '*') c.back() = c.back() * a[i+1]; else{ c.push_back(a[i + 1]); d.push_back(b[i]); } } janken ans = c.front(); // + - を計算 rep(i, 0, d.size()){ if(d[i] == '+') ans = ans + c[i + 1]; else ans = ans - c[i + 1]; } return ans; } int main(){ ll n; char c; cin >> n >> s >> c; close.resize(n); vector<ll> q; rep(i, 0, n){ // 対応するカッコを調べる if(s[i] == '(') q.push_back(i); else if(s[i] == ')'){ close[q.back()] = i + 1; q.pop_back(); } } janken ans = parse(0, n); if(c == 'R') cout << ans.R << endl; else if(c=='S') cout << ans.S << endl; else cout << ans.P << endl; }