[python] ABC196 D Hanjo

1.方針

まず、並べて実験してみる。

すると、長方形の畳をA枚並べると、正方形の畳の敷き方は一通りに定まることがわかる。

長方形の畳の並べ方は、左上の1メートル四方のスペースから順に敷き詰めていくと考えると、各スペース毎に「横向きに敷く」「縦向きに敷く」「何も敷かない」の3通りある

計算量は3**16だが、再帰が途中で打ち切られるパターンもあるので、間に合いそう。

2.ソースコード
コードの途中でresを初期化しておかないと、resの値が累積的に計算されるので注意。
イメージとしては、再帰の底の値だけを拾ってくるイメージ。

h, w, a, b = map(int, input().split())

used = [[False]*(w) for _ in range(h)]
# print(used)
def recursion(x, y, a):
  if a == 0:
    return 1
  
  if y == h:
    return 0
  
  if x == w:
    return recursion(0, y+1, a)
  
  if used[y][x]:
    return recursion(x+1, y, a)

  res = 0

  # 横向きに敷く
  if x + 1 <= w - 1:
    if not used[y][x+1]:
      used[y][x] = used[y][x+1] = True
      res += recursion(x+2, y, a-1)
      used[y][x] = used[y][x+1] = False
  
  # 縦向きに敷く
  if y + 1 <= h - 1:
    if not used[y+1][x]:
      used[y][x] = used[y+1][x] = True
      res += recursion(x+1, y, a-1)
      used[y][x] = used[y+1][x] = False
  
  # 何も敷かん
  res += recursion(x+1, y, a)

  return res

ans = recursion(0, 0, a)

print(ans)

※resをグローバル関数として、if a== 0:のときに+1する処理でもok
（https://atcoder.jp/contests/abc196/submissions/28797922）

vscode 便利なショートカットまとめ

環境

windows10

vscode ver1.62.0

vscodeでよく使いそうなショートカットキーをまとめました。

（随時、更新します。）

コピペ

Ctrl + C：カーソル行をすべてコピー or 範囲指定した箇所をコピー

Ctrl + X：カーソル行をすべて切り取り or 範囲指定した箇所を切り取り

Shift + Alt + ↑ / ↓：カーソル行をコピーし、1行上 / 下にペースト

削除

Ctrl + Shift + K：カーソル行を削除

カーソルの移動

Ctrl + Home(Fn + ←)：カーソルを先頭まで移動

Ctrl + End(Fn + →)：カーソルを末尾まで移動

Ctrl + G：カーソルの移動先を入力する窓を表示

選択

Ctrl + Alt + ↑ / ↓：行ごと範囲を選択

Ctrl + L ：カーソル行を選択

検索

Ctrl + \：同フォルダ内の同じオブジェクト（変数、関数など）を検索

Ctrl + F：検索

Ctrl + H：検索と置換

インデント

Ctrl + ]：カーソル行の先頭にインデント（Tab）を挿入

Ctrl + [：カーソル行の先頭のインデントを削除（outdentする）

改行

Ctrl + Enter：カーソル行の下に空行を挿入

Ctrl + Shift + Enter：カーソル行の上に空行を挿入

ファイル・フォルダの移動

Ctrl + Shift + Tab：展開しているファイルに順次移動

Ctrl + P：移動したいファイルを選択する画面を表示

参考元：Visual Studio Code 公式ドキュメント

code.visualstudio.com

閲覧日　2021/11/11

ショートカットキーの合わせ技

①カーソル行を含む複数行を選択したいとき

Ctrl + Lでカーソル行を選択

↓

Shift + ↑ / ↓で範囲を指定