ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

2018-09-22から1日間の記事一覧

会津大学競技プログラミング合宿2018参加記

ということで、9/19~9/21に行われた、会津大学の競プロ合宿に参加してきました。 目次 一日目 A問題 B問題 C問題 D問題 E問題 F問題 G問題 H問題 感想 二日目 A問題 B問題 C問題 D問題 E問題 F以降 感想 三日目 A問題 B問題 C問題 D問題 E問題 F問題 G問題 …

AOJ 2894 - Aizu Competitive Programming Camp 2018 Day 3 F 01 文字列と窓 (Binary String with Slit

問題 解法 サンプルの最後のケースで実験をすると、なんとなく見えてきます。 まず、移動の手段をすべて書くと、 01 → 10 10 → 01 10 → 11 11 → 10 の4通りしか存在しません。 そして、SとTが一致していない、一番左側の部分を一致させるには、それより右側…

AOJ 2892 - Aizu Competitive Programming Camp 2018 Day 3 D しりとり圧縮 (Shiritori Compressio

問題 解法 この解法はばたこ(@btk15049)さんから聞いたものになります。 dp[i] = i番目の単語までで、消去できる単語数の最大値 とします。 すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。 i番目の単語を利用…

AOJ 2889 - Aizu Competitive Programming Camp 2018 Day 3 A IPアドレス (Internet Protocol Address)

問題 解法 分ける点が3つのみなので、for文の3重ループで点をうつ場所を決めてから、それぞれが条件を満たしているかどうかチェックすることになります。 開始位置と終了位置、そして細かい条件のどれかでミスが生じると、デバッグが大変になるので気を付け…

AOJ 3042 - Aizu Competitive Programming Camp 2018 Day 2 D Gridgedge

問題 解法 縦と横に分けて考えます。 座標aからbに移動するとき、考えられるパターンは3つあり、 そのままaからbに直接いくパターン 座標0に移動してからbにいくパターン 座標r-1(およびc-1)に移動してからbにいくパターン になります。 また、座標をワープ…

AOJ 3041 - Aizu Competitive Programming Camp 2018 Day 2 C Round And Round

問題 解法 配列の中身をいじるクエリでは、処理後も配列の中身の順番自体は変わらず常に昇順になっています。 ということで、現在の先頭の数字のみがわかっていれば、出力のクエリに対応できます。 具体的には、配列をいじるクエリで、kが入力されたとき、先…

AOJ 3039 - Aizu Competitive Programming Camp 2018 Day 2 A Special Chat

問題 解法 大きい値段から貪欲に払えるだけ払えば答えが求まります。 じつは、求められているものが合計金額なので、500についてのみ考えればいいらしいです。 提出コードはこちらになります。 #include <bits/stdc++.h> using namespace std; int memo[4] = {10000, 5000, </bits/stdc++.h>…

AGC027 C - ABland Yard

問題 提出コード なんか最近すごい似た問題を見たような…(前日の練習会でこの問題を解いていました) ある頂点から、AとBが書かれている頂点どちらか片方にしかいけなくなった時点でその頂点を消してしまいます。 これを繰り返していき、頂点が残っていればYe…

AGC027 A - Candy Distribution Again

問題 提出コード 貪欲法です。 を昇順にソートし、少ない方から順番に配っていけばよいです。配ったら残っているキャンディの量を減らしていきます。 最後だけ注意が必要で、残っている数と必要な数が等しいなら人数をカウントすることができ、そうでなけれ…