はじめに
こんにちは。
またまたCaffeineholicがお送りする（代表は一体何をしているんだ…？）ABC参加記、記事としては三回目になります。
今回は頑張ってDまで解いたのに負け！向こう一週間は機嫌が悪いまま生きていくことになるでしょう。
冗談はさておいて…今回も問題への所感を記載しております。D問題が思ったより多くの参加者に解かれていて、精進が足りないことを痛感した週になってしまいました。
結果サマリ
- ABC456
- WCPC参加人数: 6人
- 各問題の最速解答者(ペナルティ無し):
| 問題 | 参加者名 | タイム | 言語 |
|---|---|---|---|
| A | Caffeineholic | 1:06 | Python |
| B | Caffeineholic | 3:54 | Python |
| C | nsubaru | 12:19 | Java |
| D | nsubaru | 19:53 | Java |
| E | nsubaru | 90:34 | Java |
| F | - | - | - |
| G | - | - | - |
今週の出題
ABC456-A
問題文を表示
問題文
6 つの面を持つサイコロが 3 個あります。
どのサイコロも、面には 1, 2, 3, 4, 5, 6 が書かれています。
これらのサイコロを同時に振ったとき、出た目の合計が X になることはありますか？
制約
- 1 ≤ X ≤ 20
- X は整数
入力
X
出力
出た目の合計が X になることがあれば Yes、なければ No を出力せよ。
出る目のパターンを全探索しましょう。私自身としては、もっと賢いやり方があるはず…と考え込むのはC問題以降からと決め込んでいます。 A問題、B問題では全探索ができる制約のゆるい問題が出るので3重for文を書いて無事AC。
ABC456-B
問題文を表示
問題文
6 つの面を持つサイコロが 3 個あります。
i 個目のサイコロの j 個目の面には A_i,j が書かれています。
どのサイコロも、各面が出る確率は 1/6 です。
これらのサイコロを同時に振ったとき、4, 5, 6 の書かれた目が 1 つずつ出る確率を求めてください。
制約
- A_i,j は 1 以上 6 以下の整数
入力
A_1,1 A_1,2 A_1,3 A_1,4 A_1,5 A_1,6
A_2,1 A_2,2 A_2,3 A_2,4 A_2,5 A_2,6
A_3,1 A_3,2 A_3,3 A_3,4 A_3,5 A_3,6
出力
答えを出力せよ。真の解との絶対誤差または相対誤差が 10^-6 以下のとき正解とみなされる。
“確率”という単語を見て引け腰にならないようにしましょう。冷静に問題を読むと、取りうる216の状態のうちサイコロの目が｛4,5,6｝になっているのはいくつか？を数えるだけのシンプルな処理が求められるのみです。
私は3重for文の中で、出た目の集合が｛4,5,6｝と一致するかどうかを利用しましたが解説には 積が120なんて判定方法も書いてありましたね。なにはともあれ無事AC。
ABC456-C
問題文を表示
問題文
a, b, c からなる文字列 S が与えられます。
S の空でない部分文字列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分文字列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。
部分文字列とは
S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- S は
a,b,cからなる長さ 1 以上 3 × 10^5 以下の文字列
入力
S
出力
答えを出力せよ。
特定のデータ構造を必要としない、いわば即興力の求められる大好きなタイプのC問題。 abbcacなどの文字列はabとbcacの各部分に分けて、それぞれ独立に考えられます。同じ文字が隣り合ってしまう部分に跨るような部分列（この例だとabbcやabbcaなど）は考える意味がない（条件を満たさない）からです。 あとは**「同じ文字が隣り合う部分はないとして、その部分文字列がいくつあるか」**を公式を利用してO(1)で求められることに気づければ、この問題をO(N)で解くことができます。 MODを取り忘れており答えの大きい場合のテストケースで落ちてしまい、1WAの後AC。5分のペナルティは大きい…
ABC456-D
問題文を表示
問題文
a, b, c からなる文字列 S が与えられます。
S の空でない部分列であって、同じ文字が隣り合わないものの個数を 998244353 で割った余りを求めてください。
ただし、2 つの部分列が文字列として一致しても、取り出す位置が異なるならば区別するものとします。
制約
- S は
a,b,cからなる長さ 1 以上 3 × 10^5 以下の文字列
入力
S
出力
答えを出力せよ。
C問題の強化版であるD問題。文言としては”部分文字列”が”部分列”に置き換わったのみですが、アプローチはがらりと変わりました。
思考回路としては
部分列は列挙できないな → C問題のように利用できる特徴もないな → 文字列の問題だしDPか？ → 部分列を全パターンは持てないけど、次に見る文字に応じたデータの持ち方をしたいな → 次に見る文字と最後に出現した文字によって結果が変わるな → 最後に出た文字をキーにして数えていくことを繰り返せばいける…？
でした（思考の再現って難しい）。
解説にはスマートなDPのコードが載っているのでそちらを参考にしたほうが良いとは思いますが、私は(文字aで終わるもの) = (他の文字で終わるもの - (今までの)文字aで終わるもの) + ((今までの)文字aで終わるもの) + 1 = (他の文字で終わるもの) + 1 という考え方を利用し更新を進めるという方針にしました。
ABC456-E
問題文を表示
問題文
AtCoder 王国には N 個の都市があり、それぞれ都市 1, 2, …, N と呼ばれています。また都市同士を双方向に結ぶ M 本の道路があり、i 番目の道路は都市 U_i と都市 V_i を結んでいます。どの都市間もいくつかの道路を辿ることで行き来可能です。
AtCoder 王国では一週間が W 日からなります。一週間は曜日 1, 2, …, W と進んでいき、曜日 W の次の日は曜日 1 に戻ります。
都市ごとにいくつかの曜日が休日となっています。都市 i の休日の情報は長さ W の文字列 S_i で与えられ、S_i の j 文字目が o のとき曜日 j が休日であることを、x のとき曜日 j が平日であることを意味します。
高橋君は曜日 1 の日の昼に、好きな都市を選んでそこを訪問します。それ以降毎日夜に一度、今いる都市にとどまるか、道路で直接結ばれた都市のいずれかに移動することを繰り返します。毎日昼の時点でいる都市が休日であるように移動を続けることが可能ならば Yes を、不可能ならば No を出力してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 ≤ T ≤ 10^5
- 1 ≤ N ≤ 10^5
- N - 1 ≤ M ≤ 10^5
- 1 ≤ U_i < V_i ≤ N
- どの都市間もいくつかの道路を辿ることで行き来可能である
- 2 ≤ W ≤ 10
- T, N, M, U_i, V_i, W は整数
- S_i は
o,xからなる長さ W の文字列 - 全てのテストケースにおける N の総和は 10^5 以下
- 全てのテストケースにおける M の総和は 10^5 以下
入力
T
case_1
case_2
⋮
case_T
ここで case_i は i 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。
N M
U_1 V_1
U_2 V_2
⋮
U_M V_M
W
S_1
S_2
⋮
S_N
出力
T 行出力せよ。
i 行目には i 番目のテストケースについての答えを出力せよ。
実装も重そうなE問題。サークル内ではnsubaru君のみACを出していました。お見事！！ D問題が解けた時点で経過時間は67分。これ以上解き進めるのは絶望的でしたが、考えたことのみ書いておこうと思います。
Wが10までという制約があるので、頂点の数をW倍にして、次の曜日に進めるノードだけ見てサイクル検出かな？ → visited配列を二次元にして持っておこうかな？ → すでに通った経路に到達できても曜日の兼ね合いがあるから面倒そうだな → 解けず
でした。
ABC456-F以降
（これ以降の問題文は割愛します）
最後に
いかがでしたでしょうか。今回から、サマリに最速解答者も載せてみました。サークル全体のレベル感もわかりやすくなったので各員のモチベーションにつながればいいのですが。 代表は早く参加して記事書いてください。Caffeineholicでした。来週も頑張りましょう。