AtCoder Beginner Contest 223 E - Placing Rectangles

f:id:yagura37s:20211021201004p:plain



長方形の張り方としては上の2パターンみたいな感じに分類できる

 

最初に 1 の置き場所を決める

1 は、上に長方形を接地しないことにする。

上に長方形を接地するようなパターンが最適だとしたら、

右側に、上に長方形が設置されていない長方形があることになる。

というわけで最初に、上に長方形を接地してないやつの置き場所を決める

できるだけX軸かY軸に押し付けるような形にしたほうが、残りの2個を置くための場所がとれそう

 

どっちの軸に押し付けるかの全探索と ABCのpermutationを全部試した

 

 

 

 

  1. fn solve(){
  2. let sssss = std::io::stdin();
  3. let mut sc = Scanner { stdin: sssss.lock() };
  4. let mut x:i64 = sc.read();
  5. let mut y:i64 = sc.read();
  6. let mut A:i64 = sc.read();
  7. let mut B:i64 = sc.read();
  8. let mut C:i64 = sc.read();
  9. let mut v= vec![A, B, C];
  10. let mut ok = false;
  11. fn dfs(x:i64, y:i64, i:usize, d:usize, v:&Vec<i64>)->bool{
  12. if x<0 || y<0{
  13. return false;
  14. }
  15. if i != 3 && x == 0 || y == 0{
  16. return false;
  17. }
  18. if i == 3{
  19. return true;
  20. }
  21. let mut res = false;
  22. if d == 0{
  23. let mut s = *1{
  24. let mut p = perm.into_iter().map(|x| *x).collect();
  25. ok |= dfs(x, y, 0, 0, &p);
  26. ok |= dfs(x, y, 0, 1, &p);
  27.  
  28.  
  29. }
  30. if ok{
  31. println!("Yes");
  32. }
  33. else{
  34. println!("No");
  35. }

 

 

解説とかツイッターとか見た

本番ではかなり無理そう

 

 

 

 

*1:v[i]-1)/y + 1);

  • res |= dfs(x-s, y, i+1, 0, v);
  • res |= dfs(x-s, y, i+1, 1, v);
  • }
  • else if d == 1{
  • let mut s = ((v[i]-1)/x + 1);
  • res |= dfs(x, y-s, i+1, 0, v);
  • res |= dfs(x, y-s, i+1, 1, v);
  • }
  • return res;
  • }
  • for perm in v.iter().permutations(v.len(