結果
| 問題 |
No.2623 Room Allocation
|
| コンテスト | |
| ユーザー |
 So-rei
|
| 提出日時 | 2024-02-10 20:46:52 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 37,688 bytes |
| コンパイル時間 | 8,074 ms |
| コンパイル使用メモリ | 167,480 KB |
| 実行使用メモリ | 77,320 KB |
| 最終ジャッジ日時 | 2024-09-28 17:17:42 |
| 合計ジャッジ時間 | 12,303 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 3 TLE * 1 -- * 26 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (92 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading;
using System.Xml;
using static SolveApp.In;
using static SolveApp.Out;
namespace SolveApp
{
class Program
{
static void Main(string[] args)
{
new yuki2623();
}
//☆1
public class yuki2621
{
public yuki2621()
{
//input-------------
(var A, var B, var C) = In.ReadTuple3<int>();
//calc--------------
Out.Write(Math.Min(B, A * C));
return;
}
}
//☆2.5
public class yuki2623
{
public yuki2623()
{
//input-------------
(var N, var X, var Y) = In.ReadTuple3<int>();
var pc = In.ReadTuple2Many<long, string>(N);
//calc--------------
// X+Y+1組目以降のi組目の人は、(i-X-Y)組目の部屋にしかはいることが出来ない!
// なので、X+Y個の部屋には
// 1人目を入れた部屋：1+X+Y, 1+2(X+Y),...人目が入る
// 2人目を入れた部屋：2+X+Y, ・・・が入る
// ・・・
//となる。X+Y人目までに部屋をどう振り分けるのが最適か？がこの答えのはず
int mod = Math.Min(N, X + Y);
var pairs = new (long x, long y)[mod];
for (int i = 0; i < N; i++)
{
if (pc[i].b == "A")
pairs[i % mod].x += pc[i].a;
else
pairs[i % mod].y += pc[i].a;
}
// dp[i] = ある人数までをどの部屋に入れたかが確定している時に、機械Aの部屋がi個埋まっている状態で、最大の希望人数を満たす値
var dp = new long[1];
for (int i = 0; i < mod; i++)
{
var nextdp = new long[i + 2];
for (int j = 0; j <= i; j++)
{
// yの部屋を埋めた
if (i - j + 1 <= Y)
nextdp[j] = Math.Max(nextdp[j], dp[j] + pairs[i].y);
if (j + 1 > X) break; //X部屋を超えた分は計算しなくて良い
// xの部屋を埋めた
nextdp[j + 1] = Math.Max(nextdp[j + 1], dp[j] + pairs[i].x);
}
dp = nextdp;
}
Out.Write(dp.Max());
return;
}
}
}//
//Common Class------------------------------------------------------------------------------------------------------------------------------------------
public static class In
{
//1行=>1個の値取得
public static T Read<T>() { var s = Console.ReadLine(); return (T)Convert.ChangeType(s, typeof(T)); }
//1行=>n個の配列値取得
public static T[] ReadAry<T>() { return Array.ConvertAll(Console.ReadLine().Split(' '), e => (T)Convert.ChangeType(e, typeof(T))); }
//n行=>1個の値取得
public static List<T> ReadMany<T>(long n) { var TT = new List<T>(); for (long i = 0; i < n; i++) TT.Add(Read<T>()); return TT; }
//n行=>*個の配列値取得
public static List<T[]> ReadManyAry<T>(long n) { var TT = new List<T[]>(); for (long i = 0; i < n; i++) TT.Add(ReadAry<T>()); return TT; }
//1行=>"0101..."の文字列をint配列で取得
public static int[] Read01() => Array.ConvertAll(Read<string>().ToCharArray(), e => (int)Convert.ChangeType(e.ToString(), typeof(int)));
//1行=>n個のタプル取得
public static (T, T) ReadTuple2<T>() { var c = ReadAry<T>(); return (c[0], c[1]); }
public static (T, U) ReadTuple2<T, U>() { var c = ReadAry<string>(); return ((T)Convert.ChangeType(c[0], typeof(T)), (U)Convert.ChangeType(c[1], typeof(U))); }
public static List<(T a, T b)> ReadTuple2Many<T>(long n) { var TT = new List<(T, T)>(); for (long i = 0; i < n; i++) TT.Add(ReadTuple2<T>()); return TT; }
public static List<(T a, U b)> ReadTuple2Many<T, U>(long n) { var TT = new List<(T, U)>(); for (long i = 0; i < n; i++) TT.Add(ReadTuple2<T, U>()); return TT; }
public static (T, T, T) ReadTuple3<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2]); }
public static (T, U, V) ReadTuple3<T, U, V>() { var c = ReadAry<string>(); return ((T)Convert.ChangeType(c[0], typeof(T)), (U)Convert.ChangeType(c[1], typeof(U)), (V)Convert.ChangeType(c[2], typeof(V))); }
public static (T, T, T, T) ReadTuple4<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3]); }
public static (T, T, T, T, T) ReadTuple5<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3], c[4]); }
public static (T, T, T, T, T, T) ReadTuple6<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3], c[4], c[5]); }
}
public static class Out
{
//1行出力
public static void Write<T>(T item) => Console.WriteLine(item);
//1行n個出力
public static void WriteAry<T>(IEnumerable<T> items, string separetor = " ") => Write(string.Join(separetor, items));
//n行1個出力
public static void WriteMany<T>(IEnumerable<T> items, string separetor = " ") { foreach (var _i in items) Write(_i); }
//n*m行1個出力
public static void WriteMany<T>(T[,] items, string separetor = " ") { foreach (var _i in items) WriteAry(string.Join(separetor, _i)); }
//n行m列出力
public static void WriteManyAry<T>(IEnumerable<IEnumerable<T>> items, string separetor = " ") { foreach (var _i in items) WriteAry(_i, separetor); }
public static void WriteManyAry<T>(IEnumerable<T[]> items, string separetor = " ") { foreach (var _i in items) WriteAry(_i, separetor); }
public static void WriteManyAry<T>(T[,] items, string separetor = " ") { for (int i = 0; i < items.GetLength(0); i++) { var ary = new T[items.GetLength(1)]; for (int j = 0; j < items.GetLength(1); j++) { ary[j] = items[i, j]; } WriteAry(ary); } }
//Y/N出力
public static void WriteYN(bool result) { if (result) Write("Yes"); else Write("No"); }
}
public struct Con
{
public const long Mod = 998244353;
}
public enum Order
{
Ascending = 1,
Descending = -1
}
/// <summary>
/// はなちる氏のをほぼそのまま使ってます
/// https://www.hanachiru-blog.com/entry/2020/06/19/141057
/// LowerBoundを追加。TはIComparableに変更
/// </summary>
/// <typeparam name="T"></typeparam>
public class SegmentTree<T>// where T : IComparable<T>
{
public int N { get; private set; }
public int length { get; private set; }
private T[] _tree;
private readonly Func<T, T, T> _updateMethod;
private readonly T _initValue;
//private struct DefaultComparer<U> : IComparer<T> where U : IComparable<T> { public int Compare(T x, T y) => x.CompareTo(y); }
/// <summary>
/// セグメント木の初期化
/// </summary>
/// <param name="items">要素達</param>
/// <param name="updateMethod">更新する方法</param>
/// <param name="initValue">セグメント木のノードの初期値</param>
public SegmentTree(IEnumerable<T> items, Func<T, T, T> updateMethod, T initValue)
{
T[] array = items.ToArray();
_updateMethod = updateMethod;
_initValue = initValue;
length = array.Length;
// セグ木の最下段は２の冪乗にする
N = 1;
while (N < length) N *= 2;
_tree = Enumerable.Repeat(initValue, 2 * N - 1).ToArray();
// 最下段に要素達を入れた後、下の段から更新していく
for (int i = 0; i < length; i++) _tree[N + i - 1] = array[i];
for (int i = N - 2; i >= 0; i--) _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);
}
/// <summary>
/// 更新する
/// </summary>
/// <param name="i">更新したい値のインデックス</param>
/// <param name="x">更新する値</param>
public void Update(int i, T x)
{
// 更新したい要素のセグ木上でのインデックスを取得
i = N + i - 1;
// 値を更新した後に、どんどん親を更新していく
_tree[i] = x;
while (i > 0)
{
i = (i - 1) / 2;
_tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);
}
}
/// <summary>
/// 区間内の目的の値を取得する，要求区間[a, b)
/// </summary>
/// <param name="a">a以上の区間</param>
/// <param name="b">b未満の区間</param>
/// <returns></returns>
public T Execute(int a, int b)
=> Execute(a, b, 0, 0, N);
private T Execute(int a, int b, int k, int l, int r)
{
// 要求区間[a, b)に対して対象区間[l, r)を求める
// 今いるノードのインデックスがk
// 要求区間と対象区間が交わらない
if (r <= a || b <= l) return _initValue;
// 要求区間が対象区間を完全に被覆
if (a <= l && r <= b) return _tree[k];
// 要求区間が対象区間の一部を被覆しているので、子について探索を行う
// 新しい対象区間は、現在の対象区間を半分に割ったもの
var vl = Execute(a, b, 2 * k + 1, l, (l + r) / 2);
var vr = Execute(a, b, 2 * k + 2, (l + r) / 2, r);
return _updateMethod(vl, vr);
}
/// <summary>
/// T[]が一様の単調増加のときのみ使用可
/// [a,b)の範囲で値がv以下になる最大のindex:rを二分探索で求める
/// </summary>
/// <param name="v"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
public int LowerBound(T v, int left = 0, int right = int.MaxValue)
{
left = Math.Max(0, left);
int l = left;
int r = Math.Min(length, right);
while (l < r)
{
int mid = l + (r - l) / 2;
if (Comparer<T>.Default.Compare(Execute(left, mid + 1), v) <= 0)
l = mid + 1;
else
r = mid;
}
return l;
}
}
/// <summary>
/// SCC : Strongly Connected Component
/// 任意の頂点v,uについて、v→uのパスとu→vのパスが存在する時、それらを同一の強連結成分という
/// この同一の強連結成分のグループを取得する
/// 自己辺,多重辺が含まれていてもOK
/// 参考：https://qiita.com/AkariLuminous/items/a2c789cebdd098dcb503
/// 入力にConnectedGlaphを使用
/// </summary>
public static class SCC
{
public static (int count, List<List<int>> groups) GetScc(int n, ConnectedGlaph cg)
{
var visited = new Stack<int>();
int now_ord = 0, group_count = 0;
var low = new int[n];
var ids = new int[n];
var ord_ = new int[n];
//初期化
for (int i = 0; i < n; i++)
ord_[i] = -1;
//まだ見ていない頂点を順番に見ていく
for (int i = 0; i < n; i++)
if (ord_[i] < 0)
DFS_SCC(i);
//カウント処理
for (int i = 0; i < n; i++)
ids[i] = group_count - 1 - ids[i];
//出力
var g = new List<List<int>>();
for (int i = 0; i < group_count; i++)
g.Add(new List<int>());
for (int i = 0; i < n; i++)
g[ids[i]].Add(i);
return (group_count, g);
void DFS_SCC(int v)
{
low[v] = ord_[v] = now_ord;
now_ord++;
visited.Push(v);
if (cg[v] != null)
{
// 行き先がある
foreach (var to in cg[v])
{
if (ord_[to] == -1)
{
DFS_SCC((int)to);
low[v] = Math.Min(low[v], low[to]);
}
else
{
low[v] = Math.Min(low[v], ord_[to]);
}
}
}
//帰りがけ
if (low[v] == ord_[v])
{
while (true)
{
int u = visited.Pop();
ord_[u] = n;
ids[u] = group_count;
if (u == v) break;
}
group_count++;
}
}
}
}
/// <summary>
/// ダイクストラ法
/// 各ノードへの最短経路を、始点の周辺から１個所ずつ確定し、徐々に範囲を広げていく方法
/// グラフの重みマイナスがある場合は不可
/// PriorityQueue、ConnectedGlaphAndValueを使用する
/// </summary>
public static class AlgoDijkstra
{
/// <summary>
/// ダイクストラ法処理メイン
/// i→jの重みgは配列pの[i,j]に書かれていることとする
/// </summary>
public static long[] GetEachWeight(long[,] p, int _start = 0, Order order = Order.Descending)
{
int start = _start;
int size = p.GetLength(0);
//判明したフラグ
var seen = new bool[size];
seen[start] = true;
//判明した最小重み
var pw = new long[size];
pw[start] = 0;
//判明数
int cnt = 0;
//優先度つきキューで近い場所から順に探す
var pq = new PriorityQueue<(long p, int idx)>(Compare, order);
for (int i = 0; i < size; i++)
pq.Push((p[start, i], i));
while (pq.Count > 0)
{
var v = pq.Pop();
if (seen[v.idx]) continue; //既知の頂点は飛ばす
seen[v.idx] = true;
pw[v.idx] = v.p;
cnt++;
if (cnt == size) break;
for (int i = 0; i < size; i++)
{
if (seen[i]) continue; //既知の頂点は飛ばす
pq.Push((v.p + p[v.idx, i], i));
}
}
return pw;
}
/// <summary>
/// ダイクストラ法処理メイン
/// p:(index,i,j,p) : index番目の辺が、i→jの重みg とする ※有向グラフの場合はisDirection=falseにすること
/// order:最小or最大
/// </summary>
public static long[] GetEachWeight(List<(int index, int i, int j, long g)> p, int n, int _start = 0, bool isDirection = true, Order order = Order.Descending)
{
int start = _start;
int size = n;
int rowcount = p.Count;
//判明したフラグ
var seen = new bool[size];
seen[start] = true;
//判明した最小重み
var pw = new long[size];
pw[start] = 0;
//判明数
int cnt = 0;
//繋がっているかどうかを処理する
var ab = new long[rowcount][];
for (int i = 0; i < rowcount; i++)
ab[i] = new long[] { p[i].i, p[i].j, p[i].g, p[i].index };
var con = new ConnectedGlaphAndValue(ab, isDirection);
//優先度つきキューで近い場所から順に探す
var pq = new PriorityQueue<(long p, int rowindex, int idx)>(Compare, order);
for (int c = 0; c < rowcount; c++)
{
if (p[c].i == start)
pq.Push((p[c].g, p[c].index, p[c].j));
if (isDirection && p[c].j == start)
pq.Push((p[c].g, p[c].index, p[c].i));
}
while (pq.Count > 0)
{
var v = pq.Pop();
if (seen[v.idx]) continue; //既知の頂点は飛ばす
seen[v.idx] = true;
pw[v.idx] = v.p;
cnt++;
//
//v.idxが接続している直前の辺は、v.rowindexで取得できる
//
if (cnt == size) break;
foreach (var next in con[v.idx])
{
if (seen[next.Key]) continue; //既知の頂点は飛ばす
pq.Push((v.p + next.Value[0], (int)next.Value[1], (int)next.Key));
}
}
return pw;
}
//goalまでの距離だけ知りたいVer
public static long GetSingle(long[,] p, int _start = 0, int _goal = -1, Order order = Order.Descending)
{
int start = _start;
int goal = _goal == -1 ? p.GetLength(0) : _goal;
int size = p.GetLength(0);
//判明したフラグ
var seen = new bool[size];
//判明した最小重み
var pw = new long[size];
seen[start] = true;
pw[start] = 0;
//優先度つきキューで近い場所から順に探す
var pq = new PriorityQueue<(long p, int idx)>(Compare, order);
for (int i = 0; i < size; i++)
pq.Push((p[start, i], i));
while (pq.Count > 0)
{
var v = pq.Pop();
if (seen[v.idx]) continue; //既知の頂点は飛ばす
seen[v.idx] = true;
pw[v.idx] = v.p;
if (v.idx == goal) break; //向かいたい頂点の距離が判明したので終了する
for (int i = 0; i < size; i++)
{
if (seen[i]) continue; //既知の頂点は飛ばす
pq.Push((v.p + p[v.idx, i], i));
}
}
return pw[goal];
}
private static int Compare((long p, int idx) x, (long p, int idx) y)
{
return x.p > y.p ? 1 : -1;
}
static int Compare((long p, int rowindex, int idx) x, (long p, int rowindex, int idx) y)
{
return x.p > y.p ? 1 : -1;
}
}
/// <summary>
/// 優先度付き待ち行列
/// </summary>
/// <typeparam name="T">要素の型</typeparam>
public class PriorityQueue<T> : IEnumerable<T> //where T : IComparable<T>
{
#region フィールド
private List<T> buffer;
private readonly Comparison<T> cmp;
private readonly int reverseFactor;
#endregion
#region 初期化
//基本
public PriorityQueue()
{
cmp = Comparer<T>.Default.Compare;
buffer = new List<T>();
reverseFactor = (int)Order.Descending;
}
//容量決めての初期化(気持ち早くなる), ソート順を決めての初期化
public PriorityQueue(int capacity = -1, Order _reverseFactor = Order.Descending)
{
cmp = Comparer<T>.Default.Compare;
buffer = new List<T>(capacity);
reverseFactor = (int)_reverseFactor;
}
//初期配列をそのまま入れる初期化, ソート順を決めての初期化
public PriorityQueue(IEnumerable<T> initBuffer, Order _reverseFactor = Order.Descending)
{
cmp = Comparer<T>.Default.Compare;
buffer = new List<T>(initBuffer.Count());
reverseFactor = (int)_reverseFactor;
foreach (var ib in initBuffer)
PushHeap(ib);
}
//比較ルールを決めての初期化1
public PriorityQueue(Comparison<T> comparison, Order _reverseFactor = Order.Descending)
{
cmp = comparison;
buffer = new List<T>();
reverseFactor = (int)_reverseFactor;
}
//比較ルールを決めての初期化2
public PriorityQueue(IComparer<T> comparer, Order _reverseFactor = Order.Descending)
{
cmp = comparer.Compare;
buffer = new List<T>();
reverseFactor = (int)_reverseFactor;
}
#endregion
#region ヒープ操作
/// <summary>
/// ヒープ化されている配列リストに新しい要素を追加する。
/// </summary>
/// <param name="buffer">対象の配列リスト</param>
private void PushHeap(T elem)
{
int n = buffer.Count;
buffer.Add(elem);
while (n != 0)
{
int i = (n - 1) / 2;
if (Compare(buffer[n], buffer[i]) < 0)
{
var tmp = buffer[i];
buffer[i] = buffer[n];
buffer[n] = tmp;
}
n = i;
}
}
/// <summary>
/// ヒープから最大値を削除し、その値を返す。O(logN)
/// </summary>
/// <returns>優先度付きキューから削除された要素</returns>
public T PopHeap()
{
var ret = buffer[0];
var pos = 0;
int cnt = buffer.Count - 1;
var x = buffer[cnt];
while (pos * 2 + 1 < cnt)
{
var lch = pos * 2 + 1;
var rch = pos * 2 + 2;
if (rch < cnt && Compare(buffer[rch], buffer[lch]) < 0) lch = rch;
if (Compare(buffer[lch], x) >= 0)
break;
buffer[pos] = buffer[lch];
pos = lch;
}
buffer[pos] = x;
buffer.RemoveAt(cnt);
return ret;
}
#endregion
#region 要素の挿入・削除
/// <summary>
/// 要素のプッシュ。
/// </summary>
/// <param name="elem">挿入したい要素</param>
public void Push(T elem) => PushHeap(elem);
public void Enqueue(T elem) => PushHeap(elem);
/// <summary>
/// 要素を1つポップ。
/// </remarks>
public T Pop() => PopHeap();
public T Dequeue() => PopHeap();
/// <summary>
/// 先頭要素の読み出し。
/// </summary>
public T Peek() => buffer[0];
/// <summary>
/// カウント
/// </summary>
public int Count { get => buffer.Count; }
public int Compare(T a, T b) => reverseFactor * cmp(a, b);
public IEnumerator<T> GetEnumerator()
{
foreach (var t in buffer)
yield return Pop();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
#endregion
}
/// <summary>
/// Union-Find atcoder::dsuを参考に高速化済(ソースは別言語のサンプルをもとに作成)
/// 2次元対応追加
/// </summary>
public class UnionFind
{
int[] par; //親がいるとき、親のindex。 ／ 親がいない(自分が一番上)のとき、子の要素の数*(-1)
int h, w; //二次元Union-Find用 初期化時にセット必須
// インスタンスでサイズセットと初期化
public UnionFind(int h, int w) : this(h * w)
{
this.h = h;
this.w = w;
}
public UnionFind(int n)
{
par = new int[n];
for (int i = 0; i < n; i++)
par[i] = -1;
}
// 別のufを使いまわしたい時専用
public UnionFind(UnionFind un)
{
par = new int[un.par.Length];
Array.Copy(un.par, par, un.par.Length);
this.h = un.h;
this.w = un.w;
}
// 親を探す
public int Find(int i, int j) => Find(i * w + j);
public int Find(int x)
{
if (par[x] < 0) return x;
return par[x] = Find(par[x]);
}
// 接続する(親が一致しない時)
public void Unite(int xi, int xj, int yi, int yj) => Unite(xi * w + xj, yi * w + yj);
public void Unite(int x, int y)
{
x = Find(x);
y = Find(y);
if (x == y) return;
if (-par[x] < -par[y]) (x, y) = (y, x);
//ツリー情報更新
par[x] += par[y];
par[y] = x;
}
// 同じかどうかチェック
public bool IsSame(int xi, int xj, int yi, int yj) => Find(xi, xj) == Find(yi, yj);
public bool IsSame(int x, int y) => Find(x) == Find(y);
public int Size(int xi, int xj) => -par[Find(xi, xj)];
public int Size(int x) => -par[Find(x)];
}
/// <summary>
/// 連結グラフの問題用
/// U,V,(params)
/// isDirection:有向グラフ:false, 無向:true
/// </summary>
public class ConnectedGlaph : IEnumerable<(long u, long v)>
{
public Dictionary<long, List<long>> _sortedGlaph;
private List<(long u, long v)> _Array; //ToArrayやCountなどが毎回O(グラフの数)だけかかってしまうため、1回やったときに作っておく
//入力から直接取り込むVer
public ConnectedGlaph(int rowcnt, bool isDirection = false, bool isMinusOne = false)
{
int tc = rowcnt;
int minus = isMinusOne ? 1 : 0;
_sortedGlaph = new Dictionary<long, List<long>>();
for (int r = 0; r < tc; r++)
{
long[] t = In.ReadAry<long>();
if (_sortedGlaph.TryGetValue(t[0] - minus, out var cols))
cols.Add(t[1] - minus);
else
_sortedGlaph[t[0] - minus] = new List<long>() { t[1] - minus };
if (isDirection) //反対方向
{
if (_sortedGlaph.TryGetValue(t[1] - minus, out var colsx))
colsx.Add(t[0] - minus);
else
_sortedGlaph[t[1] - minus] = new List<long>() { t[0] - minus };
}
}
foreach (var v in _sortedGlaph.Values)
v.Sort();
}
//配列から取り込むVer
public ConnectedGlaph(long[][] t, bool isDirection = false, bool isMinusOne = false)
{
int tc = t.Count();
int minus = isMinusOne ? 1 : 0;
_sortedGlaph = new Dictionary<long, List<long>>();
for (int i = 0; i < tc; i++)
{
if (_sortedGlaph.TryGetValue(t[i][0] - minus, out var cols))
cols.Add(t[i][1] - minus);
else
_sortedGlaph[t[i][0] - minus] = new List<long>() { t[i][1] - minus };
}
if (isDirection) //反対方向
{
for (int i = 0; i < tc; i++)
{
if (_sortedGlaph.TryGetValue(t[i][1] - minus, out var cols))
cols.Add(t[i][0] - minus);
else
_sortedGlaph[t[i][1] - minus] = new List<long>() { t[i][0] - minus };
}
}
foreach (var v in _sortedGlaph.Values)
v.Sort();
}
public ConnectedGlaph(int[][] t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
public ConnectedGlaph(List<int[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
public ConnectedGlaph(List<long[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
//存在する[i,*]の*のコレクションを返す
public List<long> this[long i]
{
get
{
if (_sortedGlaph.TryGetValue(i, out var cols))
return cols;
else
return null;
}
}
//そのグラフがあるかどうか。
public bool IsExist(long i, long j)
{
if (!_sortedGlaph.ContainsKey(i)) return false;
int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
if (idx == -1) return false;
return true;
}
private int GetIndex(long row, long i, int st = 0, int ed = -1)
{
if (ed - st <= 0)//最後1回
return _sortedGlaph[row][st] == i ? st : -1;
int half = st + (ed - st) / 2;
if (_sortedGlaph[row][half] > i)
return GetIndex(row, st, half);
else if (_sortedGlaph[row][half] < i)
return GetIndex(row, half + 1, ed);
else
return half;
}
//以下、IEnumerable<(u,v)>として操作したいときの処理
public int Count()
{
TryMakeArray();
return _Array.Count();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public IEnumerator<(long u, long v)> GetEnumerator()
{
TryMakeArray();
return new Enumerator(_Array);
}
private void TryMakeArray()
{
if (_Array == null)
{
_Array = new List<(long u, long v)>();
foreach (var d in _sortedGlaph)
foreach (var e in d.Value)
_Array.Add((d.Key, e));
}
}
// IEnumeratorを実装する
public class Enumerator : IEnumerator<(long u, long v)>
{
private readonly List<(long u, long v)> list;
private int index;
internal Enumerator(List<(long u, long v)> list)
{
this.list = list;
index = -1;
}
public bool MoveNext()
{
index++;
return (uint)index < (uint)list.Count;
}
public void Reset()
{
index = -1;
}
public (long u, long v) Current => list[index];
object IEnumerator.Current => Current;
public void Dispose() { }
}
}
/// <summary>
/// 連結グラフの問題用
/// U,V,(params)
/// isDirection:有向グラフ:false, 無向:true
/// </summary>
public class ConnectedGlaphAndValue : IEnumerable<(long u, long v, long[] p)>
{
private Dictionary<long, List<(long Key, long[] Value)>> _sortedGlaph;
private Dictionary<long, (int left, int right)> _knowIndex; //特定のiから始まる[i,*]のデータが多いときで、[i,*]検索するときは、何度も行うことになるので効率化のためここに覚えておく。
//入力から直接取り込むVer
public ConnectedGlaphAndValue(int rowcnt, bool isDirection = false, bool isMinusOne = false)
{
int tc = rowcnt;
int minus = isMinusOne ? 1 : 0;
_sortedGlaph = new Dictionary<long, List<(long Key, long[] Value)>>();
_knowIndex = new Dictionary<long, (int left, int right)>();
for (int r = 0; r < tc; r++)
{
long[] t = In.ReadAry<long>();
if (_sortedGlaph.TryGetValue(t[0] - minus, out var cols))
cols.Add((t[1] - minus, t.Skip(2).ToArray()));
else
_sortedGlaph[t[0] - minus] = new List<(long, long[])>() { (t[1] - minus, t.Skip(2).ToArray()) };
if (isDirection) //反対方向
{
if (_sortedGlaph.TryGetValue(t[1] - minus, out var colsx))
colsx.Add((t[0] - minus, t.Skip(2).ToArray()));
else
_sortedGlaph[t[1] - minus] = new List<(long, long[])>() { (t[0] - minus, t.Skip(2).ToArray()) };
}
}
foreach (var v in _sortedGlaph.Values)
v.Sort();
}
public ConnectedGlaphAndValue(long[][] t, bool isDirection = false, bool isMinusOne = false)
{
int tc = t.Count();
int minus = isMinusOne ? 1 : 0;
_sortedGlaph = new Dictionary<long, List<(long Key, long[] Value)>>();
_knowIndex = new Dictionary<long, (int left, int right)>();
for (int i = 0; i < tc; i++)
{
if (_sortedGlaph.TryGetValue(t[i][0] - minus, out var cols))
cols.Add((t[i][1] - minus, t[i].Skip(2).ToArray()));
else
_sortedGlaph[t[i][0] - minus] = new List<(long, long[])>() { (t[i][1] - minus, t[i].Skip(2).ToArray()) };
}
if (isDirection) //反対方向
{
for (int i = 0; i < tc; i++)
{
if (_sortedGlaph.TryGetValue(t[i][1] - minus, out var cols))
cols.Add((t[i][0] - minus, t[i].Skip(2).ToArray()));
else
_sortedGlaph[t[i][1] - minus] = new List<(long, long[])>() { (t[i][0] - minus, t[i].Skip(2).ToArray()) };
}
}
foreach (var key in _sortedGlaph.Keys.ToArray())
_sortedGlaph[key] = _sortedGlaph[key].OrderBy(p => p.Key).ToList();
}
public ConnectedGlaphAndValue(int[][] t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
public ConnectedGlaphAndValue(List<int[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
public ConnectedGlaphAndValue(List<long[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
{
}
//存在する[i,*]の*のコレクションを返す
public IEnumerable<(long Key, long[] Value)> this[long i]
{
get
{
if (!_sortedGlaph.ContainsKey(i)) yield break;
foreach (var e in _sortedGlaph[i])
yield return e;
}
}
//そのグラフがあるかどうか。あればparams,なければnullを返す
public IEnumerable<long> this[long i, long j]
{
get
{
if (!_sortedGlaph.ContainsKey(i)) return null;
int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
if (idx == -1) return null;
return _sortedGlaph[i][idx].Value;
}
}
//そのグラフがあるかどうか。
public bool IsExist(long i, long j)
{
if (!_sortedGlaph.ContainsKey(i)) return false;
int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
if (idx == -1) return false;
return true;
}
private int GetIndex(long row, long i, int st = 0, int ed = -1)
{
if (ed - st <= 0)//最後1回
return _sortedGlaph[row][st].Key == i ? st : -1;
int half = st + (ed - st) / 2;
if (_sortedGlaph[row][half].Key > i)
return GetIndex(row, st, half);
else if (_sortedGlaph[row][half].Key < i)
return GetIndex(row, half + 1, ed);
else
return half;
}
public IEnumerator<(long u, long v, long[] p)> GetEnumerator()
{
foreach (var d in _sortedGlaph)
foreach (var e in d.Value)
yield return (d.Key, e.Key, e.Value);
}
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
}
}